FlashPunk Tutorial 05: A* Pathfinding for NPCs

Like this at Facebook! What’s up? The Pathfinding tutorial is! After a bunch of stuff keeping me from finishing it, I’ve finally made it. As announced in the previous post, the code is on GitHub from now on. You can get the entire source code in a nice zip or tar archive over here. I’ve tried to make the code as easy to understand as possible, because I simply don’t have the time nor nerve to explain every single line there is. Instead, I’ll focus on explaining the logic of the code as easily to understand as possible, and only refer to actual code when it’s really important. You are really going to need to get the code, Alt+Tab between this tutorial and the code I’m referring to pretty much all the time. The screenshots of code I’m showing here are only telling you part of the story. Apart from the pathfinding code, there are several other bigger changes made to the code ever since tutorial number 4. Major additions are:

  • NPCs and their pathfinding code
  • A clock that continuously ticks and a display for the time
  • A text area that displays the current location of the player
  • Map data, player data and NPC data is loaded from xml in contrast to hardcoded data

You can try the SWF directly here.

The code for displaying text is rather simple, and shouldn’t need much explanation. I think you’ll be able figure it out by looking at the loadMap() function of Game.as and then looking up the DisplayText class. This seems to not work with FlashPunk 1.4 though, so until I fix this issue with the new version, this code is going to stay on FP1.3.
The xml data is loaded in the DataLoader class which initiates the npc, map and player entities in the constructor function of Game.as. Okay, now that I’m done with the pre-stuff, let’s talk about pathfinding, and in particular A* pathfinding. I’ve learned how it works from this great article. Go and read it, it’s really well written.

Pathfinding Implementation
Done? Alright, I’m going to talk about how I implemented the code in the game. As you now know, in order to figure out a path, we first need to define clearly what a path is. It is the sequence of positions that leads from one position to an end position, where each position is connected to another and is reachable from there without an interruption. If there was an interruption, then it wouldn’t be a continous path. But in order to define what paths are, we need to define positions. As in the article, I’ve decided to divide the map area of each map into squares of 48×48 pixels. You can see in the Map.as class that I added a function that reads in the <solid> tag data from the oel given to the map upon creation. This lets the Map read in the data for its property gridSquares, which is an array of GridSquare objects. A GridSquare object has x and y properties for the location of the upper left corner, the index that stores its position in the gridSquares array and a flag “walkable” that let’s us know if this particular square is accessible for the player and NPCs. For example a square that happens to have a house on it would be “unwalkable”.

We create 2 Rectangle objects out of the current solid rect and gridSquare and then check if the intersects() function returns true, in which case the current gridSquare element does have an impassable collision area in it, so we better not risk making it accessible for NPCs. We set the walkable flag to false. So at this point, we have a gridSquares array with the map area information necessary to calculate paths for each map upon instantiation.
Next, we need to create a new datastructure that can store our A* node data, which are the various costs: movement cost, heuristic cost and full cost, a GridSquare object and the parent node. This datastructure is the Node.as class inside the utility folder inside the src folder. If you look at the NPC.as class, you can see that every NPC has a Pathfinder object called pathfinder. Another property of importance here is the path array. This array contains a sequence of points, which are moved towards in order each frame, if the current activity of the NPC is set to WALK. This is done by checking the currentActivity property each time update() runs, and then calling walkProcedure if the activity has the value of WALK. Look at walkProcedure(). We calculate the distance from the current position x and y to the point that the NPC is supposed to move towards, which is path[pathIndex]. If the distance is less than the minimum distance, we can say that the NPC is close enough to the point, so we want to iterate the pathIndex variable and go ahead towards the next point in path, using the movement() function, which simply determines if the NPC is too far to the right or left, or too far up or down, constantly updating the x and y positions. It also determines the animation to be played almost identical to the Player class. Nothing fancy here.

So as long as there is a next point in the path and the activity is set to WALK, our NPC is going to keep moving. The task of our pathfinder object is to calculate the points that have to be stored in the path array. We therefore call the pathfinding function with the current starting position, the end position where we want to go and the maps array. It is important to note that the pathfinder function can only figure out a path WITHIN a single map. For the inter-mapular (new term I coined :D) path finding, there is an extra class for that, which I’ll explain later.
Open the Pathfinder class. Look at the pathfinding() function first. It has the task to validate the parameters. If for example the endPoint received is in a square that is unwalkable, the pathfinding() method will return a null value. Further, since the parameters are Points, which means they only have x and y values, we first need to find out what grid squares they belong to. The grid square for the map is obtained by accessing the maps array parameter. You should realize that this maps array is the very same that is created in the Game.as class, so that means it contains all data for all maps in the game. This will most likely be a performance hog later on, getting passed around all the time, but for now I’m content with it.

