Developing By Me

Project Development and Design

Pathfinding Basics

Within any simulation programming, which includes game development, it is important that the mobile object [mob] knows how to find a target and reach that target. There are a few methods of pathfinding that are currently used that include but are not limited to Dijkstra’s Algorithm [DA], Open Shortest Path First [OSPF], and B-Line. Each method has advantages however the best method depends on the project since each project has different environments and needs.

First it is best to understand what pathfinding is and what it needs to do. Pathfinding is defined as a method or algorithm to find a route from one point to another. In terms of game development, any mob needs to find a route through the static or dynamic environment. This route is our path it must avoid buildings, static objects and other mobs in order to reach the target location. This is often done in real time since dynamic objects can change from frame to frame.

The first thing to understand about creating a pathfinding algorithm is however it is programmed the mob needs to move through the environment. When it comes to static environments there is often a table or another primer that defines the layout of the landscape. Table 1 displays a small collision table.

Table 1
X X X X X X X X X X X X X
X . . . . . . 1 X . . . X
X . . . . . . . X . . . X
X . . . . . . . X . . . X
X . X X X X X X X . . . X
X . . . . . . . . . . . X
X X X X X . . . X . . . X
X . . 2 X . . . X . . . X
X . . . X . . . X . . . X
X . . . . . . . X . . 3 X
X X X X X X X D X X X X X

 

The above table has a few objects to note. The ‘X’ is impassable, ‘.’ is passable, ‘D’ is the door or entry point, and numbers are objectives. This table represents a house a player might want to raid. Since the player can ‘see’ where the chests and walls are he can quickly move around the room. However, the NPC can read the table to ‘see’ where objects are but how does it know which way to move to get there the fastest. That’s where the pathfinding logic comes into the AI.

It is important to understand there are two types of AI’s the first preplans the path then follows that until the circumstances change. The second goes at the target until it finds a block then tries to get around it. The first can cost a lot of CPU cycles since the whole path must be recalculated at every change. The second is more common since a B-Line is quick to program. But it can produce unexpected results. The best results happen from a combination of the 2. But before the hybrid can be explained the basics of the two methods needs to be explained.

Table 2 shows paths possible created by an OSPF or DA. In this table the nodes are marked with an ‘o’. Any of which could be used to create the path. The only difference between the OSPF and DA are the metrics used. DA uses an open location method while OSPF typically uses a grid method. The grid method is faster to reference but the open location method allows the AI to skip steps it would normally have to in the OSPF. The lines show the paths used by OSPF.

Table 2
X X X X X X X X X X X X X
X o 1 X o o X
X | . . . . . | X | . | X
X o o X | . | X
X | X X X X X X X | . | X
X o o o o o X
X X X X X | . | X | . | X
X o 2 X | . | X | . | X
X | . | X | . | X | . | X
X o o o o X o 3 X
X X X X X X X D X X X X X

 

 

 

 

 

 

 

 

Since the three objectives can be done in any order the AI has to make a choice on how to achieve them. There are a few assumptions but the first is that the AI can only move along the lines, no diagonals. If the choice is to layout the whole plan the objectives would be achieved in a logical order such as least number of steps. OSPF will follow the path of 2, 3, then 1 totaling 48 steps. If the AI is told to follow the objectives in order then the step count is 60. The difference is only 12 steps but this could be as much as 24 seconds assuming 2 seconds per step. The goal of OSPF is to find the shortest path from the predefined points. The method does not work well with dynamic environments since it will have to recalculate all of the possible locations every time the world changes.

The DA method allows the dynamic environment to shift since it uses the same OSPF points but only looks a head a few steps. This can reduce the processing time when the world changes. An example of this change is Table 3 where the walls and have moved.

Table 3
X X X X X X X X X X X X X
X o 1 X o o X
X | . . . . . | X | . | X
X o o o o X
X X X X X X X X X | . | X
X o o o X | . | X
X | X X X | . | X | . | X
X o 2 X | . | X | . | X
X | . | X | . | X | . | X
X o o X o o o 3 X
X X X X X X X D X X X X X

 

 

 

 

 

 

 

 

With the changed path OSFP would determine from the door that 3, 1, 2 or 1, 3, 2 is the best path. Both have a count of 42 steps, while the previous shortest path now has a count of 44 steps. The difference is not much but if the game board keeps changing the paths have to be recalculated every time. The advantage of the DA model is that every normal stop point is recalculated and only adjusted if there is a significant change. This allows the AI to maintain course to its first goal even if the step count becomes higher with the changes.  The processing is kept to a minimum allowing the AI to focus on the changes instead of the potential paths that could have changed again during the recalculations.

The next argument is the B-Line path. This is the most common since there are minimal calculations. The AI picks a target and follows the straightest line to that target. The problem with the B-Line is if the map looks like Table 4 it can get confused.

Table 4
X X X X X X X X X
X . . . . . . . X
X . X X X . . . X
X . . . X . . . X
X . . . X . . . X
D X 1 . . X
X . . . X . . . X
X . . . X . . . X
X . . . X X X . X
X . . . . . . . X
X X X X X X X X X

 

 

 

 

 

 

 

 

The B-Line will try to go straight at the goal following the line. However, if it’s a pure B-Line there are a few scenarios that could happen it can move up, down or get stuck. A properly coded B-Line will notice that it hast to move around the wall to the goal. However when the AI gets stuck there is normally a hard coded option of right or left. The default is right because most people are right handed. In this scenario right is the correct option. However if the walls were reversed then right would cause it to hit the wall and turn around to go the other way. The best option to avid this is to use a OSPF map with the B-Line. Table 5 displays the OSPF map.

Table 5
X X X X X X X X X
X o o o X
X | X X X | . | X
X o o X | . | X
X | . | X | . | X
D o o X 1 . | X
X | . | X | . | X
X | . | X o o X
X | . | X X X | X
X o o o X
X X X X X X X X X

 

 

 

 

 

 

 

 

the secondary map of OSPF the B-Line can choose which will keep it as close to its target as possible without turning the wrong way. This may appear to be identical to the OSPF or DA methods. However the B-Line can move in any direction it does not have to keep to the grid lines. The OSPF map is only utilized when there is a choice to be made that such as a wall that it cannot pass. This method is rarely used but can improve how pathfinding AI’s are utilized in the future.

The problem with many common pathfinding AI’s is they use the B-Line methods and the mob can get stuck. This is obvious when the mob starts to run around in a clockwise circle, turning right, or falls off a cliff trying to reach its target. Other methods can be used to prevent this but they will be covered in the next article.

Related pages

  1. AI Pathfinding A*
  2. AI Pathfinding Ray Casting
powered by Related Pages WP plugin

4 Responses to “Pathfinding Basics”

%d bloggers like this: