Live script based pathfinding?
by Zod · in Technical Issues · 01/21/2007 (10:46 am) · 8 replies
I have a few functions that create a perfect grid of markers on terrain points. It is setup so that you enter the mision editor, type in the function name, it places the markers and then you can walk around pruning and adjusting their positions as needed. Once you have pruned, you call anotehr function which loops through all of the markers that are left and shoves their positions into an array and saves the array to a file. You can reload the markers into the mission from this array to do further adjustments as needed and resave. I have a function that will pick a random position from the array you could use as a random destination. I have another function that will pick a position from the array closest to a choosen position you could use as a starting point.
Now, this stuff was the easy part. The hard part I can't get my head around. Obviously we want to create a path from start to destination. Any help is appreciated and I am sure many would benifit from this. Here is what I have..
Create a grid of markers within mission area. Change %square multiplyer for more or less markers.
Continued..
Now, this stuff was the easy part. The hard part I can't get my head around. Obviously we want to create a path from start to destination. Any help is appreciated and I am sure many would benifit from this. Here is what I have..
Create a grid of markers within mission area. Change %square multiplyer for more or less markers.
function posFromTransform(%transform)
{
// the first three words of an object's transform are the object's position
%position = getWord(%transform, 0) SPC getWord(%transform, 1) SPC getWord(%transform, 2);
return %position;
}
function findNextGridPoint(%axis)
{
// Code: Martin "Founder" Hoover
// www.garagegames.com/my/home/view.profile.php?qid=5055
if(%axis == 0)
return 0;
%square = NameToID("MissionGroup/Terrain").squaresize * 8;
%axis = mFloor(%axis);
%remainder = %axis % %square;
if(%remainder >= (%square / 2))
{
while(%axis % %square != 0)
%axis++;
}
else
{
while(%axis % %square != 0)
%axis--;
}
return %axis;
}
function generateGridPointArray()
{
// Code: Martin "Founder" Hoover
// www.garagegames.com/my/home/view.profile.php?qid=5055
// "x x x x" (startPointX StartPointY WidthTotal heightTotal)
%area = NameToID("MissionGroup/MissionArea").area;
%square = NameToID("MissionGroup/Terrain").squaresize * 8;
%minX = getWord( %area, 0 );
%minY = getWord( %area, 1 );
%maxX = getWord( %area, 2 );
%maxY = getWord( %area, 3 );
%xStart = findNextGridPoint( %minX );
%yStart = findNextGridPoint( %minY );
%xEnd = findNextGridPoint( %xStart + %maxX );
%yEnd = findNextGridPoint( %yStart + %maxY );
// Create the group if it does not exist
%group = nameToId("MissionGroup/BotNavigation");
if(%group <= 0)
{
%group = new SimGroup("BotNavigation");
MissionGroup.add(%group);
}
for ( %x = %xStart; %x < %xEnd; %x+=%square )
{
for ( %y = %yStart; %y < %yEnd; %y+=%square )
{
%z = getTerrainHeight( %x SPC %y ) + 1.0; // Set above terrain 1 unit
%pos = %x SPC %y SPC %z;
%marker = MissionMarkerData::create("WayPointMarker"); // Less overhead then path markers
%marker.setTransform(%pos SPC "1 0 0 0");
%group.add(%marker);
}
}
}Continued..
About the author
#2
01/21/2007 (2:30 pm)
Zod, it seems like you already have all the functionality needed to create a path from start to finish. maybe you need to be more specific about the kind of functionality you're looking for.
#3
How I'm using the system right now. Also needs work ::onReachDestination
01/21/2007 (3:44 pm)
This function function AiPlayer::getNextNavPointis severely lacking. Bots will ping pong between the same two nodes for all eternity. It's needs some algorithm which I just can't grasp.
How I'm using the system right now. Also needs work ::onReachDestination
function AIPlayer::spawn(%name)
{
%spawnPoint = pickSpawnPoint();
// Create the Ai player object
%player = new AiPlayer() {
dataBlock = DemoPlayer;
path = "";
};
MissionCleanup.add(%player);
%player.setShapeName(%name);
%player.setTransform(%spawnPoint);
// Pick a random position from the Nav array
%player.destination = %player.getRandomNavEndPoint( %pos );
// Find the closest nav position to the bots current position and go there
%player.moveToPosition( %player.findClosestNavPoint( %pos ) );
return %player;
}
function DemoPlayer::onReachDestination(%this, %obj)
{
%pos = %obj.getNextNavPoint( posFromTransform( %obj.getTransform() ), %obj.destination );
if ( %pos != %obj.destination )
%obj.moveToPosition( %obj.findClosestNavPoint( %pos ) );
else
{
%pos = posFromTransform( %obj.getTransform() );
%obj.destination = %obj.getRandomNavEndPoint( %pos );
%obj.moveToPosition( %obj.findClosestNavPoint( %pos ) );
}
}
function AIPlayer::moveToPosition(%this, %pos)
{
//echo("\c5AIPlayer::moveToPosition(" SPC %this @", "@ %pos SPC ")");
if ( !isObject( %this ) || %this.getState() $= "Dead" )
return;
%this.setMoveDestination( %pos, 0 );
%this.setAimLocation( vectorAdd( %pos, "0 0 0.5" ) );
} 
#4
Dijkstra
AI Pathfinding
... you should be able to modify their A-star implementations to work with your node graph.
01/21/2007 (4:05 pm)
@Zod - Check out the these resources...Dijkstra
AI Pathfinding
... you should be able to modify their A-star implementations to work with your node graph.
#5
Thanks, but I had allready looked them over and decided they are actually no better then the paths used by stock TGE. They require you to manually place waypoints in the map one at a time so the script can connect the dots via raycasts and weight them while your walking around. I allready have the dots in mass and need them connected on the fly as needed. I think A-Star is probably what is needed as we have a destination and a distance to work with. But I am definitely not grasping this A-Star stuff :)
01/21/2007 (4:31 pm)
Tom,Thanks, but I had allready looked them over and decided they are actually no better then the paths used by stock TGE. They require you to manually place waypoints in the map one at a time so the script can connect the dots via raycasts and weight them while your walking around. I allready have the dots in mass and need them connected on the fly as needed. I think A-Star is probably what is needed as we have a destination and a distance to work with. But I am definitely not grasping this A-Star stuff :)
#6
01/21/2007 (4:54 pm)
@Zod - Ummm that was my point... you don't have to use their waypoints. Pull the A-star algorithm from one of those resources and add it to your code.
#7
01/21/2007 (5:55 pm)
Well the two resources are somewhat complex and the marker setup they used so very tangled into the script, pulling either apart doesn't seem reasonable. But I shall take a crack at the second one. The first one is definitely out of the question. Thanks. 
#8
That should give you a good idea how A* works. It's probably what you need if you already hav the node network laid out.
02/09/2007 (12:46 pm)
www.policyalmanac.org/games/aStarTutorial.htmThat should give you a good idea how A* works. It's probably what you need if you already hav the node network laid out.
Zod
function createArrayFromMarkers() { %mission = fileBase($Server::MissionFile); %path = filePath($Server::MissionFile); %group = nameToId("MissionGroup/BotNavigation"); for ( %i = 0; %i < %group.getCount(); %i++ ) { %marker = %group.getObject( %i ); $Nav::Position[%mission, %i] = posFromTransform(%marker.getTransform()); } $Nav::Count[%mission] = %i; export("$Nav::*", %path @ %mission @ ".nav", false); deleteVariables("$Nav::"); %group.delete(); }Load markers into mission group from the array
function createMarkersFromArray() { %mission = fileBase($Server::MissionFile); // Create the group if it does not exist %group = nameToId("MissionGroup/BotNavigation"); if(%group <= 0) { %group = new SimGroup("BotNavigation"); MissionGroup.add(%group); } for ( %i = 0; %i < $Nav::Count[%mission]; %i++ ) { %marker = MissionMarkerData::create("WayPointMarker"); %marker.setTransform($Nav::Position[%mission, %i] SPC "1 0 0 0"); %group.add(%marker); } deleteVariables("$Nav::"); }Grab a random position from the array
function AiPlayer::getRandomNavEndPoint(%this, %startPos) { //echo("\c5AiPlayer::getRandomNavEndPoint(" SPC %this @", "@ %startPos SPC ")"); %mission = fileBase($Server::MissionFile); //Send a random position from the array within the count %random = mFloor(getRandom(0, $Nav::Count[%mission])); %pos = $Nav::Position[%mission, %random]; if ( %pos !$= %startPos ) return $Nav::Position[%mission, %random]; else { error( "Somehow we were unable to find a Random Nav End Point for" SPC %this SPC "!" ); warn( "Possible infinate loop commencing!" ); %this.getRandomNavEndPoint( %startPos ); } }Grab a starting point from the array which is closest to our player and is within LOS
function AIPlayer::hasLOStoPosition(%bot, %endPos) { %startPos = posFromTransform(%bot.getTransform()); %mask = ( $TypeMasks::InteriorObjectType | $TypeMasks::StaticTSObjectType | $TypeMasks::ShapeBaseObjectType ); %scan = containerRayCast( %startPos, %endPos, %mask, %bot ); %result = firstWord( %scan ); if ( !%result ) return( true ); return( false ); } function AiPlayer::findClosestNavPoint(%this, %pos) { //echo("\c5AiPlayer::findClosestNavPoint(" SPC %this @", "@ %pos SPC ")"); %mission = fileBase($Server::MissionFile); //Define a reference distance, something high, it will be decremented in the following loop. %reference = 100000; //Now loop through the NavArray to find the closest position for ( %i = 0; %i < $Nav::Count[%mission]; %i++ ) { %navPos = $Nav::Position[%mission, %i]; // Make sure it's not the staring position if( %navPos $= %pos ) continue; // Make sure LOS isn't blocked if ( !%this.hasLOStoPosition( %navPos ) ) continue; %dist = vectorDist( %pos, %navPos ); //Change the reference distance to the position closer to our fed position. if ( %dist < %reference ) { %closest = %i; %reference = %dist; } } // If this returns NULL we're in trouble! if ( %closest !$= "" ) return $Nav::Position[%mission, %closest]; else error( "Somehow we were unable to find Closest Nav Point for" SPC %this SPC "!" ); }Obviously you would have to exe the .nav file with the .mis execution to work with the array. Simple check for file exist if then execute.
This is where I am trying to get the next node.
//Lets assume pos = bots position and end = goal function AiPlayer::getNextNavPoint(%this, %pos, %end) { //echo("\c5AiPlayer::getNextNavPoint(" SPC %this @", "@ %pos @", "@ %end SPC ")"); %mission = fileBase($Server::MissionFile); //How far do we have to travel? %reference = vectorDist( %pos, %end ); //Now loop through the NavArray for ( %i = 0; %i < $Nav::Count[%mission]; %i++ ) { %navPos = $Nav::Position[%mission, %i]; // Make sure it's not the staring position if( %navPos $= %pos ) continue; // Make sure LOS isn't blocked else don't use this one if ( !%this.hasLOStoPosition( %navPos ) ) continue; // Is this node further away from the end then where we are now? %dist = vectorDist( %navPos, %end ); if ( vectorDist( %navPos, %end ) > %reference ) continue; // Early out if ( %navPos $= %end ) return %navPos; if ( %dist < %reference ) { %closest = %i; %reference = %dist; } } //Return the new position or none :( if ( %closest !$= "" ) return $Nav::Position[%mission, %closest]; else return -1; }