4
\$\begingroup\$

Do you have any idea how to extract graph data from this type of procedurally generated level?

enter image description here

Well, actually we need to analyze only top level (gray). Background (black) does not matter. What I am looking for is a way to statistically analyze such type of generated maps. For example how much isolated areas I have (it's not hard, I know), how much branches in each area I have and which areas has exit.

Do you remember any algorithm or math instrument to do that? Memory does not matter, algorithm complexity does not matter too. It's not runtime task.

P.S. A desired result can look like this:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ This smells like an XY problem. What are you trying to achieve with the graph? \$\endgroup\$ – congusbongus Mar 14 '17 at 4:27
  • 1
    \$\begingroup\$ Going from tiles to graphs seems hard. Computer vision algorithms might be useful (maybe straight skeleton or medial axis). If it's your procedural generator you might be able to go the other direction. Generate the graph first, and then the pixel/tile data from the graph, so that you don't need to recover the graph. \$\endgroup\$ – amitp Mar 14 '17 at 5:28
  • \$\begingroup\$ @congusbongus I can generate a bunch of these levels and I need to select "most interesting" ones from them. It means they have to be 1 or more "exits", as much as possible areas with much as possible branches. I could also select levels with given characteristics like number of exits or longest direct way. \$\endgroup\$ – Epsiloncool Mar 14 '17 at 12:21
  • \$\begingroup\$ @amitp Thank you! The medial axis algorithm looks like exactly I need! I will run in this direction. \$\endgroup\$ – Epsiloncool Mar 14 '17 at 13:36
5
\$\begingroup\$

Here's something you can try. First, take a map like this:

map

Record the distance from the edge distance of each empty cell. You can do this iteratively using cellular automation. I've used Manhattan distance but you can use others, although I think your choice affects a few of the following steps.

distances

Find the cells that are more distant than all their neighbours, a.k.a. local maxima. Mark these as peaks peak.

peaks

Find all the cells that are at least as distant as all their neighbours. I guess you can call these ranges range; they form groups that are local maxima for the most part.

ranges

From here you can connect most of the ranges range to peaks peak or other ranges range by looking at their neighbours and hill climbing; these will form ridges ridge.

ridges

You might notice that not everything is connected, particularly on the right part at some narrow passageways. You can connect them up by finding such passageways and hill climbing away from them; eventually you'll reach a range or peak. Here's one way to identify these: find cells that are:

  • neighbours
  • have minimum distance from the edge
  • have opposing directions of ascension

For example, given this group of four cells:

group4

The top-left cell can ascend to the left, and the top-right cell can ascend to the right and bottom. Since left and right are opposites, those two cells form what you might call a col col. Similarly the top-left and bottom-left cells are also opposites and part of a col. Just like with the ranges, you can hill climb ridge to connect the cols to the rest of the graph (if they weren't already).

cols

That's it; you should have connected graphs for each contiguous area. You can convert the peaks peak, ranges range and cols col into nodes, and the connecting ridges ridge into edges, for graph analysis.

graph

You also have some metadata to play around with; the distances of the peaks and ranges represent how wide those areas are, and cols tend to be choke points.

I'm not familiar with the various Computer Vision algorithms for finding topological skeletons (like straight skeleton or medial axis), but the general idea seems to be the same.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.