Morning all Thought I''d email to see whether anyone out there knows of this cool new way of AI pathfinding I''ve heard of - NavMeshes - and whether anybody knows of any sites/source code around that explain the idea and how to implement it? Cheers Dan

From what I''ve read, NavMeshes aren''t a new AI technique, just a different way of generating nodes for search algorithms like A*. Instead of the older method (manually placed nodes, or a grid of them), you just have a program (the game itself or a level preprocessor) analize the geometry for a level and use that information to generate nodes. You can also just use the geometry itself as nodes (like each floor polygon''s center) and not have to keep seperate information for the AI.

Yep, NavMeshes have been around for a while. The best sources i''ve found at Game Program Gems 1 and AI Wisdom.

I''d advise not using the raw world geometry because you can do some simple optimizations if you make seperate node listing.

I''m currently working on making a simple NavMesh program (2D) and will post it in a week or so once its done and after I do a quick write up.

...and further to this, nav meshes are just a name given to a specific, simple type of skeletonisation technique for planning. The broad class of skeletonisation techniques has been around for a very long time... so to suggest that nav meshes are new is incorrect and that in reality, they are just new to you!

Of course, it''s great that you''re learning new AI techniques.

Cheers,

Timkin

Hi again

Cheers for all the helpful replies. Had a look thru'' the AI Wisdom book and may buy the next book in the series, but still would love more code, so if that code''s available (from ''TheDarkening'') then I apprecaite seeing what you''ve done.

At the moment, I''m reading in the world mesh, generating face normals and measuring their angle to a up vector (0,1,0) and if the slope is over 60 degrees then''s it not walkable, else it can be part of the NavMesh. BUT, the code doesn''t work. The normals seem ok, the angle code is solid, and then convertion from RAD to DEG is fine, so what''s wrong??? Any ideas?

Dan

if you are interested in NAvMeshes I suggest you read the work of Jean Paul van Waveren about the bot in Quake Arena as it''s entirely based on NavMeshes. Pretty interesting stuff. Clicky

Sancte Isidore ora pro nobis !

quote: Original post by djwarder
but still would love more code, so if that code''s available (from ''TheDarkening'') then I apprecaite seeing what you''ve done.

I didnt manage to get as much done on the NavMeshes as I had planned (spent too much time fixing peoples computers and working on other areas of the game). Right now all my nav mesh creation code does is allow the user to pick the points and if polygons share an edge they will be connected. It then uses A* to find a basic path from point A to B.

djwarder, If you''d still like to see the code then send me an email and we can set something up.

sirstatic@hotmail.com
icq 19378482