A* search (beta) in Unreal Tournament (1999)

BreadcrumbII.uc

class BreadcrumbII extends Actor;

// A* Search stuff
var(Breadcrumb_Search)		float			AdditionalCost;
var(Breadcrumb_Search)		float			DistanceFactor;
var(Breadcrumb_Search)		float			HeuristicFactor;

// Breadcrumb Linking stuff
var(Breadcrumb_Linker)		float			MaxLinkDistance;
var(Breadcrumb_Linker)		float			MinLinkDistance;

// Navigation
var(Breadcrumb_Navigation)	float			SpeedMultiplier;

function LeaveCrumb(Pawn Other)
{
	Other.GroundSpeed /= SpeedMultiplier;
}

function BreadcrumbList CrumbLinks()
{
	local BreadcrumbList myList;
	local BreadcrumbII myCrumb;
	
	foreach RadiusActors(class'BreadcrumbII', myCrumb, MaxLinkDistance)
	{
		if ( VSize(myCrumb.Location - Location) < MinLinkDistance || FastTrace(myCrumb.Location) )
			continue;
			
		myList.Insert(myCrumb);
	}
	
	return myList;
}

function float CostFor(BreadcrumbII Other, BreadcrumbMap dCosts, out BreadcrumbMap rCosts)
{
	local float cost;
	local float dc;
	
	if ( !dCosts.Get(Other, dc) )
		dc = 0;
	
	cost = VSize(Other.Location - Location) * HeuristicFactor + dc * DistanceFactor + AdditionalCost;
	rCosts.Set(Other, cost);
	
	return cost;
}

function BreadcrumbList GetPathTo(BreadcrumbII Destination, optional out BreadcrumbMap costs)
{
	local BreadcrumbMap rCosts;
	local BreadcrumbMap dCosts;
	local BreadcrumbII current;
	local BreadcrumbII neighbor;
	local PriorityQueue openSet;
	local BreadcrumbList closedSet;
	local BreadcrumbList curList;
	local BreadcrumbList iter;
	local BreadcrumbList Result;
	local BreadcrumbLinkMap cameFrom;
	
	dCosts = Spawn(class'BreadCrumbMap');
	rCosts = Spawn(class'BreadCrumbMap');
	costs = rCosts;
	
	dCosts.Set(self, 0);
	rCosts.Set(self, CostFor(Destination, dCosts, rCosts));
	cameFrom.Set(self, none);
	
	current = self;
	
	while ( current != none )
	{
		curList = current.CrumbLinks();
		iter = curList;
		
		while ( iter != none && iter.Iterate(curList, neighbor) )
		{
			if ( closedSet.HasCrumb(neighbor) )
				continue;
				
			cameFrom.Set(neighbor, current);
				
			if ( neighbor == Destination )
				break;
				
			closedSet.Insert(neighbor);
			openSet.Insert(current.CostFor(neighbor, dCosts, rCosts), neighbor);
		}
		
		if ( curList != none ) curList.Destroy();
		
		current = openSet.Poll();
	}
	
	for ( current = Destination; current != none; current = cameFrom.Get(current) )
		Result.Insert(current);
		
	return Result;
}

defaultproperties
{
	DistanceFactor=1
	HeuristicFactor=1
}

BreadcrumbLinkMap.uc

class BreadcrumbLinkMap extends Actor;

var	BreadcrumbII		QCrumb;
var	BreadcrumbII    	QData;
var	BreadcrumbLinkMap	nextMap;

function Set(BreadcrumbII key, BreadcrumbII value)
{
	local BreadcrumbLinkMap map;

	for ( map = self; map != none; map = map.nextMap )
		if ( map.QCrumb == key )
		{
			map.QData = value;
			
			return;
		}

	if ( QCrumb != none )
	{
		if ( nextMap != none )
			nextMap.Set(key, value);
		
		else
		{
			nextMap = Spawn(class'BreadcrumbLinkMap', self);
			nextMap.QCrumb = key;
			nextMap.QData = value;
		}
		
		return;
	}
	
	QCrumb = key;
	QData = value;
}