After we have our startSquare and endSquare and it is established that the destination is walkable, we initiate the closedNodes and openNodes arrays. As you remember from reading the general article I linked you to, nodes are there to store the information that is of immediate concern when calculating a path. Closed nodes are those that we don’t want to visit again and open nodes are the ones we are going to consider storing next. The main function is findNextNode(), which is a half-assed recursive function. It is half-assed because it doesn’t construct its return variable recursively. The path array is a class property. This function is little more than a loop actually. But I find it more understandable in the recursive form.

The code of the findNextNode() function is fairly straight forward. We first check if the current node is the end node. If that is the case, we get out of the recursive loop. There is no return necessary, because the path array is charged before each call of findNextNode(). If the current node is not the end node, we create points for the 4 adjacent directions around our current square. I omitted the possibility for diagonal movement, because collisions might occur on the corners of the hitboxes. So to be on the safe side, I’ve commented the code that creates the diagonally accessible points. You can activate diagonal movement by uncommenting here.
We then loop through those points and break out of the current iteration if these conditions are met:
  1. The square that this point belongs to is not walkable
  2. The square that this point belongs to is not existent
  3. The node this point belongs to is a closed node
If none of these conditions are met, we add the node to the openNodes array, setting the cost and move on to the next. Setting the cost is done by calling the getHeuristicCost() method. This basically depends on the delta of x and y of the current square and the end square. It’s the same method of determining a “value” or “rating” of the square as described in the A* article. If you want to enable diagonal movement, you also have to uncomment the line 105. Once this loop is finished, we have the open nodes stored in the openNodes array. We just need to loop through it again and find the one with the lowest cost, and on the side, move all open nodes into the closedNodes array. This is different from the way described in the article, but I find it simpler this way and it might save some processing time, too.

So after the best node is pushed into the path array, the index of the current node inside the closedNodes array is passed to the findNextNode() function and called again.

Inter-Mapular pathfinding
Once all this is over, we return the path array in the pathfinding() method back to the NPC. Like this, we have implemented a pathfinding for NPCs that is limited to a single map. Let’s make NPCs move across maps. In order to do that, there are a bunch of preliminary things I need to talk about. To find a way across maps, we need a good way of storing map data. A relational mapping in a sense. That’s why the Map class has several new properties. There is an array called childMaps, an exits array and outsideMapIndex and a transitionPoints array. We need to differ also in outdoor and indoor maps. The way I defined the thing for now is that outdoor maps are maps that can have adjacent maps which are also of type outdoor that can be moved towards in one of the main directions north, east, south and west. Apart from that, outdoor maps can also have childMaps, which are basically always indoor maps. They can be dungeons, or houses etc. Transition points are instances of the new GlobalPosition class, which contains an x and y coordinate, but also a mapIndex property. It has 2 uses. If I need to know at what position I’m spawning when entering an indoors map, then the transition point of the indoors map tells me at what x and y that is, and the mapIndex stores from which map I came. When an NPC is leaving an indoors map for an outdoors map, then the transition point tells it to what map that door leads, and to which x and y the NPC must move to be able to leave. This introduces the notion of starting and exit points. NPCs can move across maps by going to an exit point, changing their currentMapIndex and spawning at the starting point of the next map, moving to the exit point inside that new map to get to another map or to the actual destination. Those startingPoint <-> exitPoint/endPoint paths are computed by the Pathfinder class. Let’s take a look at the general layout of our world. We have 2 outdoor maps, each with 3 child maps. The grassland has index 0, the earthland map has index 1. The first 3 children of the grassland map have indices 2, 3 and 4, whereas the child maps of the earthland map have indices 5,6 and 7. For an NPC to get from the middle house of the grassland map to the left house of the earthland map, the maps it must go by are: 3 -> 0 -> 1 -> 5.
That is called a map path. It’s like the pimp of the normal path. It owns it and tells it what to do.
This map path is computed in the MapPathfinder class, which employs a Depth-First-Search implementation. Depth-First-Search?! Yes, I’ll explain. DFS is a less sophisticated search method than A* in theory (which actually means the code is all the more complex). Since there is no unwalkable map for us right now, and since the general map structure is far far simpler than the gridSquares areas of single maps, I decided to use this approach. It works out for me. Basically what the pathfinding method of MapPathfinder does is it takes the maps array, the index of the starting and end map, and then returns the mapPath, like the one I told you about [3, 0, 1, 5]. We need an array that contains the indices of the visited maps, because once we tried going into a map and it turned out to not lead to the end map, we want to never go there again. Notice that I said “lead to”, not “is” the end map. The function is called determineMapPath() and is has more complicated code than the A* function earlier. It first checks if the current map is the one we’re looking for. If that is true, it pushes the index of the current map into the mapPath array, and also pushes it into the visited maps array. Then it returns true. WOOT? As with the normal Pathfinder, we want to store the mapPath inside a class scope array. But we also need to keep track of visited maps and need to cut any branch we’re following that doesn’t end in the map we’re searching for. Let’s do this in our heads right now: We’re in map with index 3, an indoors map. It isn’t the target map, which has index 5, so we get to the first condition. Is it an indoors map? Yes it is, so we check if it is the starting map index. Yup, so let’s push this map into the visitedMaps array. Then we call the function again with the index of the only map we can go from here. Only this time, we’re taking the return value and store it in “result”. If the branch leading from this exit leads to the destination, we’re going to push the current map index into the mapPath. If the result is false, then we return a false ourselves here.

