AI A* Pathfinding

From IrrWizard

Introduction

This short tutorial shows how you can implement A* pathfinding into your game. IrrWizard will automatically add this if you select the 'Full Framework' option.

A* Pathfinding

The following classes of interest are created when you choose the 'Full Framework' option while running IrrWizard.

• CGamePathManager
• CGamePather

The GamePathManager.cpp contains the code that implements the 'micropather' A* path finding algorithm.. (For more information on micropather, click here)

First off all we need to create a series of Nodes or waypoints around our game level map, this is called a NavGraph. This is just a list of irr::core::vector3df waypoints.

Each Node or waypoint has to also have a list of adjacent nodes or waypoints as well.

The following code represents the picture above. Create a new function CGamePlayState01::loadPathMap(pManager), and add the following code. (Call this from the Init() function)

pManager->getPathManager()->setWaypoint(irr::core::vector3df(0,0,0));	     // node 0
pManager->getPathManager()->setWaypoint(irr::core::vector3df(0,0,500));     // node 1
pManager->getPathManager()->setWaypoint(irr::core::vector3df(500, 0, 500)); // node 2
pManager->getPathManager()->setWaypoint(irr::core::vector3df(500, 0, 0));   // node 3	
pManager->getPathManager()->setWaypoint(irr::core::vector3df(1000, 0, 500));// node 4	
// setAdjacentNode(node, neighbour);
pManager->getPathManager()->setAdjacentNode(0, 1);
pManager->getPathManager()->setAdjacentNode(1, 0);
pManager->getPathManager()->setAdjacentNode(1, 2);
pManager->getPathManager()->setAdjacentNode(2, 1);
pManager->getPathManager()->setAdjacentNode(2, 3);
pManager->getPathManager()->setAdjacentNode(2, 4);
pManager->getPathManager()->setAdjacentNode(3, 2);
pManager->getPathManager()->setAdjacentNode(4, 2);

Without a dedicated tool that creates these Navagation maps (NavGraphs), the easiest way is to change your game to be windowed, and print the camera's x,y,z position in the title bar. Then you can move the camera to the position you want the node to be, then alt+tab into your IDE and enter the position.

Enter the following code into the Update() function of CGamePlayState:

////// DEBUG ONLY !!!!
core::stringw str = L"Debug - camera pos [";
str += (int)pManager->getSceneManager()->getActiveCamera()->getPosition().X;
str += "   ";
str += (int)pManager->getSceneManager()->getActiveCamera()->getPosition().Y;
str += "   ";
str += (int)pManager->getSceneManager()->getActiveCamera()->getPosition().Z;
str += "]";
pManager->getDevice()->setWindowCaption(str.c_str());
//////////////////////

Another good idea is to create a debug function that adds a TestSceneNode with a text label above, then you can visually see the nodes which helps with working out the adjacent nodes. This is how I created the nodes for 'map-20kdm2'

Create a new function the the CGamePlayState01 class, and then call that from the Init() function.

//// Node 00
scene::ISceneNode* node00 = pManager->getSceneManager()->addTestSceneNode(10);
node00->setPosition(pManager->getPathManager()->getWaypointAt(0));
pManager->getSceneManager()->addTextSceneNode(pManager->getGUIEnvironment()->
    getBuiltInFont(), L"node 00", video::SColor(255,255,0,0), node00);
...

Below is a picture of the nodes being displayed, the white box coming out of the enemy's chest is a node.

The code that calls the CGamePather is in the EntityStateRun of the CGAmeEnemyOwnedStates class. This provides AI game logic out of the box for you to use without worrying about creating your own. If you wanted it to behave in a slightly different mannor, then this is where you would change it.

A better way would be to create some more EntityStates, ie EntityStateSeek, EntitySateEvade and EntityStatePursue with logic to match instead of a generic EntityStateRun which Seeks and Pursues in one.

Now all that is left to do is add your Enemy. This is done in similar way as before, the only thing different is to set the position from the waypoint list.:

...
// get waypoint from node list in case it changes. you can specify a vector3df but make 
// sure its a avalid waypoint
enemyNode->setPosition(pManager->getPathManager()->getWaypointAt(2));
CGameEnemy enemy = new CGameEnemy(ENTITY_MERC);  // any unique ID
enemy->setSpeed(1500); // new parameter
enemy->setModel(enemyNode);
...
           

NavGraph XML

The NavGraph can be created externally by using an XML file.

Usage from within game level Init():

// AI Navagation Graph, try xml first then default back to code if not found
if (!pManager->getPathManager()->loadNavGraph("media/navGraph.xml")) 
  loadPathMap(pManager);  

example xml:

<Nodes value="NavGraph"> 
  <Node id="0" posX="0" posY="0" posZ="0"> 
    <AdjacentNode id="1" cost="1"/> 
  </Node> 
  <Node id="1" posX="0" posY="0" posZ="500"> 
    <AdjacentNode id="0" cost="1"/> 
    <AdjacentNode id="2" cost="1"/> 
  </Node> 
  <Node id="2" posX="500" posY="0" posZ="500"> 
    <AdjacentNode id="1" cost="1"/> 
    <AdjacentNode id="3" cost="1"/> 
    <AdjacentNode id="4" cost="1"/> 
  </Node> 
  <Node id="3" posX="500" posY="0" posZ="0"> 
    <AdjacentNode id="2" cost="1"/> 
  </Node>
  <Node id="4" posX="1000" posY="0" posZ="500"> 
    <AdjacentNode id="2" cost="1"/> 
  </Node>
</nodes>