I'm tring trying to navigate an off-grid mesh. The mesh is generated as follows: Take the triangle directly under the players starting point (determined by level designer). Look up which triangles share edges with the current, if the slope below a certain treshold (can a unit walk on it?) add it to the solution.


The result is an irregular mesh (note I forgot to triangulate two quads in the illustration)


Elevation and slope in the mesh are stored, there is no overlapping.

What I want to be able to do is the following:

1) The player can build and remove structures that the agents will have to navigate around.


2) The player can build structures that have their own tiny piece of nav-mesh or vertical displacement (stone walls, lookout posts) that agents can walk on


3) Agents walk around relatively small obstacles or perform an action traversing certain areas (swamp, chest high wall)


For 1) and 2) I think there are potential issues with triangulation and splitting/restoring the mesh everytime something is built or removed. The mesh easily gets very dense when multiple buildings are placed on/inside one triangle.

Because inserting and removing nodes from a 2D BSP tree is trivial I thought this might be a solution. Is something like this ever attempted before? Are there any articles on 2D BSP pathfinding?

[Edited by - Defeatist on June 2, 2010 10:15:27 AM]

Can you link-ify the images? (You can use HTML tags for this.)

updated! :)

You can add the new obstacles as polygons and run gluTess on it. You'll have to rebuild the graph, but it'll do what you want and be reasonably close to optimal.

-Morten-