 |
|
 |
| |
Smart Move: Intelligent Path-Finding
by Bryan Stout [Programming]
|
|
| |
|
February 12, 1999
|
|
Page 1 of 9
|
|
|
| |
|
O
f all the decisions involved in computer-game AI, the most common is probably path-finding-looking for a good route for moving an entity from here to there. The entity can be a single person, a vehicle, or a combat unit; the genre can be an action game, a simulator, a role-playing game, or a strategy game. But any game in which the computer is responsible for moving things around has to solve the path-finding problem.
And this is not a trivial problem. Questions about path-finding are regularly seen in online game programming forums, and the entities in several games move in less than intelligent paths. However, although path-finding is not trivial, there are some well-established, solid algorithms that deserve to be known better in the game community.
Several path-finding algorithms are not very efficient, but studying them serves us by introducing concepts incrementally. We can then understand how different shortcomings are overcome.
To demonstrate the workings of the algorithms visually, I have developed a program in Delphi 2.0 called "PathDemo." It is available for readers to download. The article and demo assume that the playing space is represented with square tiles. You can adapt the concepts in the algorithms to other tilings, such as hexagons; ideas for adapting them to continuous spaces are discussed at the end of the article.
|
| |
|
Page 1 of 9 |
|
|
| |
|
|
|
|
Printer-Friendly Version
