Path Finding (Part 1)

One of the most common problems in game programming is the need to find a path to move some intelligent entity. Take as an example a game where the player (represented by a ghost) is chased by some intelligent enemies.

A simple solution to this problem is an algorithm where the direction is obtained from the relationship between the positions of the enemies and the player, as shown in the image below.

Unfortunately, this solution is not satisfactory for most of the games ’cause it doesn’t take into account many possible obstacles in the scene. Besides that, it also doesn’t calculate the best path (which is not always the straighter or faster way).

To have a better result, we must use a Path-Finding Algorithm. The process consists of three steps:

  1. Map the scene defining the main points (nodes), the links between these points (connections), the value of each connection (cost) and the position of each point in the scene (2D or 3D);
  2. Run the algorithm to calculate the path between the start and end points;
  3. Take the response and use it to move the game element.

The mapping process may change according to the type of scene. This process can be done manually, but it’s common to use tools for that purpose (such as Level Editors).

The mapping information is then loaded and used by the game. Usually this data is represented with one of these data structures:

  1. Adjacency Matrix: A [NxN] matrix where each line represents the start point, the columns represent the destination and the values ​​represent the connection’s cost.
  2. Linked List: Better structure than the array (it saves some memory), but is more complex to manipulate.
  3. Graph: Data structure where each point is represented as a node and its connections with others. It is the most used structure for path-finding.

The image below shows an example of a game scene mapped into an Adjacency Matrix. Notice that the value 1 (one) represents a connection from one point to another. When there is no connection between two points we use a value that represents infinity (can a very large value if the language cannot represent this value).

Although it is easy to use, an Adjacency Matrix wastes a lot of memory when the number of points of the scene is very large. Furthermore, another structure is required for storing the visual location of points in the scene.

The Graph data structure is widely used and can be implemented using an object-oriented approach, as shown in the image below. The great advantage of using an Object-Oriented Graph is the possibility to attach a logical behaviour on it (for example when a door opens and the graph needs to be adjusted, reacting to that event).

It’s important to notice such algorithms cannot run all the time because of performance issues, thus it is important to define the frequency they are executed. The tricky part here is to find a good balance because, depending on the implementation, the visual result may not look convincing enough (laggy).

Another important detail is how to specify the start and end points to the algorithm. Because of animations and interpolations, usually the visual position of the game elements aren’t exactly the same as the mapped points, which may require a function to find the closest node from a specified position.

In the next post I will speak about Dijkstra, the first algorithm created to solve the problem of path-finding.

 

One thought to “Path Finding (Part 1)”

Leave a Reply

Your email address will not be published. Required fields are marked *