|
Of
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.
|
Printer-Friendly Version
