Darryl Long

This week was extremely busy and I didn’t quite get everything that I wanted, done however it was still quite a productive week. This week’s focus is mainly around pathfinding and implementing it into the Creature Feature project and IRNTJ lion.

Pathfinding

Pathfinding, there is quite a lot of work and detail under the surface when it comes to pathfinding. There are two main requirements when it comes to pathfinding the first of which is path data or world data, this is the data of the areas where the agent is able to traverse. This data is required in order to build an appropriate node map to work out traversable areas for the agent. There are multiple ways to map out an area, spatial graphing is an option and so is navigational meshes, these both create nodes that the pathfinding algorithm can use to work out a path. Nodes are points within the map, nodes also contain a number of edges, and edge denotes a traversable path in which the agent may move from one node to the next node. By graphing out and creating a node map, this data can then be used to figure out where the agent is able to move and can be used in an algorithm.

The second step to pathfinding is to use a pathfinding algorithm to work out the fastest path to the objective, there are multiple algorithms that can be used:

• Depth-First Search – Searches to the deepest node first and checks throughout whether this is the optimal path.
• Breadth-First Search – Searches all of the first connecting nodes first and then the second and so forth.
• Dijkstra – Searches the unvisited node with the lowest cost first and then checks it’s neighbours.
• A* – This algorithm is similar to Dijkstra but adds a heuristic distance value from the objective where it is weighted more heavily, it is known as a guided search. This is the standard that is used in most games as it is fairly efficient.

For a visual representation of the algorithms, it can be found here.

After figuring out which pathfinding algorithm to use, the next big step was to implement it into the game. At each vertex where a tree was being placed during the procedural generation mentioned in the last blog, I also created a node. Additionally, I also created edges for the nodes connecting it in all four binary directions, this created a simple node grid map. Using this node grid map I applied the pathfinding algorithm to create a list of nodes that would lead the agent from one location to the final location. A pseudocode implementation of A* can be seen below, additionally, a good explanation of the implementation can be found here.

I managed to get the pathfinding working and the agent was able to create find a path to a point unless it was not a traversable area. However, I found that the movement felt extremely rigid and unnatural and wanted to improve on that fact, an easy fix to this was to add diagonal edges that connected the nodes, this meant that the agent was no longer only turning at 90-degree angles and it made the movement look far more natural, this still has room for improvement however.

Another error I had was that the agent was only able to pathfind once and the second attempt was breaking the code. I later found that this was due to the fact that when grabbing the edges I created a temporary node list, but it was still referencing the original node list and so deleting the nodes from the list removed them from the original.

IRNTJ – Lion

After figuring out all the necessary requirements for pathfinding I was able to implement pathfinding in one of my games, I Really Need This Job. Pathfinding was required for our sleeping lion trap, where if the player goes too close to the lion it will wake the lion. When the lion wakes it chases the player and kills the player if it comes into contact with it.