2
\$\begingroup\$

I'm new to game development, but I'm trying to figure out a good algorithm for positioning rectangles (of any width and height) in a given surface area, and connecting them with any variation of lines. Two rectangles will never have more than one line connecting them.

Where would I begin working on a problem like this? This is only a 2 dimensional surface. I read about graph theory, and it seems like this is a close representation of that. The rectangles would be considered a node, and the lines connecting them would be considered an edge in graph theory.

\$\endgroup\$
  • \$\begingroup\$ Clippit voice: It looks like you're writing a roguelike dungeon generator. We have this similar question and RogueBasin has a detailed tutorial. (If that's actually what you meant to ask. Is it?) \$\endgroup\$ – Anko Aug 23 '14 at 20:50
  • \$\begingroup\$ Kind of. Although rather than a random map, I want to retrieve the already stored data and draw it. So I will store the width and height of each rectangle, and then store the links between them, storing the source rectangle and target rectangle. \$\endgroup\$ – MacGyver Aug 25 '14 at 15:17
  • \$\begingroup\$ That indeed sounds like an undirected graph, which makes me think you might want a graph layout algorithm. I'm still fuzzy on the details though: Are these rectangles different sizes? Does it matter where the edges connect with them? \$\endgroup\$ – Anko Aug 25 '14 at 21:12
  • \$\begingroup\$ Well, they are directed, because the lines have arrows of which way to go. Yes, they are all different sizes. \$\endgroup\$ – MacGyver Aug 26 '14 at 2:40
  • \$\begingroup\$ No, it doesn't matter where the edges connect. \$\endgroup\$ – MacGyver Aug 26 '14 at 3:05
1
\$\begingroup\$

It sounds like you are looking at an unusual problem for games: given a bunch of rectangles with connecting edges, lay them out so that no rectangles or edges (I'm guessing) overlap. Usually the layout happens during map generation, which means it's trivial.

The general problem, of laying out a planar graph with a set of goals (minimise overlaps, edge lengths as even as possible) is a major field of study within Graph Drawing. People write papers on this stuff, and that may be cool, but might be a bit heavy for someone new to game development.

Therefore I suggest you take an existing graph layout algorithm, and modify it to include the rectangle overlap criterion. Depending on how well you want to do it, it might be trivial, or you might need to dive into the bowels of the algorithm.

Keep in mind that you are by no means guaranteed no overlaps; recall the three utilities puzzle that has no solution (but never fails to confound the internet).

Here's one way you could do it; one of the simplest graph layout algorithms to understand are force-directed ones - they simulate the graph as nodes that repel each other and edges that are spring-like and try to become as short as possible. There's even an open source javascript version called springy.js here (GitHub, demo):

springy demo graph

You could do one of two things with this:

  • Add edges with lengths long enough to guarantee the rectangles don't overlap. You may end up with a very sparse layout if you have elongated rectangles, however.
  • In the tick function, add a function that applies a large repelling force if you detect that rectangles overlap.

Unfortunately, classic force-directed graph layout algos don't resolve edge overlaps well. Fortunately due to its dynamic nature, it's sensitive to initial conditions, so you can run the algorithm repeatedly until you get a nice result.

\$\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.