In the first few months of 1996, I read about many approaches to unit movement and path calculation. At the time path-finding did not seem to be widely used in games, but as CPU cycles have increased and as game players have demanded better movement of units, path-finding algorithms have become more popular. I eventually decided to implement path-finding for my game with the A* algorithm. My game has a grid/tile map (as opposed to a continuous coordinate map), and I wanted to tell military units to walk from one spot to another. How could I find a good path? I want my units to take roads when possible, and avoid mountains and hills. (This is similar to the path-finding goals in the once-popular game, "Civilization".) I have been writing up some of my thoughts and findings in these pages.
When trying to write movement for game units, the biggest choice is probably between the path-finding and step-taking approaches. Path-Finders look at the map and find a path for your unit to take. After that, your unit takes each step prescribed by the path-finder. Step-takers look only for the next step and leave the remainder of the path to the goal for later. There are advantages and disadvantages to each approach, as you might expect. When two things are in widespread use, you should expect that neither is always better than the other.
There are many other topics related to path-finding.
Next: Introduction |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |