Pathfinding in buildings

[lhkbob]

I know you can easily use a* to search over terrain and things like that (especially because they lend themselves to easily making nodes for the paths), but are there any efficient algorithms geared specifically towards moving around buildings.  You could do it with a* and hand placing the nodes appropriately, but I would like an algorithm that would work with (pseudo) randomly generated buildings in which case it might be harder to place accurate nodes.

[ravenger]

I guess the thing you would apply in interiors like buildings is called a navigation mesh. An interesting link I stumbled upon is this one: http://www.ai-blog.net/archives/000091.html, hope its helpfull

[lhkbob]

Thanks, this seems to be exactly what I was looking for.

Games published by our own members! Check 'em out!

[JAW]

I give the same reply in almost any A* questions:
You dont need better pathfinding, you need a better search space. Just define an algortihm that produces optimal navigation nodes. You cant search better than A* in most cases, but you can greatly improve the data you search in.

For navigation in buildings I would place nodes on all relevant positions like doors, stairs and whatever. Maybe place extra nodes for cover behind objects, if the game needs it.

There are several articles about search space optimization on Gamasutra afaik.

-JAW

[raft]

You dont need better pathfinding, you need a better search space.

exactly agree. indeed that's what jKilavuz aims for. it's designed with the purpose of collecting pathfind data from arbitrary geometry. from it's tutorial:

There are numerous good algorithms for determining a path given a connectivity graph. The actual problem is creating a connectivity graph which correctly represents the enviroment. For simple 2D games the connectivity graph was a side affect of the tiling system used to create the map. For 3D games, especially those constructed from arbitrary geometry, no such simple solution exists. jKılavuz is meant to solve this problem.

regards,
r a f t