Hello all, i'm now about to embark on implementing path finding in my game engine and was wondering if anyone can see any obvious flaws with the methods im considering using? Firstly a little about the level layout for the engine - Levels are basically a hybrid heightmap / tile based approach, although meshes can be placed at non tile-aligned locations if the level requires it to allow for a less modular feel below is a screenshot of a basic level in the designer - Im considering 2 possiblities for the level navigation 1) Use a points of visiblity graph ( simular to that used in the unreal2 engine ), this would be designed by the level designer by placing points of visibility in the level and connecting these together to specify which ones can 'see' each other. 2) Use a navigation mesh for non heightmaped areas created from the tiles themselves, each tile would have a mesh marked as floor which would be added to the worlds navigation mesh at level compile time. Option 1 would result in a smaller search graph whilst option 2 would require no additional designer input once the tiles have been created by the artist but would result in a potentially much larger graph. One important factor is that the player will be able to control up to 25 characters and that these should be-able to navigate as a 'pack' through the level [Edited by - MButchers on January 17, 2005 11:15:10 AM]

I would recommend option 1 wholeheartedly for several reasons.

First, allowing an artist to create the graph will probably result in more natural looking motion. Second, smaller graphs are much easier to solve if you're going to use an algorithm like A*, which will leave you with more cycles to dedicate to other important things your game needs to do.

Many thanks CWhite

Mark

Quote: Original post by MButchers
1) Use a points of visiblity graph ( simular to that used in the unreal2 engine ), this would be
designed by the level designer by placing points of visibility in the level and connecting these together to
specify which ones can 'see' each other.

Why not scatter such points randomly, using your existing visibility tests to form the connections to nearby nodes, and eliminating any redundant points (eg. those that connect to all the same nodes as an adjacent one)? The advantage of this method is less work up-front for your artist/designer, and the algorithm can be easily re-run if you make subsequent amendments to your level. You can still let the artist amend the eventual graph if you need, but you may as well get the computer to give them a head start.