Hey all! This is Northman from Nerd Kingdom here to share some AI bytes with you. Specifically I’d like to talk about Pathfinding and how it relates to TUG and our characters.
Pathfinding is the act of finding the best path between two points in the world. The key word there is “best”. The definition of best depends on the type of game you are making and the type of character you are trying to find a path for. I think a small thought experiment helps to clarify the set of problems pathfinding tries to solve:
Imagine a mountain goat and a human facing a mountain that extends as far to their left and right as their eyes can see. Directly in front of them is a door. On the door is a sign that reads: “Tunnel to the Other Side”. The human does not have any climbing gear and the mountain is far too steep to for the human to scale it without proper equipment. If both the human and the goat want to get to the other side of the mountain what do they do? The goat does not have hands to open doors nor the ability to read. However, the goat is a sure-footed climber and does not have any problem scaling the mountain so it goes on its goaty way over the top of the mountain. Conversely, the human does have hands and can read so they take the tunnel. The path the goat and the human found are both the best path they can muster by their definition of best even if they are both very different.
By Darklich14 (Own work) [CC BY 3.0 (http://creativecommons.org/licenses/by/3.0)], via Wikimedia Commons
*Insert funny remark about goats here.*
“Ropes? We don’t need no stinkin’ ropes!”
So now that we have defined Pathfinding and talked about what “best” means we can look at what tools we have for finding paths. Most pathfinding techniques break up the world into spatial subsections (nodes) and store information about how those nodes are connected (edges). In Computer Science we call a set of nodes and edges a “graph”. Graphs are cool because they have been studied by mathematicians since the 18th century (check out the Seven Bridges of Königsberg). What this means to us is there are well known techniques, also known as algorithms, for dealing with graphs and finding best paths on them (see Pathfinding on Wikipedia). One of the most common algorithms used in games for pathfinding is A*. I won’t get into the details of A* in this post because it gets technical very quickly but the image below provides a good visual representation of a typical A* search.
By Subh83 (Own work) [CC BY 3.0 (http://creativecommons.org/licenses/by/3.0)], via Wikimedia Commons
An illustration of an A* search. The initial red node indicates the starting position and the green node indicates the goal position. The gray polygon represents an obstacle. The goal is to find the shortest distance path from the starting node to the goal node while avoiding the obstacle.The path found is highlighted in green at the end of the animation.
We are currently exploring algorithms and graph representations for our world in TUG but so far we have implemented a navigational grid. In graph terms the grid is made up of nodes that all represent the same amount of space (one square meter) and each node has edges to its immediate neighboring nodes (grid cells): top left, top, top right, right, bottom right, bottom, bottom left, and left. These cells can be blocked by obstacles (shown in the image below in red) or open (shown in the image below in blue). This allows us to run A* searches to find best paths for our characters that avoid obstacles.
Blue Cells: Areas a character can navigate in.
Red Cells: Areas blocked by an object.
I hope you have enjoyed this introduction to pathfinding. Pathfinding is a large topic with many different techniques available depending on the pathfinding problem at hand. If you have any questions please feel free to email me at “northman at nerdkingdom dot com”. We are working hard to refine our pathfinding approaches for our characters and look forward to sharing more with you soon!
Have a great weekend!