How do you maintain a navmesh in RTS game?

In RTS you constantly build and destroy buildings. That means you need to update your navmesh through the game.

I have done hierarchical pathfinding with two graphs, one finer and one coarser, on static map that does not change, from the book Programming Game AI by Example. I have not worked with navmeshes so far. I have no experience with maintaining a graph or mesh either, as in RTS games. Any articles or books you can recommend on the topic I would gladly read.

Thank you

You might check out Recast and Detour. It supports building a navmesh out of connected tiles, and each tile can be quickly reconstructed as the mesh from which it is obtained is changed.

I have seen all sorts of articles around that deal with the dynamic modification of navmeshes. It's not trivial, however. Implementing something like Recast might be the best bet.

It is much more complex than the pathfinding I did in "Programming Game AI by Example". I doubt I will find a book where NavMesh implementation is given and explained. But it seems the AI Game WIsdom series contains a lot of information on NavMeshes. As soon as I get some money next week I am ordering all 4.

In my RTS project so far I got the selection system and steering behaviors. Next is the pathfinding system, seems I will spend two months or so on this.

Edit: I decided to go with Recast and Detour. I will spend way too much time on pathfinding myself and I won't get the game done till October which is my deadline. If you guys can recommend some tutorials/articles or whatever on Recast and Detour please, there is no documentation for it which makes things hard.

I decided to do my own pathfinding. I provide a short description of what I plan to do, feel free to comment.

1. Only two types of objects can change the navmesh at runtime. Trees and buildings.

2. Trees - when a tree is cut down a rectangle will be added to the navmesh, at position where the tree was so that the area is now walkable. Each minute I will do a check if I can join some rectangles for fallen trees. This way I wont lose performance and I will make sure that I dont get lot of small rectangles in the navmesh for the trees that were cut down. So that is all about trees, easy right?

3. Buildings - As in Warcraft, you can position the building at discrete positions, which means I will use a grid. There are two cases, a building is created or destroyed. When a building is destroyed it is easy, just add one rectangle(representing this building's area) to the navmesh. When a building is created it will occupy a rectangle in my grid so basically I will just cut off the cells that are inside this building's area, which will be fast to test. Then I will add the triangles around the building as in this image. http://postimage.org/image/5pnq53dzb/ So you can just walk on the green area, the yellow is the building. This is the only case where I will use triangles in my navmesh. Everything else will be done with rectangles that fit in a grid so that intersections tests are easy, when you try to create a building and update the navmesh. So the main part of the job will be dealing with the different cases of rectangle intersections. Restricting myself to a grid and not using triangles will make things easier. Well actually instead of thinking about cases, I should find myself some computational geometry algorithm that partitions a surface into rectangles. Not quadrangulation algorithm, I need only rectangles which are quads yes, but with vertical and horizontal lines only.

Here is the process of creating a building: http://postimage.org/image/bzde0j8vf/

A question I have is will this cause me problems? http://postimage.org/image/wow6dzpuj/
I mean can I have two rectangles that share a side with one rectangle, or I will have to split the big rectangle like in the image below ?

Thanks for any comments