Author Topic: Dividing a map into sections - Help!  (Read 5521 times)

0 Members and 1 Guest are viewing this topic.

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Dividing a map into sections - Help!
« 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:


-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.
« Last Edit: August 31, 2011, 08:30:36 pm by ZippyDee »
There's something about Tuesday...


Pushpins 'n' stuff...


Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #1 on: August 31, 2011, 09:04:26 pm »
So are you pretty much looking for a way to get from point A to point B in a kind of maze of "rooms" ?

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #2 on: August 31, 2011, 09:36:20 pm »
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.
« Last Edit: August 31, 2011, 09:36:52 pm by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #3 on: September 01, 2011, 07:39:50 am »
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.
« Last Edit: September 01, 2011, 07:55:07 am by ZippyDee »
There's something about Tuesday...


Pushpins 'n' stuff...


Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #4 on: September 01, 2011, 02:02:52 pm »
So if I get this right, you want to automatically split the map into area's, such that connectivity is preserved?
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #5 on: September 01, 2011, 04:36:20 pm »
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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #6 on: September 01, 2011, 05:09:08 pm »
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.
« Last Edit: September 01, 2011, 05:19:17 pm by ZippyDee »
There's something about Tuesday...


Pushpins 'n' stuff...


Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #7 on: September 01, 2011, 11:17:56 pm »
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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #8 on: September 02, 2011, 03:24:45 am »
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.
There's something about Tuesday...


Pushpins 'n' stuff...


Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #9 on: September 02, 2011, 01:42:44 pm »
I remember reading something about it by Pottinger (Age of Empires dev), perhaps here.
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Dividing a map into sections - Help!
« Reply #10 on: September 02, 2011, 03:02:04 pm »
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.