I'm working on some pathfinding, and I've been trying to find a good way to divide a map up into sections to use as nodes for high-level pathfinding.
Low-level pathing consists of generating the intricate paths required to navigate around obstacles to get to a specified end point, whereas high-level pathing is used to plan out the general route across the map that the low-level path should more or less follow (or at least gravitate toward). High-level pathfinding will ignore small obstacles (like trees or small rocks) and instead focus on finding a general route around any large areas of high ground or large masses of water, or any other major terrain aspects.
Another thing that high-level pathfinding should take into account is any major choke points in the map that could be avoided. This can fairly easily be done by simply adding a higher cost for traveling from one node to another if there's a tight choke point in between the two.
The actual pathfinding is fairly simple to do. The part I'm running into trouble with is creating the high-level nodes in the first place. Basically I've demonstrated what I'm trying to do on the Xel'Naga Caverns map from StarCraft 2 just as an example:
-Red lines show the actual map walls (ehh, so I scribbled them in...close enough).
-Blue lines show where the different sections were divided.
-Green dots show the section center points that will act as the actual high-level nodes.
To demonstrate how these would be used, let's say you want to find a path from the pink dot to the yellow dot. First you generate a high-level path (blue) from the high-level node of the starting section to the high-level node of the ending section. Then you'll generate the actual low-level path (white) using the high-level path as merely a guide for generally where to go.
I'm trying to figure out a way to generate these map sections dynamically, but I'm really not sure how to go about doing it. Any suggestions?
I'm thinking it would work to maybe trace an outline of all the walls and then simplify those outlines to smooth out the chaotic edges and find more of the general shape of the walls, and then use those angles to create the sections, but I'm not sure how to go about simplifying the lines.
EDIT: I found two algorithms that I may be able to use for this: the
Ramer-Douglas-Peucker algorithm for simplifying a curve made up of line segments, and the
Hertel-Mehlhorn algorithm for approximate convex polygon partitioning.
I can use the first algorithm to simplify the walls of the map, then use the second algorithm to remove inessential edges, leaving me with larger convex areas which I can easily use as the nodes.
The only thing I still have yet to really find is a good polygon triangulation algorithm that doesn't tend to make slivers...I know Delaunay Triangulation is supposed to avoid long, thin triangles, but I haven't found a very good explanation of the algorithm itself, or any clear implementations of it.
