Currently working with pathfinding in my recent project, and would like to figure out a way to deal with objects that are placed after the map is created, or objects that can be destroyed after the map is created. Currently, I just use steering to work around these objects, similar to the methods used to work around moving characters, but I can't help but think that there is a better way. The way I'm currently doing it allows for my agents to get stuck if the objects are placed in certain ways, and they exibit a lot of the stupid looking tendancies of solving pathfinding with steering alone. The objects in question don't move [or do so in an instant way, and do so rarely enough to be treated as seperate objects], but are boolean in thier existance. Stuff like a door closing and opening, or a crate or wall being destroyed, or a new wall being built, are starting to make things rather tough on my pathfinding. The solution, obviously, is to incorporate these new obstructions/openings into the structure that i'm already using to find paths around static objects, so that the path finder [that already works great for static geometry] can do it's thing, with less reliance on steering. But I'm at a bit of a loss as of how to do this. Removing objects that exist from the start seems simple, just include a set of nodes that cover the entire footprint of the object in question, and leave links to these nodes deactivated. Just activate them when the object is destroyed, and deactivate them if it's re-created [in the case of doors], and it's done. This doesn't work though for dynamically created objects, whose position isn't known at load time. I'm using a triangular nav-mesh for my path finding, incase that helps. I'm kinda at a loss here as of to what would be the best way to approach this. How have others done it?

The triangular nav-mesh helps :)

You can re-compute the part of the navmesh that is affected by the change.

If its something destroyed, just triangulate the area it occupied.
Its its something new, you need to eliminate the triangles that are completely occupied, and divide the partially occupied triangles into a bunch of new ones.

Saw this approach in the AI wisdom book...

You may also use some kind of constraint on the size of the new triangles, or you might end up dividing forever.

Also be very careful about spikes. Unless the calculations you are doing are very small and limited you don't want to do them all in a single frame.

In Spring I solved this by keeping a list of areas that need to be recalculated, and keep working thru it with a limited amount of calculations during each frame. In the meantime you can use their old values.

Take a look at the D* algorithm (Dynamic A*). It does exactly what you want.

Thanks for the input, currently working on a quick and dirty way to re-triangulate the altered areas, splitting into time steps [good idea btw, likely something I would have had to go back and change, especially considering things tend to all change at once]. Trying also to have it save the old state too, so that when it is removed [especially true with doors opening and closing] it just deletes the changes and puts the old stuff back.

Looking into D* too, looks interesting, and even if i don't use it, looks like good reading :D

Google is being a real pain though, searching for '*'s, and DStar turns up rather little. Know of any good papers off the top of your head? [I'll find them eventually, but if you happen to know some, can save me the search]

This would be as good a place as any to start...
http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

In particular, check out Anthony Stentz's work in this area.