AI Pathfinding

I've had this code working for some time now, over 4 years to be exact. This bot navigation code is an enhanced version of the one I used in Spoonbot. The basic idea is also the same: The bot is fully scripted, waypoints are represented by coordinate entries in an array, instead of real objects on the map.

Why use an array and not mission-editor aware objects? Well first this would be an overhead. Second, it's simpler this way. And third, you can have the waypoints in a separate file, without touching the mission file.

How do you use this code? Ok first a few variables I use in my game:
$enableMissionTasks should be set to 1 during a game round. We have a BF1942-like "Conquest" mode, so this is how we know that we're actually playing.
$localClient should be set to the local client's ID. Go look into player.cs or game.cs and make sure that this variable exists after the first (local) client has joined. When you load up a map, you'll see "CADD: 1234" somewhere in the console, that's your own client id. The code needs your cliend id for waypoint editing. Once you spawn and start the waypoint placement with "WAY_StartAutoWaypoint();", it will watch your movements.

Just go into common/server/clientConnection.cs, and look for this line:

echo("CADD: " @ %client @ " " @ %client.getAddress());

Right after that, add this block:

if ($localClientDefined != 1)
   {
   	$localClient = %client;
   	$localClientDefined = 1;
   }
   $latestClient = %client;

You should also create a sound datablock called "PlaceWaypoint" - this is a sound that notifies you each time a waypoint has been placed. A good place for this is inside client/scripts/audioProfiles.cs:

new AudioProfile(PlaceWaypoint)
{
   filename = "~/data/sound/placeWaypoint.wav";
   description = "AudioGui";
   preload = true;
};

Here's a quick manual on how to create waypoints:
Load up your map, then drop to the console and type "WAY_StartAutoWaypoint();"
Run around the map. Listen for the waypoint placement sounds, you should try to run in straight lines between the each placed waypoint. The Auto-Waypointer will place waypoints automatically along the path you take. Try to visit many locations, walk around buildings, etc. - please don't walk "one-way-routes" such as jumping down a cliff, as the bots may end up trying to walk up the cliff...
It's VITAL that all your possible targets have at least one waypoint nearby, else the bots can't reach them (duh)

You can also map a keybind to WAY_AddWaypoint() so you can MANUALLY place waypoints at delicate locations such as mazes, corners... Note that you MUST leave the Auto-Waypoint-Generator on though, or else you will get broken paths.
When you're finished, call WAY_ProcessWaypoints()

Use WAY_Load() and WAY_Save() to load and save waypoint files.

Ok, but how do you get your bots to use the waypoints?
I suggest something like this in your AIPlayer.cs:

// Player reached destination waypoint, continue to next waypoint
// NOTE: This is called from C++ whenever a bot has reached it's moveDestination
//"%this" is the bot's "%player"
function Armor::onReachDestination(%this,%obj)
{
   if (%this.waypointsSet == true)
   {
	echo("[BOT] Next Waypoint in List:" SPC %this.nextWaypoint);
   	%next = %this.waypointList[%this.nextWaypoint];
	BOT_setNextWaypoint(%this, %next);
	%this.nextWaypoint++;
	if (%this.nextWaypoint == (%this.numWaypoints))
	{
		BOT_clearWaypoints(%this);
		%this.setMoveSpeed(0.0);
	}
   }
   
}

Now all you need is to call BOT_findPath(%bot, %targetLocation), and the bot will automatically start to head towards the target location using the waypoints. Again, the target location should be near a waypoint, or it won't work. Even though this code is scripted, it's more than capable of providing navigation support for 20-30 bots without noticeable framerate drops.
A last word of warning: While this code works perfectly, it's just navigation code - not a complete bot. It's your responsibility to keep your bot's CPU usage low. One word of advice: Split up the bot's thinking into a high- and a low-level part. Reschedule the low-level thinking (shoot, engage targets of opportunity) every 100-200ms, and the high-level stuff (objectives, which mission goal to go after) every 3-5 seconds.







Now, here's the file "botWayfinding.cs" which contains all the magic:

