Omnimaga
General Discussion => Other Discussions => Math and Science => Topic started by: ZippyDee on August 31, 2011, 07:27:04 pm
-
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:
(http://img.removedfromgame.com/imgs/Screen shot 2011-08-31 at 4.10.38 PM.png)
-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.
(http://img.removedfromgame.com/imgs/Screen shot 2011-08-31 at 4.14.40 PM.png)
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 (http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm) for simplifying a curve made up of line segments, and the Hertel-Mehlhorn algorithm (http://www.philvaz.com/compgeom/) 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.
-
So are you pretty much looking for a way to get from point A to point B in a kind of maze of "rooms" ?
-
I remember coming across an interesting pathfinding algorithm in some papers a few months back. Basically...
EDIT: found it
"Reactive Path-Planning: A directional Diffusion Algorithm on Multi-layered Cellular Automata" by F. M. Marchese, written sometime around 2000. Sorry I can't explain the algorithm, but I have to go. Hope you can find it.
-
Xeda, I can do pathfinding. I have written multiple pathfinding implementations before. It's CREATING the rooms that I'm having issues with.
Qwerty, Thanks for the reference! I'll take a look and see what I can find.
-
So if I get this right, you want to automatically split the map into area's, such that connectivity is preserved?
-
Actually, are you trying to generate maps or implement a pathfinding algorithm? Those tend to be different domains. However, if I understand your post, I think I may have a solution.
First of all, I notice that your example map fits very well onto a hexagonal grid. That's quite nice, because it allows you to use a "tile" system very effectively. Basically, after or while generating the map, place all the areas of a "unit" size into a grid of interlocking hexagons. For each face of a hexagon that has an opening through which the character can travel, reset a flag. For each face where there isn't an opening, set the flag. After doing this, notice that all valid paths are characterized by a collection of open faces. In other words, every hexagon along a reasonable valid path (except for the tiles holding the endpoints) contains at least two open faces: one for the character to enter through and one for them to exit through. Find the set of those tiles and there are your nodes. That allows you to use a standard pathfinding algorithm for the low level path and use cubic interpolation of that path if you want to generate a smooth path for the character.
-
So if I get this right, you want to automatically split the map into area's, such that connectivity is preserved?
That is EXACTLY what I'm trying to do.
@Qwerty, implementing the low-level pathfinding is not the issue. Implementing the high-level pathfinding is not the issue either. And generating the map is not the issue either. It's creating the nodes for the high-level pathfinding by dividing the map into multiple sections that I'm having trouble with.
-
That's what I described :P
When you're generating the map, you generate a terrain tilemap underneath. Those tiles with two or more open faces are the nodes in the tree that can be traversed using whatever pathfinding algorithm you have.
-
That's what I described :P
When you're generating the map, you generate a terrain tilemap underneath. Those tiles with two or more open faces are the nodes in the tree that can be traversed using whatever pathfinding algorithm you have.
That's for the low-level pathfinding. I have that part covered. I have the tilemap. I'm trying to divide that tilemap up into larger sections for the high-level part.
-
I remember reading something about it by Pottinger (Age of Empires dev), perhaps here (http://docs.google.com/viewer?a=v&q=cache:tgiI2QjyHdUJ:www.gamasutra.com/gdcarchive/2000/pottinger.doc+pottinger+age+of+empires+paper&hl=en&gl=nl&pid=bl&srcid=ADGEESjoFa60nTxo-_1FoticM3B9Rj8BnlafOV23R4RQNXCkYdMdgQBOzdwqM9r33xVfefpwti_uqZzULie_T4ntV5nyY8-DN4qATO2ZyDdXJDuG_l6bAj2WiYy-dc6z5J_crQCCMLL3&sig=AHIEtbQ2Dd-5bc-BT_LllG1pgEfb3lp-bQ).
-
Hmm this is a pretty complex question, I myself have looked into creating nodes intelligently for a game I was working on a while back. Try something like this, fill the screen with nodes all over the place, and connect them accordingly. Next, remove any redundant nodes. That is, remove any node that does not provide a new field of view from that of a connected node. Also don't remove any nodes that would separate the node tree into two sections.
It would be a bit complicated, and you would probably have to add in some weighting to decide which nodes were better to remove than others, and even possibly fining the midpoint of nodes if they are of equal weight.
Here is two pictures to illustrate what I'm talking about. The first picture is a map filled evenly with nodes, all connected to each other. The second image is one possible generation with all of the other redundant nodes removed.