In part 1 of the series we basically just laid down the details of graph search algorithms. In the process, hopefully we learned that they are not something to be feared and are in fact quite simple in most cases. With that out of the way we are all clear to start digging into the actual pathfinding.
There are many different strategies for handling pathfinding. We are only going to look at one of them here and we are going to do it from the perspective of a tilemap. There is absolutely no reason why the algorithm described in this post would not work for a non-tilemap environment. If you remember from part 1 graph search algorithms do not care at all what their nodes represent. We will be using a tilemap based level only because it is easier to explain and visualize.
Laying the Foundation
The graph search algorithm acts on a list of nodes and edges so our first step is to create a node list to feed it. We are going to start simple and build up from there. In the process of evolving our structures to meet the new complexity it will hopefully be evident how you can add any game specific traits as well in the same fashion. Let's jump right in and define our starting Node structure:
struct Node: int x int y Node edges
The general strategy here is that we are going to loop through all of our tiles and we will create Nodes for any tile that we can visit that is above a ground tile.
for y in range( 0, tilemap.height ) for x in range( 0, tilemap.width ) processTile( x, y ) def processTile( x, y ): // we want an empty (passable) tile with a non-passable tile below if not isTilePassable( x, y ) || isTilePassable( x, y + 1 ): return // we have a passable tile. create a Node for it node = Node( x, y ) // nodeList is our global list of all the Nodes that we create nodeList.add( node )
This post is written to be more algorithmic so some very simple methods will not be defined but they should be very easily implemented based on your own tilemap data structures. One such example would be the
isTilePassable used in the code above. It returns true if the tile can be passed or false if not.
Astute readers will notice straight away that the above code only checks for one empty tile with ground below. That is all well and good if all AI agents are only 1 tile high. In reality, that will not often be the case so lets expand our Node structure to be more flexible and account for agents of differing heights. While we are expanding the Node class there is one more bit of data that would be good to know for later: if this Node is the edge of a platform or not. We'll add an enum to account for this that will specify if we have a ledge node or not. A ledge is defined as the end of a solid platform that contains a passable tile to the side and a passable tile below the side tile.
enum NodeType: Walkway LedgeLeft LedgeRight LedgeBoth struct Node: int x int y // how much space above this tile do we have int clearance // what type of Node this is NodeType type Node edges
Every time we create a Node we will also want to give it a clearance so our Node constructor above should change to do this. We should also create a new method to set the NodeType:
node = Node( x, y, getClearanceForTile( x, y ) ) node.type = getNodeType( x, y ) def getNodeType( x, y ): // gather some data about the surrounding tiles var belowRightPassable = isTilePassable( x + 1, y + 1 ) var belowLeftPassable = isTilePassable( x - 1, y + 1 ) var rightPassable = isTilePassable( x + 1, y ) var leftPassable = isTilePassable( x - 1, y ) // if we have no passable tiles below right/left or no passable tiles right/left this is a walkway if( ( !belowRightPassable && !belowLeftPassable ) || ( !rightPassable && !leftPassable ) ) return NodeType.Walkway; if( !belowLeftPassable && leftPassable ) return NodeType.LedgeRight; if( !belowRightPassable && rightPassable ) return NodeType.LedgeLeft; if( belowRightPassable && belowLeftPassable && rightPassable && leftPassable ) return NodeType.LedgeBoth; return NodeType.Walkway;
At this point our nodeList should contain every node that is walkable and we have stored if it is a ledge. The following image illustrates visually what our nodeList looks like. Red depicts Walkways, blue Ledges and green LedgeBoth Nodes.
Processing the Nodes
Our Nodes are all just lonely islands right now. They have no edges connecting them and if we remember our graph search algorithm requires edges so that it can find a path between any two Nodes. Lets fix that and add edges to connect all our adjacent Nodes. We will need a couple more simple helper methods to keep the code clean. As above, these won't be specifically defined here for brevity and readability. The
getAdjacentNode fetches the Node to the right/left of the passed in Node.
foreach node in nodeList: leftNode = getAdjacentNode( node, -1 ) if leftNode is not null and node.clearance >= agentHeight: node.edges.add( leftNode ) rightNode = getAdjacentNode( node, 1 ) if rightNode is not null and node.clearance >= agentHeight: node.edges.add( rightNode )
Now we are getting somewhere! We now have a list of Nodes with edges present connecting the Nodes to all of their neighbors. The image below illustrates the edges with a dark red line.
We now have a good base to work with. We created Nodes for all of our walkable areas and connected them with edges. The Nodes can be passed to a graph search algorithm and it can provide a legit path for the agent to follow. As it stands now, that path would only be found if both the start and end points are on the same platform. Not very useful! This next step (connecting nodes between platforms) is where things get interesting.
In the next part we will delve into adding more complex edges. Instead of merely connecting two edges that are adjacent to each other we need to take into account how our agent can get from one platform to another.