function BreadcrumbII Get(BreadcrumbII key)
{
	local BreadcrumbLinkMap map;

	for ( map = self; map != none; map = map.nextMap )
		if ( map.QCrumb == key )
			return map.QData;
			
	return none;
}

BreadcrumbList.uc

class BreadcrumbList extends Actor;

var	BreadcrumbII	myCrumb;
var BreadcrumbList	nextList;

function Insert(BreadcrumbII other)
{
	if ( myCrumb == none )
		myCrumb = other;
		
	else
	{
		nextList = Spawn(class'BreadcrumbList', self);
		nextList.myCrumb = other;
	}
}

function bool HasCrumb(BreadcrumbII other)
{
	local BreadcrumbList l;
	
	for ( l = self; l != none; l = l.nextList )
		if ( l.myCrumb == other ) return true;
			
	return false;
}

function bool Iterate(out BreadcrumbList repeater, out BreadcrumbII crumb)
{
	if ( myCrumb == none )
		return false;

	crumb = myCrumb;
	repeater = nextList;
	
	return true;
}

defaultproperties
{
}

BreadcrumbMap.uc

class BreadcrumbMap extends Actor;

var	BreadcrumbII	QCrumb;
var	float			QData;
var	BreadcrumbMap	nextMap;

function Set(BreadcrumbII key, float value)
{
	local BreadcrumbMap map;

	for ( map = self; map != none; map = map.nextMap )
		if ( map.QCrumb == key )
		{
			map.QData = value;
			
			return;
		}

	if ( QCrumb != none )
	{
		if ( nextMap != none )
			nextMap.Set(key, value);
		
		else
		{
			nextMap = Spawn(class'BreadcrumbMap', self);
			nextMap.QCrumb = key;
			nextMap.QData = value;
		}
		
		return;
	}
	
	QCrumb = key;
	QData = value;
}

function bool Get(BreadcrumbII key, out float res)
{
	local BreadcrumbMap map;

	for ( map = self; map != none; map = map.nextMap )
		if ( map.QCrumb == key )
		{
			res = map.QData;
			return true;
		}
			
	return false;
}

defaultproperties
{
}

PriorityQueue.uc

class PriorityQueue extends Actor;

var	float			QCost;
var	BreadcrumbII	QData;
var	bool			bOccupied;
var	bool			bUsedUp;
var	PriorityQueue	nextQueue;

function bool InsertHere(float cost, BreadcrumbII data)
{
	local PriorityQueue exNext;

	if ( bOccupied )
	{
		if ( nextQueue != none )
			exNext = nextQueue;
	
		nextQueue = Spawn(class'PriorityQueue', self);
		nextQueue.insert(cost, data);
		
		if ( exNext != none )
			nextQueue.nextQueue = exNext;
	}
	
	else
	{
		QCost = cost;
		QData = data;
		
		bOccupied = true;
		
		return false;
	}
	
	return true;
}

function Insert(float cost, BreadcrumbII data)
{
	local PriorityQueue current;
	local PriorityQueue previous;
	
	for ( current = self; current != none && current.QCost <= cost; current = current.nextQueue )
		previous = current;
		
	while ( previous.bUsedUp )
		previous = previous.nextQueue;
		
	previous.InsertHere(cost, data);
}

function BreadcrumbII Poll()
{
	local PriorityQueue q;

	if ( bUsedUp )
	{
		for ( q = self; q != none; q = q.nextQueue )
			if ( q.bOccupied && !q.bUsedUp )
				return q.Poll();
		
		return none;
	}

	bUsedUp = true;
	
	return QData;
}

function int Length()
{
	local PriorityQueue current;
	local int res;
	
	res = 0;
	
	for ( current = self; current != none; current = current.nextQueue )
		if ( !current.bUsedUp )
			res += 1;
		
	return res;
}

defaultproperties
{
}