Gamasutra: The Art & Business of Making Gamesspacer
Smart Move: Intelligent Path-Finding
View All     RSS
December 21, 2014
arrowPress Releases
December 21, 2014
PR Newswire
View All






If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Smart Move: Intelligent Path-Finding

February 12, 1999 Article Start Page 1 of 9 Next
 

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.


Article Start Page 1 of 9 Next

Related Jobs

En Masse Entertainment
En Masse Entertainment — Seattle, Washington, United States
[12.19.14]

Network Engineer
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States
[12.19.14]

IT Administrator
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States
[12.19.14]

IT Administrator
Gameloft
Gameloft — Seattle, Washington, United States
[12.19.14]

Gameplay Programmer





Loading Comments

loader image