//****************************************************************************
// ILLUMIBOT - The AI for ILLUMINA
// Wayfinding code
// $Revision: 1.4 $
//
// (c) 2003 Single Cell Development
// http://www.totalren.com/scp
// ---------------------------------------------------
//
// $Log: botWayfinding.cs,v $
// Revision 1.4  2003/02/04 21:15:32  werewolf
// bots now capture objectives correctly
//
// Revision 1.3  2003/02/03 20:20:49  werewolf
// added waypoints for Kheb, added waypoint placement sound
//
// Revision 1.2  2003/02/01 22:24:29  werewolf
// Bots make their first steps! Waypoint navigation works!
//
// Revision 1.1  2003/02/01 17:09:57  werewolf
// Added first version of bot wayfinding code. Automatic waypoint generation works!
//
//
//
//****************************************************************************

$MaxWaypointDistance = 50;


//Find a path from current location to a specified location
//"%this" is the bot's "%player"
function BOT_findPath(%this, %targetPosition)
{
        echo("[BOT] Searching for path to " SPC %targetPosition);
	if (%this.waypointsSet == false)
	{
           BOT_clearWaypoints(%this);
           WAY_GetMeToPos(%this, %targetPosition, true);
           if (%this.numWaypoints > 0)
	      BOT_setNextWaypoint(%this, %this.waypointList[0]);
	}
	else
	{
           echo("[BOT] Already have a path to" SPC %targetPosition SPC "!");
	}
	%this.waypointsSet = true;
	return (0);
}

//"%this" is the bot's "%player"
function BOT_setNextWaypoint(%this, %position)
{
	%this.setMoveDestination(%position);
	%this.setAimLocation(%position);
	%this.setMoveSpeed(1.0);
}

//"%this" is the bot's "%player"
function BOT_addWaypoint(%this, %position)
{
	echo("[BOT] addWaypoint at" SPC %position);
	%this.waypointList[%this.numWaypoints] = %position;
	%this.numWaypoints++;
}

//"%this" is the bot's "%player"
function BOT_clearWaypoints(%this)
{
	echo("[BOT] Waypoints cleared");
	%this.numWaypoints = 0;
	%this.nextWaypoint = 1;
	%this.waypointsSet = false;
}


// Find the path from point1 to point2
function WAY_FindPath(%Point1, %Point2)
{
        if (%point1 == %point2) return (%point1);

        %cashpath = $BT::CACHE[%Point1, %Point2];
        if ((%cashpath != -1) && (%cashpath !$= ""))
        {
          return (%cashpath);
        }

        %PointString = %Point2;
        %Used[%Point2] = true;
        %found=false;

        for (%PointIndex=0;%found==false; %PointIndex++)
        {
                %LookupPoint = getWord(%PointString, %PointIndex);
                if  ((%LookupPoint == -1) || (%LookupPoint $= ""))
                {
                  break;
                }

                %TempString = $B::R[%LookupPoint];
                for (%PointNumber=0; %found==false; %PointNumber++)
                {
                        %Point = GetWord(%TempString,%PointNumber);

                        if ((%Point == -1) || (%Point $= ""))
                        {
                          break;
                        }
                        if (%Used[%Point] $= "")
                        {
                                %Parent[%Point] = %LookupPoint;
                                %Used[%Point] = true;
                                %PointString = %PointString @ " " @ %Point;
                                if (%Point == %Point1){ %found = true;}
                        }
                }
        }

        %path = %Point1;
        %Point = %Point1;
	$LastNumPoints = 0;
        for (%nI =0; (%nI < 80) && (%Point !$=""); %nI++)
        {
                %Point = %Parent[%Point];
                %path = %path @ " " @ %Point;
		$LastNumPoints++;
        }
        $BT::CACHE[%Point1, %Point2] = %path;
        return (%path);
}


