I've been thinking about how I would setup the pathfinding nodes/edges for the heightmap based terrain in the RTS game I'm working on. The method I've come up with thus far is as follows: 1. Get all vertices and edges from the terrain mesh 2. Create a node at every vertex and pathing edge for every edge 3a. Loop through every edge, finding it's slope angle 3b. If angle > maxAngle, delete edge and mark edge's nodes (vertices) as red 4a. Loop through every edge 4b. If the edge's nodes (vertices) are both red then delete edge 4c. If the edge has 1 red node then mark the other node as blue 5. Loop through every edge and delete those that don't have 2 blue nodes 6. Loop through every node and delete all those that aren't blue (I called the nodes blue and red in this instance to correlate with the picture below) After that, assuming I'm not mistaken, there should be remaining only an edging around any rises or falls that exceed the slope limit. This picture should help show what I mean. The green edges are those that exceed the slope limit. The red nodes are those that are connected to edges that exceed the slope limit. The blue nodes are those that are connected to edges with one red node. The yellow edges are those that have 2 blue nodes. The yellow edges and blue nodes are the ones that would be kept in the end. Given that I now have the boundaries, I could run through each remaining node and check it against every other node and see if there is a boundary (yellow edge) between them (on the x-z plane) and if not, create a new edge between them. I'm pretty sure that after that I'd have all I needed for pathfinding to anywhere. At run time when pathfinding from A to B I would: 1. Get closest node to A and pathfind to closest node to B 2. Check if there's any blockage between closest node and next node on path and if not, drop the closest node and go to the next node 3. At second last node on path, check if there's any blockage to B and if not, go straight to B I'm pretty sure that this will all work, but I don't want to start implementing it without being sure so my questions are: Is this going to work and/or is there a better way? Also, what would be the best way to incorporate dynamic blockages at runtime (eg. built buildings and other units)? I would think ignoring them when doing all the pathfinding and just using flocking to get around them. [Edited by - Matt Carr on May 18, 2008 12:14:44 AM]

I would use the polygons directly instead of the edges. Edges are... edges, lines where every geometric notion is typically ill-defined.

Instead, mark the polygons according to their normal. Much easier.

Quote: Original post by Steadtler
I would use the polygons directly instead of the edges. Edges are... edges, lines where every geometric notion is typically ill-defined.

Instead, mark the polygons according to their normal. Much easier.

I'm not sure I could end up with a result as effective without using the edges. I'd be using this method on terrain created by raising and lowering verts on a triangle strip based plane so I don't think there'd be any issue.

I'll probably implement this sometime in the next couple of days, I'm pretty sure it will work fine.

Quote: Original post by Matt Carr
[ snip ]
I'm pretty sure that this will all work, but I don't want to start implementing it without being sure so my questions are:

Is this going to work and/or is there a better way?

Yes and yes. You can use edges to compute gradient and pathing information and provided that your units only ever move along this skeletonisation of your surface you'll be okay. If your units can move freely over the surface then constraining them to only move on edges looks abnormal. If you add path smoothing to make the path look more natural you cannot then be assured that you haven't violated your gradient constraints. If this is an issue for you, use surface information (directional derivatives through the centroid would be a good start). Other than that, your algorithm isn't optimal, but that's an issue I'll let you work on. ;)

Quote:
Also, what would be the best way to incorporate dynamic blockages at runtime (eg. built buildings and other units)? I would think ignoring them when doing all the pathfinding and just using flocking to get around them.

You can take that approach - that of combining a reactive steering system with a path following system to deal with dynamic obstacles - but you cannot guarantee that any local obstacle avoidance behaviour wont invalidate your path solution (i.e., leave the unit in a position from which it cannot return to the path).

The alternative is to maintain a dynamically updated cost graph for the problem, using, for example, D*.

Cheers,

Timkin

I agree with Steadtler.

Take the dual of your graph -- turn each face into a node, each node into a face, and each edge now connects the two nodes that where the two faces it was between. (this can be conceptual rather than literal).

Now each node has a slope -- the normal of the face. Delete every node that breaks the steepness condition -- an easy check. This automatically involves deleting every edge adjacent to it.

You can freely move back to the starting map, and now the legal terrain to move on is a bunch of faces, and the too steep portions are deleted on a face-level.

Note that your solution could rule out possibly valid paths. A narrow and flat 1-tile wide path between two steep cliffs would be deleted by your algorithm, even if it was perfectly clear.

If you want to find the equivalent of "blue" nodes, simply mark every adjacent face blue when you delete a face. If you want to find the equivalent of "yellow" edges, instead of deleting edges when you delete a face (aka, mark it as red) instead mark them yellow unless the node on the other side is red -- in that case, delete them.

This will result in every deleted (or red) region being surrounded by yellow edges.

If you want to mark the faces that are adjacent to the red/deleted faces, just mark all adjacent faces as blue if they aren't already red when you mark a face as red. And now you'll have a ring of blue faces, and a ring of yellow edges, around every "pathing hole" on your map.