NaughtScape[08] - AStar Pathfinding Prep; nodes, edges, and graphs.
NaughtScape is a project I am undertaking to create a small game mimicking the look and mechanics of Old School RuneScape. I started this project to help myself learn some Unity game programming and also some 3D modelling. The first seven entries in this blog were posted to Steemit, and can be found through my profile: @maple-thunder.
Since my last post I've put many hours into implementing a pathfinding system for the player (and the enemies in the future). It took me a while to get the underlying code structure for the pathfinding grid.
For the pathfinding to work I had to create a map of the walkable tiles, and the cost to move from each tile into it's neighbours. To achieve this I created 3 classes:
- Path_Node
- Path_Edge
- Path_TileGraph
Nodes and Edges
The Path_Node class is very simple because all it has to hold is reference to the data (Tile) that it represents, and an array of Path_Edges that lead into neighbouring nodes. The Path_Edge class is equally as simple only needing to contain a float to represent the cost of traversing this edge, or the cost to enter the node this edge leads into. The other thing the edge has is a reference to the node it leads to.
Both classes are made generic by adding the <T> where you would normally add a type.
Both of these classes were written to be generic and possibly work with various types of objects. Because I was using them with my Tile class I named the graph class Path_TileGraph. This is where the generic classes get instantiated with the Tile type.
Creating the Tile Graph
To start creating the graph I needed a couple things. First was a Dictionary<Tile, Path_Node<Tile>> so I could easily get a node from a supplied tile, second was an array of the tiles in the world. I grabbed an array of the tiles directly from the world, and looped through them. For each tile I checked it's movement cost, and if the movement cost was above 0 a new Path_Node was created and added to the nodes dictionary.
The movement cost was a small function I wrote inside the Tile class. This would effect the pathfinding more if I made this cost change based on how difficult the terrain was to cross. I chose to have tiles be pathable or not so the movement cost will only ever be 0 or 1.
Once the nodes dictionary contains a node for each walkable tile, I loop through the dictionary and grab the neighbours of each tile with a GetNeighbours function. This is just a public accessor for the _neighbours variable in the Tile which is set with a SetNeighbours function.
SetNeighbours defaults to allowing diagonal movement, but that can be altered if desired.
When I had the neighbours I added them, and their movement cost, one by one into a new Path_Edge object. This edge got added to the Path_Node's edges array.
Finding the Right Path
At this point I had the entire walkable tile graph generated. Now I just had to create the Path_AStar class to implement the AStar method of pathfinding.
Path_AStar was responsible for finding a path between the player's current tile position, and one that was clicked on. This was achieved by adding a SetPath function to my PlayerController which took in a Tile as a parameter. Then SetPath instantiated a new Path_AStar object.
The destination tile was passed in from the MouseController on a left click.
Path_AStar requires 3 parameters in it's constructor:
- The WorldData for the world
- The current tile the player is in
- The destination tile
The WorldData was used to retrieve the tile graph dictionary of path nodes that was just created. I used this dictionary to get the path node for both the start and end tiles so I had my beginning and end nodes. Next up was creating a List to hold the nodes after they have been checked (ClosedSet), a SimplePriorityQueue to hold the nodes waiting to be checked (OpenSet), and a dictionary of path node to path node to keep track of which tile you entered a given tile from (Came_From).
The SimplePriorityQueue is a library I imported from BlueRaja's GitHub. I needed this because a generic Queue class adds all new entries to the bottom, but I needed to be able to add nodes that could have a higher or lower importance depending on it's distance from the goal.
There were two other major dictionaries that I needed to instantiate, both were dictionaries of a Path_Node<Tile>> to a float. Once I instantiated each list, I looped through them is set the default value for each to infinity.
The g_score represents the total movement cost to get to the node from the start, and the f_score represents the estimated total cost of the path if you traverse through this node.
I create a while loop that will terminate when there are no nodes in the OpenSet. Inside the loop I Dequeued the first node from the OpenSet, which was the node with the lowest f_score, removing it from OpenSet.
Before I dealt with the ClosedSet, I did a quick check to see if the current node is the goal node. If it was I called reconstruct_path and passed in the Came_From dictionary and the current tile (which is the goal tile). If it wasn't I added the current node to the ClosedSet to label it as checked.
Checking Neighbouring Nodes
Once the current node was added to the ClosedSet I looped through each of the edges attached to the node. These led to any tile that the player can path to from the current tile. I used the edge's reference to the neighbouring node to check and see if the neighbouring node was in the ClosedSet already. If it was I continued into the next operation, skipping the rest of the loop.
If the neighbouring node was not in the ClosedSet, I calculated it's tentative_g_score. This was the g_score for the neighbouring node if the player took the current best path to the current location and then moved into the neighbouring tile. Then I checked to see if the neighbouring tile had already been added to the OpenSet and it's current g_score is lower than the tentative_g_score. If both are true it meant that the node was both waiting to be checked and it had a better path to it already set, so I continued on to the next iteration.
If the neighbouring tile was in the OpenSet but the tentative_g_score was lower than the stored g_score, or the neighbouring tile was not in the OpenSet yet, I set the values for the neighbouring tile in the g_score, f_score, and Came_From dictionaries. Then if the OpenSet didn't include the neighbouring tile, I added it with it's f_score as the priority.
Setting the Path
Once I found my way to the goal tile it was time to construct and save the path. I wrote a small function to do this for me using the Came_From dictionary.
In reconstruct_path I created a new Queue<Tile> called total_path and added the current tile to the queue. The I looped through the Came_From dictionary using a while loop that takes Came_From.ContainsKey(current) as it's condition. Because the key in the dictionary is the node in the path that leads to the current node, the only node without an entry will be the starting tile of the path. So when the starting tile is reached, Came_From.ContainsKey(current) will return false and the loop will be broken.
I then returned the reverse of total_path because it was build from end to start.
Structure Complete
Now that the main structure for the pathfinding is complete I just need to make sure everything is called where it needs to be, then put out fires and fix some bugs. I'm going end this post here, and in the next one I will talk about how I connected the pathfinding in with the player !
Until Next Time !
If you have any suggestions for improvements, questions, or links to resources that would help me out feel free to leave a comment. I am using Unity as a game engine and Blender for any 3D modeling I may have to do during this project. Upvote if you liked the post or found it helpful, and follow me for future updates on NaughtScape, sometimes other programming, and occasionally other stuff. All of the source code can be found on my Github.
You could also add me in game on OSRS if you play !
My ign is MapleThunder.