# Convert 2d generated level to graph or analyze

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

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:

• This smells like an XY problem. What are you trying to achieve with the graph? Commented Mar 14, 2017 at 4:27
• 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. Commented Mar 14, 2017 at 5:28
• @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. Commented Mar 14, 2017 at 12:21
• @amitp Thank you! The medial axis algorithm looks like exactly I need! I will run in this direction. Commented Mar 14, 2017 at 13:36

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

Record the distance from the edge 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.

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

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

From here you can connect most of the ranges to peaks or other ranges by looking at their neighbours and hill climbing; these will form 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:

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 . 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 to connect the cols to the rest of the graph (if they weren't already).

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

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.