Okay, we’re in map with index 0. It’s not the end map, and it’s not an indoors map, so we first check childMaps. We loop through the child maps, starting at the one with map index 2. Before that, we check if map 2 is visited already. If it isn’t (and it isn’t), then we again call this function with the map index 2. Okay, we’re in map of index 2, it’s not the end map, and it’s an indoors map. It isn’t the starting map, so the only possible result is that it’s a dead end. We mark this map as visited and return false. Back in the childMaps loop, we find out that this branch doesn’t lead anywhere, so we move on to map index 3. It is already visited, so we skip to map index 4. We go there and same story as with map index 2, it’s a dead end. Alright, we now loop through the possible exits. If the current exit in the loop is Map.NONE, it means there is no map in that direction. If there is, we check if it was visited before, which map of index 1 isn’t. We’re in map 1 and nope, it’s not the destination map, and it’s not an indoors map, so we check its childMaps. We move into the first child map which has index 5. There we find out that it is the destination map! We push the index into the mapPath, check it as visited and return true. Totally happy that we this branch was successful, map 1 now pushes itself into the mapPath too, and reports true back to map 0. There, map 0 gets excited as well and pushes itself into the mapPath and returns true to map 3. Map 3 is the one where we started out, and there we push 3 into the mapPath and finally move out of the function. If you called a trace on mapPath right after this, you’d see that the mapPath is [5, 1, 0, 3] which is the order in which we inserted them. We basically went from destination to start. So, in order to return a proper mapPath to the NPC, we call reverse on the array.

In the NPC class, we are always going to first call the mapPathfinder’s pathfinding function and then the pathfinding function of pathfinder. In order to glue them together, mapPathfinder has the findNextExitPoint and determineNewStartingPosition functions, which have the task of spawning and setting destination points for the NPC to use A* pathfinding on.

Autonomous NPCs
One thing of importance is that we want our NPCs to move around independently from the player. They should do their thing regardless of the player’s actions, location and status. Of course, we can block them by standing in the way, and in the future maybe engage them in combat. But the general notion is that NPCs are as autonomous as possible. You’ll realize that NPCs have a currentMapIndex variable, and in the update() function we set the visibility and collidable properties according to the Game’s current map index, which is basically always the map the player is at and the map index of the NPC. This way, NPCs get the update() function called, because their always actors of the current stage, only sometimes their invisible and sometimes their not.

In the Game class’ update function, we receive an array from the timer that contains the new hour and minute values. This only returns those values if there is an actually new minute in the new frame. Every 12 frames one minute advances, so only 1 out of 12 times does this condition enter its code block. There we call the aiUpdate() function of the NPC, where we can check if the NPC has an “appointment” at the time. Appointments have their own class and they simply store a position and a time. For example, we defined in npc_data.xml that Zelda has to get to map index 5 at 6.30. So once it is 6.30, the whole pathfinding procedure kicks off.

So that basically sums up the way pathfinding works in my code. Of course, there is a lot more code I haven’t explained that also plays an important role in pathfinding, but it’s largely really all about datastructure management, and about connecting the different modules with each other.
I hope this has been useful for you. This implementation is far from perfect as always, but I’m pretty proud of having come up with my own implementation without using a 3rd party one. If you have suggestions as to how to make this implementation faster/cleaner/simpler then let me know! If you have questions about certain parts of the code as it is in this snapshot, let me know as well, I’ll answer them. I’m going out of town for a week on Monday, so I’m not gonna be able to answer you at that time though.

email thispdfcut and reblogBookmark on deliciousShare on Facebooktwitterdigg thisGoogle BuzzYahoo BuzzBookmark on FriendfeedAdd this anywhere


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s