CODEWITHSUNDEEP
arraysgraph-algorithm
user1300214
user1300214

Reputation:

Converting a graph structure to a 2d array

I'm looking at automatic dungeon and dragons style dungeon creation although not as advanced as those you can find on the web. Ultimately I want an N by N grid, say with 1's for walls 0's for pathways and open spaces, and so on. I'm able to randomly generate a graph structure which represents the connectedness of the dungeon and size of each space. But I want to convert the graph structure into a 2d array as described. I'm not fussy about how the rooms and corridors appear so long as there are no crossings and it's reasonably compact.

My question is are there any known algorithms to do this?

Upvotes: 1

Views: 696

Answers (1)

D. Law.
D. Law.

Reputation: 244

Short answer:

Yes, there are known algorithms.

Long answer:

They type of algorithm you are looking for has a few parts.

Planar Graphs

The type of graph that you can embed into a grid is a planar graph. A planar graph is a graph that can be drawn on a flat surface or plane. The first step of you algorithm has to be to check to see if your graph is planar or not. In the link above are some ways to check if your graph is planar. If your graph is non-planar you cannot draw it without intersections. This may be a downfall for your random generator.

Embedding Graphs

This link references a paper on embedding graphs in an n by n matrix. It does not exactly match your request, but you can manipulate it post-embed-algorithm to fulfill your needs by replacing each vertex with the largest rooms n by n area. Now this algorithm is probably not the most compact possible given its nature of a straight line, but that leads me to your final request of compactness.

Packing Problems

Packing problems have varying difficulties. From the initial sounds of your problem, yours falls into the harder category, especially since you have the whole corridor linkage making it even more difficult. This problem can be np-complete/np-hard with no efficient algorithm, so stopping at the above step may be the most resonable. Check out the the wikipedia on packing problems to look into your specific case to determine if you want to spend time making it more compact.

Upvotes: 1

Related Questions