function WAY_GetMeToPos(%botplayer, %Pos, %goToTargetCoordinates)
{
	echo ("Looking for a waypoint near the target:" SPC %Pos);
	%TargetWPT = WAY_FindNearestWPTbyPos(%Pos);
	echo ("Looking for a waypoint near the player:" SPC %botplayer.getPosition());
	%NearestWPT = WAY_FindNearestWPTbyPos(%botplayer.getPosition());
	if (%TargetWpt == %NearestWpt)
	{
		BOT_addWaypoint(%botplayer, $B::W[%NearestWpt]);
		if (%goToTargetCoordinates)
			BOT_addWaypoint(%botplayer, %Pos);
		return true;
	}
	
	%tempPath = WAY_FindPath(%NearestWPT, %TargetWPT);
	BOT_clearWaypoints(%botplayer);
	if ($LastNumPoints > 0)
	{
		for(%x = 0; %x < $LastNumPoints; %x++)
		{
			%Point = getWord(%tempPath, %x);
			%Location = $B::W[%Point];
			BOT_addWaypoint(%botplayer, %Location);
		}
		if (%goToTargetCoordinates)
			BOT_addWaypoint(%botplayer, %Pos);
		
		return true;
	}
	else if ($LastNumPoints==0)
	{
		echo("Can't get " @ %botplayer @ " to " @ %pos );
		return false;
	}
}




function WAY_CalculateRouteDistance(%Start,%Finish)
{
	%StartPos = $B::W[%Start];
	%FinishPos = $B::W[%Finish];
	%Route = $B::R[%Start,%Finish];
	%HopCount = getWordCount(%Route) - 1;


	if(%Route $= "n")
		%Distance = 99999999;

	else if (%Route $= "")
		%Distance = VectorDist(%StartPos,%FinishPos);

	else
	{
		%Distance = VectorDist(%StartPos,$B::W[getWord(%Route,0)]);

		for(%x = 0; %x < %HopCount; %x++)
			%Distance = %Distance +
					VectorDist($B::W[getWord(%Route,%x)],$B::W[getWord(%Route,%x+1)]);

		%Distance = %Distance + VectorDist(%EndPos,$B::W[getWord(%Route,%HopCount)]);
	}

	return %Distance;
}

function WAY_Save()
{
	%Filename = $Server::MissionFile @ ".bot";
	export("$B::*", %Filename, false);
}

function WAY_Load()
{
	WAY_Reset();
	%Filename = $Server::MissionFile @ ".bot";
	exec(%Filename);
	echo("Loaded" SPC $B::Count SPC "Waypoints");
}

function WAY_Reset()
{
	deleteVariables("$B::*");
	deleteVariables("$BT::*");
	$B::Version = 1;		// Version of the waypoint data format
	$B::Count = 0;			// Number of waypoints
	$B::Count_Calculated = 0;	// How many waypoints have been processed
//	$B::W[0] = "0.0 0.0 0.0";	// A Waypoint
//	$B::R[0] = "0";			// A Route
	$LastGoodPos = 0;
	$LastGoodLosView = "";
}

function WAY_ProcessWaypoints()
{
   for (%point1=0;%point1<$B::Count;%point1++)
   {
        %PointInfo = "";
        for (%point2=0 ;%point2<$B::Count;%point2++)
        {
            if (%point1 != %point2)
            {
                %los = false;
                %coord1 = $B::W[%point1];
                %coord2 = $B::W[%point2];

                if (WAY_CheckLOS(%coord1,%coord2,$MaxWaypointDistance))
                {
                  %PointInfo = %PointInfo @ %point2 @ " " ;
                }
            }
        }
   $B::R[%point1] = %PointInfo;
  }
  $B::Count_Calculated = $B::Count;
  WAY_Save();
}

function WAY_CheckLOS(%apos1,%apos2,%MaxDist)
{
	
	%pos1 = VectorAdd(%apos1, "0 0 2");
	%pos2 = VectorAdd(%apos2, "0 0 2");
	
	if(VectorDist(%pos1,%pos2) <= %MaxDist)
	{
	   %searchMasks = 
      		$TypeMasks::InteriorObjectType |  $TypeMasks::TerrainObjectType |
         	$TypeMasks::ForceFieldObjectType | $TypeMasks::VehicleObjectType;

	   //LOS check. The last variable makes the check ignore the own player, so we don't block our own LOS
	   %scanTarg = ContainerRayCast (%pos1, %pos2, %searchMasks, $localClient.player);

	   if (%scanTarg)
	   {
//		echo("Point" SPC %pos1 SPC "can NOT see point" SPC %pos2 SPC "due to" SPC %scanTarg.getClassName());
		return false;
	   }
	   else
	   {
//		echo("Point" SPC %pos1 SPC "CAN see point" SPC %pos2);
		return true;
	   }
	}
//	echo("Point" SPC %pos1 SPC "CAN NOT see point" SPC %pos2 SPC "due to distance" SPC VectorDist(%pos1,%pos2));
	return false;
}

