Pathfinding – The Art of Search
Posted on 24 de April de 2010 by William Wolff on Articles
Pathfinding is basically the hability of a object to move yourself from a point A to a Point B in a intelligent way.
This is the most simple and specific definition that we can have to explain this technique used today , mainly in computer games.
When we are playing some computer game or during the development of a game , we face up with the question of how the elements of this game will be moving along the game enviroment.
Every day we see more , and more games with their characters moving thru big landscapes , identifying obstacles , avoiding mountains , and being able to move in groups and making region patrols.
In this cases and many others in a specific moment we must determine the path needed by this objects to move along the enviroment, making this task one of most important task in a game development point of view.
Using modern computer graphics techniques, every day the game enviroments are being large , dinamic and complex, turning the job to find the path in this enviroments something really challenging.
1.1 Logic Elements.
To realize a simple search on a game enviroment we must define some key elements to the process.
This elements form all the logic structure needed to make a intelligent search on the enviroment.
Basically we have 4 elements to do a Pathfinding:
- Object or Character.
- Logic Map.
- The search algorithm.
- Functional Control.
In this post i will only talk about the logic map and the search algorithm, becouse i think the other elements talk for yourselves, don´t you think?
1.2 Types of Maps.
In simulated enviroments or computer games a “Map” can be considered any logic representation of search space where we are trying to “move” from a location to another.
This Maps can be inumerous logic structures , but with a common objective of make possible we “Locate” determined points or “places”.
On the development of the simulated enviroment needed to the game, in many cases, the creation of this map determine the way of the things will happen on the game execution , and this map are pré-created before the game logic be implemented taking account the influence caused by the type of map used in a game.
This pré-creation can be done in different ways , but the techniques that are used frequently are:
- RoadMap
- Cell Decomposition
- Potential Fields
In the RoadMap approach the space conectivity is represented by a unidimensional curves network.
In the Cell Decomposition approach the space are broked into cells where the conectivity of each cell is represented by a adjacency graph between the cells.
In the Potential Fields approach, a function that determine the Attraction or Repulse in every place of a map are applyed.
1.3 Search Algorithms.
After the definition of what map are being used we must attach a search algorithm to perform the searches in this enviroment.
When we think in obtain a path, we are not thinking only get the path, but we want the “Best” path.
Is that means for example, we not want the character do a travel in all the map, just to reach the other side of a little house on it…
The most famous search methods are:
- Breadth First Search
- Best First Search
- Dijkstra
- A*
I will only talk about the A* algorithm, becouse this is a closed question about their superiority about the others.
1.3.1 A* – The Mojo of a search.
In this search method a graph of adjacency are traversed containing weights in every node.
In every iteration a heuristic calculation is performed making possible evaluate if the search are being realyzed in the best direction possible.
Conceptualy, a heuristic is a calculated estimative using the characteristics of a specific problem, that make possible evaluate if the processing of the algorithm are converging to a possible solution, or not.
The most used characteristic to perform this calculation is the distance, but this not means other variables cannot be used, like the type of ground where the character are walking.
The most famous heuristic formulas are:
- Euclidean Distance – √(x-x´)*(x-x´)+(y-y´)*(y-y´)
- Manhatten – (x-x´) + (y-y´)
- Max(dx,dy) – If { a=(x-x´) > b=(y-y´)} return (a), else return (b)
This is a possible implementation of the A* algorithm:
I hope this help your journey in the game development , and for any doubts and comments , i will be glad to help you in “the best path i can”… 
Regards.
William Wolff
Comments:
Leave your comment
Wolff Entertainment.com - All rights reserved
powered by wordpress
Recent Comments