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

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