Sign in to follow this

Followers
0

#
Pathfinding concepts, the basics

General and Gameplay Programming

## The problem

Pathfinding is a domain in computing science that is widely known to be complex since most of the paper/explanation comes from expert/mathematician/AI veterans. Applied to games, it gets more complex as you get into optimizations more often than basic explanations. True, it is a complicated subject: it needs to be**efficient**and also be

**accurate**.

## The compromises

When you try to achieve both efficiency and accuracy, you will certainly need some very heavily-optimized code. So for games, we'll need to state some compromises. Do we actually need the shortest path or having a path at all will suffice? Can our level/terrain can be simplified into a basic layout? Those two questions are the fundamentals of the compromises:**sufficient and simplistic**. For games, an AI moving toward an objective will be sufficient enough to be believable. And to obtain good performances and efficient work flow, we'll need to break down our level into a more simplistic representation.

## The theory

Pathfinding is a complex process that we can split down into three components: the spacial representation, the goal estimation and the agent. The spacial representation, also known as the*graph*, is a means to describe a network of inter-connected walkable zones (roads, floors, ...). The goal estimation, known as an

*heuristic*, is a general representation to where

*might*be the goal. This is a mere estimation that is needed to speed things up. Finally, the agent is the one responsible for actually searching through the spacial representation based on the goal estimation. Putting this together you get an

*agent*searching for a

*goal*on a

*spatial representation*with some hints to where it

*might be*. Simple enough? But why do we need these three components? Why can't we just use a

*spatial representation*and iterate through all the zones till we find our goal? Yes you could, but it depends on what you are trying to achieve. What if you have different types of enemies? Say we have a soldier and a tank heading toward the player. A tank can't go in tight spaces and can not make sharp turns. How would you represent both in a one component? With the three components above, both units are

*walking*on the same terrain, looking for the same goal, the player, but have their own limitations: you got a spatial representation, a goal and two agents. That is why pathfinding is always explained as three distinct components.

## The graph

There are several ways to represent a graph of walkable zones and I'll be describing the three most used throughout my research. The first one, the most basic and easiest to understand is the*grid*. This is the most-explained type of graph when it come to pathfinding, go ahead and google "A star search algo" and you'll most likely find an

*evenly spaced grid*that covers a square room/space. Let's take a look on a simple "H" shape.

*detail*we could simply remove black dot from the graph and voila. Here's another catch: from

*a*to

*b*would require a search through all the mid to south noded, +-96nodes, to find a path of +-19nodes. The search algorithm is wasting precious time and power to go from 96nodes to 19. You could also add diagonal connectiond between nodes to reduce the path a bit. Another catch: most of the implementations I saw relies on raycasting from the sky (to detect nodes that are outside of geometry) thus making it useless (or complex workaround) when dealing with environments that have a ceiling. The point is, this graph is inefficient because too much data is representing the same

*zone*(we'll get into that in a moment). The

*waypoints*graph is the most used (based on pure observation in games). It does give you an alternative to the grid since more than 4 connections (8 with diagonal) between nodes can be made. Nodes are placed around the level with care to cover most of the walk-able areas without creating too much noise for the search algorithm.

*a*to

*b*of +-11 nodes. That is a lot better than the grid-based graph but still has a major issue (like the grid graph). The resulting network from these two

*point-line-connections*is stripping away part of your actual walk-able area. See the image below for a better understanding.

*floor*of our geometry. Multiple problems emerge from this fact: paths will have angular turns, an agent could never land on the

*a*or

*b*since they are not on the network and the paths can not be reduced with some

*direct-line-of-sight*. Because these types of network only consider the walk-able area to be dots (with a radius) and their connections, the outside of the network can only be

*unwalk-able*area or at least not safe (like a ditch, or narrow passage). So cutting a corner or trying to go in straight lines between nodes

*may be*risky. I say

*may be*because it depends on your level and your network. You could place your nodes to take account of the fact that agents will cut corners and maybe your level doesn't have ditches/holes/obstacles. For those that are still with me, the solution to the above problems lie within our actual geometry, meshes, commonly referred as navigation mesh or simply

*navmesh*. The mesh of your floor geometry is pretty much all you'll ever need to build your network: connected vertices form triangles, put in our terms, interconnected nodes.

## The heuristic

The heuristic is an information that is provided to each node of your graph to*direct*the search algorithm toward the target(s). Acting like a heat map, your search algorithm will look into this map to prioritize nodes.

*game changer*in pathfinding, without it, performance would drop since the search would need to look up every node till it finds the target. On the other hand, with a heuristic that isn't adapted to your game, it would result in false estimation and your search algorithm could waste some valuable time in the opposite direction of your target. If your graph is relatively small (node count) and your target platform possesses enough memory, the best heuristic would be as follows: each nodes contains a list of all other nodes in the graph with their corresponding depth. So node #1 would know that it's 4 nodes away from #56, and thus providing the best estimation for the search algorithm - moving from lowest depth connections of each node would inevitably result in the shortest path.

## The agent

This is where the search algorithm is performed. With a network and heuristic, a basic A* (pronounced "a star") algorithm can find the shortest path between two nodes. A* algorithm is really well documented and is pretty simple to implement (under 50 lines of code), so I don't have anything more to say on that topic.## The result

At this point, the agent found a path of nodes toward the target. As stated in my previous posts of April, Pathfinding 101 and Pathfinding 102-ish, we'll need to find a way to optimize the path into a list of waypoints. This is where I struggled the most, I tried to find an algorithm that would optimize the path based on*my*understanding of the

*Funnel algorithm*. And then I found a simple implementation in C++ (first result on google). It does work perfectly and it only requires a list of

*portals*to walk through, so it will work with any graph you decide to use.

## Demo

A tech demo that combines everything discussed in this article.## Implementations in Unity3D

- Aron Granberg's Pathfinding v3.0 is looking awesome; grid and navmesh graph + Recast; free and pro licence (not yet released)
- Alex King Simple Path; grid graph only, doe not support height properly; pro licence only (60$)
- Unity3d road map includes Recast + Pathfinding + Crowd simulation for its v3.5 (fall 2011)
- Your own implementation (to be released)

*Reprinted with permission from Michael Grenier's blog*

0