XNA NavMesh generation
A very simple program to generate a NavMesh implemented in XNA.
After adding some collision geometry the open areas are flooded with small AABBs (rectangles). It will then find all boxes that are next to the collision geometry and store the edges of these boxes. Because of this you can use any shape for your collision geometry, although only simple AABBs are used in the examples.
When all the edges have been found they are cleaned up so that it only contains vertices in the corners. From these corners "Portals" are then generated and this creates "Rooms". The general rule is that you should be able to draw a straight line from a Portal to any other Portal in the same Room. If this is not possible another Portal is created to split the Room in two.
After the Portals and Rooms are created they are linked together to create a waypoint graph that can be used by AI to find it's way around the map.
The final waypoint system should be used with other methods such as obstacle avoidance to create more natural movement.