Dynamic obstacles

Dynamic obstacles is a way to modify the navigation graph at runtime. For example if there is box standing in a room npcs need to be able to path find around it. The system let you add and remove obstacles. Moving them can be seen as removing them and adding it again. Each obstacle have a position and a shape that describe how much area it touch. It also have custom data that describe what will happen to the part of the search graph that it affect. It can mark it non walkable, set some flags or change the cost of walking there. For example if you throw out some oil it can mark the area as a higher cost and a flag that treeman will not walk there at all. The rest of the details depends on what search space representation is used.

Tile:

In a tile graph one checks what tiles that the shape touch and then mark them.

Point:

In a point graph it get all the points inside the shape and modify them and the links to them as needed.

Navmesh:

In a navmesh they blockers can be cut out with geometry operation. The navmesh polygons inside the blocker can then be flagged as needed.

Reference

Automated Static and Dynamic Obstacle Avoidance in Arbitrary 3D Polygonal Worlds