function WAY_GetLosView(%pos)
{
	%Result = "";
	for(%x = 0; %x < $B::Count; %x++)
	{
	   if(($B::W[%x] != %pos) && (WAY_CheckLOS(%pos,$B::W[%x],$MaxWaypointDistance) == true))
	   {
//	      echo("Added" SPC %x SPC "to view");
	      %Result = %Result @ %x @ " ";
	   }
	}
	return %Result;
}

// Function to see if a point can see all points in list
function WAY_CanSeeAllLOS(%Point,%Points)
{
	%Result = true;
	%PointCount = getWordCount(%points);
	%Pos = $B::W[%Point];
	%Cansee = "";
	for(%x = 1; %x < %PointCount; %x++)
	{
		if ((%Point != getWord(%points,%x)) && (WAY_CheckLOS(%Pos,$B::W[getWord(%points,%x)],$MaxWaypointDistance) == false))
			%Result = false;
		else
			%cansee = %cansee @ getWord(%points,%x) @ " ";
	}
	return %Result;
}


function WAY_AddWaypoint(%id, %pos)
{
	%add_tp = -1;

	%minAdj = 99999;

	for(%x = 0; %x < $B::Count; %x++)
		if(VectorDist(%pos, $B::W[%x]) < 1)
			%add_tp = %x;

	if(%add_tp == -1)
	{
		$B::W[$B::Count] = %pos;
		echo("Added waypoint " @ $B::Count @ " at " @ %pos);
		echo("Point " @ $B::Count @ " can see " @ WAY_GetLosView(%pos));
		$B::Count++;
		WAY_Save();
		alxPlay("PlaceWaypoint");
   	}
}


// Removes waypoints if other's can already perform function.
function WAY_Optimise_Points()
{
	for(%x = 0; %x < $B::Count; %x++)
	{
		if($B::W[%x] !$= "")
		{
			%LosView = WAYGetLosView($B::W[%x]);
			%WordCount = BotThink::getWordCount(%LosView);
			%DeletePoint = false;
			for(%y = 0; ((%y < %WordCount) && (%DeletePoint == false)); %y++)
			{
				%Point = getWord(%LosView,%x);
			
				if(WAYCanSeeAllLOS(%Point,%LosView) == true)
				{
					%DeletePoint = true;
					echo(%x @ " redundant, " @ %Point @ " can see " @ %LosView);
					$B::W[%x] = "";
				}
			}
		}
	}
}

function WAY_FindNearestWPTbyPos(%PlayerPosition)
{
	%Nearest = -1;

//	%PlayerPosition = VectorAdd(%PlayerPosition,"0 0 2");

	%Distance = 999999;

	for(%x = 0; %x < $B::Count; %x++)
	{
		%WPTPosition = $B::W[%x];
		%NomDistance = VectorDist(%PlayerPosition, %WPTPosition);
		if ((%NomDistance < %Distance) && (WAY_CheckLOS(%PlayerPosition, %WPTPosition,20000) == true))
		{
			%Nearest = %x;
			%Distance = %NomDistance;
		}
	}
 
	$LosWarning=false;
	if (%Nearest != -1)
	{
		echo("Found an optimal nearest waypoint:" SPC %Nearest);
		return %Nearest;
	}
	else
	{
		$LosWarning=true;
		echo ("WARNING: WAY_FindNearestWPTbyPos can't find a waypoint with LOS!");
		return WAY_FindNearestWPTbyPosNOLOS(%PlayerPosition);
	} 
}

//Same as above, but without LOS check!
function WAY_FindNearestWPTbyPosNOLOS(%PlayerPosition)
{
	%Nearest = -1;
	%Distance = 999999;
	for(%x = 0; %x < $B::Count; %x++)
	{
		%WPTPosition = $B::W[%x];
		%NomDistance = VectorDist(%PlayerPosition, %WPTPosition);
		if (%NomDistance < %Distance)
		{
			%Nearest = %x;
			%Distance = %NomDistance;
		}
	}
	return %Nearest; 
}

