Pathfinding in 3d space

[mohsenz2006]

Hi every one.
I know how to setup a 2d A* path-finding system in Irrlicht. Actually I've already done it.
But my problem comes when I want to setup a 3d A* pathfinding system.
for 2D I draw nodes and edges (the grid) and store their positions and cost (distance). in 3d space I don't have a grid. I have a terrain or a room. how should I do that for them?

[hendu]

The common methods are either polys, waypoints, or a 3d grid (for example 0.5m apart, etc).

[CuteAlien]

Depends also a little on what you mean with 3D. Do you still walk on the floor, except maybe for occasionally jumping, ladder climbing, etc (typical shooter)or do you fly around the world (helicopter)? Don't really know how to solve flying, but for walking a typical solution is using a navigation mesh. You can try creating those from the polygons, but having done that once I don't recommend doing that - instead write a small editor for that where people can define the walkable areas (way faster to code and better control for level editing guys).

[mohsenz2006]

you were so helpful guys but aren't there any references, sample codes or stuff like that on how to generate a navigation mesh and/or defining walkable areas? I'm new to Irrlicht and need some more help.

[CuteAlien]

Try google... I haven't done that for years, back when I needed it the best information was available in the "AI game programming wisdom" books. But maybe by now there are websites out there describing it as well.

[mohsenz2006]

I've been trying it for hours but couldn't find any thing useful so far. I've also read some game AI books but none of them describes how to generate navigation mesh.
I know that in Irrlicht we can set up a Triangle Selector and through it we can get the triangles of a mesh. but I'm not sure if I'm in the right path and I'm worried about the performance. for example if we have a 200 x 200 terrain, it doesn't seem a good idea to get all of its triangles.

[CuteAlien]

It's not trivial to do. Using all polygons or merging polygons is one of the questions. But what I meant above is that the best way to generate it is to do that by hand with an editor. Aka - you either mark the floor-polygons as beeing part of the navigation mesh - or (mostly better) your editor allows just creating new polygons for the floor (which can be projected to have the same height as the floor automatically for example). I really can't help much with searching - the game ai programming wisdom book was the main source of information I had last time (and I spend months full-time working until my navigation mesh was good enough to handle all the cases I wanted including stuff like ladders - this was _way_ harder than coding A* itself and I had to figure out a lot of it myself as the book only gave the rough basics. Actually it was the hardest part of writing a FPS-AI which is why I recommend so much writing an editor instead of trying to automize it - writing an editor for that is a lot easier and even more flexible in the end).

[ACE247]

A Link from how navmeshes are created In Valve's Counter Strike Source, It might well be insightfull to the what, how's and such.
https://developer.valvesoftware.com/wik ... ion_Meshes
A Link to a practical example with Source Code, not using navmeshes, but Nodes to do A* pathfinding.
http://irrcodes.googlecode.com/files/pathfinding.zip
And finally there's the Recast Navigation Library which does Navmesh generation and comes with a A* Demo.
http://code.google.com/p/recastnavigation/

Hope that was helpfull.

EDIT: Oh and there was this ol' article on navmeshes and pathfinding, that gives quite a nice overview of things.
http://www.ai-blog.net/archives/000152.html

[mohsenz2006]

thank you all. you were great.