Smart Unit Navigation

Intro

Navigating a unit from A to B with some intelligence has always been an interesting problem frequently asked by game programmers. There are different ways of implementing this and I will try to show some algorithms and examples.

Although these pages are mostly dedicated to games programming they present algorithms that can be used for any program that requires pathfinding.

To get started, let me discuss a few issues that would have to be decided by the programmer and the nature of the game. Often we have to concider the speed of evaluation. This is important when we are working with realtime simulations in games. Another issue that frequently pops up, is the amount of memory it will take to evaluate the path from A to B. In a turnbased simulation, one can always use any efficient timeconsuming algorithm that will generate the true shortest path with as much memory it needs at the moment. When a path is found, one simply stores the path (a list of movements). However, in a realtime environment one would have to think about the speed and distribution of evaluation over time. You would not want the game to stall when you are doing the pathfinding for one unit. Distributing the execution over time means that more memory is needed as each moving unit has to have its own dataset for pathfinding. Realtime simulations also have to consider changes to the map during its movement that might result in the unit doing a costly re-evaluation. In contrast, the cost of re-evaluation in a turnbased game would not be that much of a problem to the player.

I hope these pages are of some help. Please contact me if you need some more information or want to contribute to these pages. More algorithms and example programs will be added in the future...

I'm sorry that I don't have the A* algorithm here yet. I will try to add a page on this some time later.

Have fun,
John Christian Lønningdal


Selected pages of interest:

Strange Creations -Biggest collection of programming tutorials, documents and FAQ's
Amit J. Patel -Game programming pages
Steven M. Woodcock -AI and other game related programming
Game Developers Magazine -Bryan Stout has collected all the path finding stuff into one Delphi program together with an article presented in GDMag Oct/Nov 1996. Check it out, it's well written and a great program to sample all the algorithms.
Interactive Game Algorithms Some very good pages on graphics and code optimization.
Lenny's pages A nice collection on a lot of fields within game development.

Last significant update: 28. September 1996


The Game Programmers Guild
This Game Programmers Guild site
is owned by
John Christian Lønningdal.

[
Prev | Skip It | Next 5 | Random |Next ]

Want to join the ring? Get the
info.

Back to my programmers page.


johncl@online.no