function WAY_StartAutoWaypoint()
{
	%id = $localClient.player;
	echo("Starting auto waypoint generation for player" SPC %id);
	WAY_AddWaypoint(%id,%id.getPosition());
	WAY_AutoWaypoint(%id);
}

function WAY_AutoWaypoint(%id)
{
	cancel($autoWaypointTask);

        //Abort if we've left the mission
        if ($enableMissionTasks != 1)
          return;


	if($LastGoodPos == 0)
	{
		$LastGoodLosView = WAY_GetLosView(%id.getPosition());
		$LastGoodPos = %id.getPosition();
	}

// Get current position

	$CurrentPos = %id.getPosition();

	if($LastGoodPos != $CurrentPos)
	{
		$CurrentPos = %id.getPosition();
		$CurrentLosView = WAY_GetLosView($CurrentPos);
//		echo("LOS View:" SPC $CurrentLosView);
		
		if($CurrentLosView $= $LastGoodLosView)
		{
			$LastGoodPos = $CurrentPos;
			$LastGoodLosView = $CurrentLosView;
		}
		else
		{
			echo("Waypoint LOS situation changed!");
			// Lost contact with waypoints so add a new one at last good point.
			if ((getWordCount($CurrentLosView) == 0) &&
				(getWordCount($LastGoodLosView) > 0))
			{
				echo("Type 1: Added point at last good pos");
				WAY_AddWaypoint(%id, $LastGoodPos);
			}

// Gained contact with waypoints. Add waypoint at current position
// This happens when you switch teams. I always switch teams to map the other team's base, so this IS a common situation!
			else if((getWordCount($CurrentLosView) > 0) &&
				(getWordCount($LastGoodLosView) == 0))
			{
				
					WAY_AddWaypoint(%id,$CurrentPos);
					echo("Type 2: Added point at current pos");
			}

			$CurrentLosView = WAY_GetLosView($CurrentPos);
					
			$LastGoodPos = $CurrentPos;
			$LastGoodLosView = $CurrentLosView;

			echo("NewLastGoodLOS    = " @ $LastGoodLosView);
			echo("NewCurrentLOS = " @ $CurrentLosView);

		}
	}
	
	// Reschedule after a couple of  msecs!
	$autoWaypointTask = schedule(100, 0, "WAY_AutoWaypoint", %id);
}

Some explanations: The function WAY_ProcessWaypoints() calculates which waypoints can see each other. Each route entry usually contains the array-indices of two waypoints. The actual pathfinding codes goes through all route entries, and builds one long route. It's definitely possible to optimize this code by using a C-coded function that does the Djkistra-algorithm, but I'm just too lazy for that now. By the way, optimizing the ProcessWaypoints() function is obsolete: it only takes about 0.5 seconds for 80 waypoints on a 2.5GHz machine AND it's only to be called once, manually, after waypoint placement, so I'm satisfied ;)

The waypoints and routes are stored in a file that has the same filename as the mission + ".BOT"

Noticed the $BT::CACHE stuff? That's a special array that caches whole routes. If a bot ever has the same origin- and target-waypoint again, the complete route calculation is skipped and the already-calculated one is used! If you have MANY waypoints you may want to disable this feature for memory reasons. Usually it's absolutely no problem though, and I would keep it in if your waypoint files don't exceed 200-300 waypoints. You could also put a limit on how many routes can be cached to prevent too much memory usage.

Be careful if you mess with the LOS functions, or you might end up with broken routes, bots not finding any waypoints near their target, etc.

The Auto-Waypointer works by checking which nearby waypoints are visible at a regular interval. Everytime we loose or gain eye contact with a waypoint, it places a new one at the last good location. This works very well for corners and such, but I still manually place waypoints around tight corridors just to make sure. The manual placement of waypoints doesn't interfere with the automatic placement, don't worry.

That's it! I hope it's useful for your project, and stop by our site (www.illumina-game.com) sometime.