Pathfinding - A* | Theta*

Path-finding was obviously going to be an important of Zity as most of the NPC creatures would need to be able to get places in a non-linear fashion. For instance a zombie seeing the player through a window will need a way to get to the player besides just running at the window. To accomplish this I looked at many different path-finding solutions, ideas, and methods and settled on Theta* (A variant of A*).

Path-finding - An overview

In video-games a common scenario involves an NPC trying to get to the player whilst avoiding obstacles. While things like (steering behaviors) allow characters to dynamically avoid obstacles, sometimes we need characters to find a path through a maze, out of a building, or to a far away player. To accomplish this games use a method called path-finding which involves traversing a representation of the map in order to find the shortest path from start to goal.

Maps are typically represented by a bunch of polygons or sprites that draw the terrain. Then collision meshes and bounding boxes are used to check if things are hitting these maps. Path-finding unfortunately requires another representation of the map. Depending on the style and type of game the map representations can vary. Common representations are grids/graphs, way-points, navigation meshes, and visibility graphs. Each of these has pros and cons depending on each game's requirements. You can read an excellent article on map representations (and find more information about path-finding in general) (here).

Once the representation is implemented you then need a method of finding paths on it. There are many different algorithms and variations on them to choose from but the most common is A* (A star). A* merges together two other techniques to find paths to create a very fast, and accurate path-finder.

A*

There's a lot I could cover about A* but I'm going to very quickly go over it's implementation. A* works by estimating a nodes distance to the goal node and adding that to how far the node has come from the starting node. These two values are H (distance to goal) and G (distance from start). One other value is F (H and G combined) which is used to determine the likelihood that the node will lead to the goal. Every node keeps track of it's G and F values and the node it came from.

A* also uses two lists. One is the Open list which keeps track of all the nodes we have yet to expand. The other is the closed list which keeps track of the nodes we have expanded already. An important note is that the Open list sorts the nodes by their F values so that the highest (best) F value is at the front.

A* basically works as follow:
Start by adding all the neighbors of the start node to the Open list. To do this you get the neighbors from the Graph, calculate how far each node is from the starting node (G - usually 1), and how far the node probably is from the goal node (H) and add them together and store F and G. Also set each neighbor node's Parent to the starting node.

Now you have some number of nodes in the Open list sorted by their likelihood of leading to the goal node. You take the best one out of the Open list and basically repeat what you did with the starting node - Expand it's neighbors and set their values. You then put the node in the closed list since it's been traversed already.

Now eventually you will get to the point where the node you take out of the Open list if the goal node. Once you get here you can stop and create the path by starting from the ending node and adding the Parent of it, and it's Parent, and it's Parent and so on until you get back to the starting node.

There's a lot more to A* then this and I encourage anyone who is interested to check out (this) for a very well done article on how it works and how to implement it.

Theta* 

 Now A* is great for finding a path from node to node to node until you reach the goal, but in most cases this results in weird looking movement for NPCs. What I found when trying to path-find on a grid/graph is that the paths would be very choppy and jagged. Now there are many ways to smooth the paths found by A* to help reduce the jaggedness but these often times don't result in shortest paths and can also seem weird. Take a look at (this article) for an introduction/implementation of Theta* which addresses the problems with A*.

Theta* finds paths that are smoother and better than A* at much the same speed and memory cost. It does this by using line of sight checks from expanded nodes to parent nodes to see if the path could be shorter. By doing this in the finding stage instead of after a path has been found Theta* finds the shortest, straightest paths.

Zity

What would be the point if I didn't talk about Zity. I've been working on rewriting my NPC code to make it more component based and easily maintainable. It has been hard. I've started by working on my Zombie class and abstracting the rendering, physics, and AI elements to separate objects that can be added to any NPC object as components. Hopefully this will help reduce messiness and let me alter small sections of code easily instead of hunting all over. As I was doing this I realized I needed to work on how the zombies will go about path-finding and that's what resulted in this article. I implemented Theta* and find it works perfectly. Currently I'm working on a 'Incomplete/Local Information' version of Theta* that will accept input as to where the NPCs have already been. This will let them explore the map to try and get to locations instead of finding the perfect path instantly. You can read more about it in this question I posted (here).

Currently I'm working on zombie AI and path-finding and will post updates as that continues along.