Gamasutra: The Art & Business of Making Gamesspacer
Smart Move: Intelligent Path-Finding
arrowPress Releases
July 29, 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

Sony Online Entertainment, San Diego
Sony Online Entertainment, San Diego — San Diego, California, United States
[07.29.14]

Intermediate and Senior Database Tools Programmers
2K
2K — Novato, California, United States
[07.29.14]

Senior Engine Programmer
Turbine Inc.
Turbine Inc. — Needham, Massachusetts, United States
[07.29.14]

Cloud Solution Architect
2K
2K — Novato, California, United States
[07.29.14]

Senior Animation Engineer






Comments


bruce wernick
profile image
PathDemo link is broken


none
 
Comment: