Sunday, March 25, 2012

Hallway Headway

I've made a satisfying bit of progress tonight on this hallway layout problem.  Here's an example of an 8-room graph it's doing well with now:

The key improvement that got me to this point was to reuse some intermediate values from the layout algorithm to help me choose the best order in which to draw things.  The rooms are gone through in planar canonical order, which guarantees that vertex k+1 is on the external face of the subgraph with vertices 1..k; this ensures much easier edge-drawing.  Furthermore, there is a representation called a "planar embedding" that lists the edges for each vertex in clockwise order.

By following these two orderings, I got a lot of hallways to stop running into each other, wrapping around rooms, and hogging space in weird ways.  Oh, I also changed the A* heuristic from Euclidean to Manhattan distance, which helps avoid wall-hugging and gives a more organic feel overall.

There's still a ways to go, I'm pretty convinced of that.  I tried a 10-vertex graph similar to the above, but that seems to be asking too much.  I'm increasingly thinking I'll go ahead and invest the time in a realtime display of level generation in progress, so I can see what's going on rather than trying to guess what goes wrong based on looking only at successful levels.  Should be fun to watch, too.

I'm also considering moving away from the Chrobak-Payne straight line drawing algorithm for layout, most likely in favor of going back to Fruchterman-Reingold force-directed layout I was using earlier.  The Chrobak-Payne output seems a bit too regular to give a satisfying sense of randomness.  It has a characteristic triangular shape, which leaves a lot of space unfilled, and there's always that long straight hallway at the top between the first two rooms.  Of course, I could imagine ways of fudging around that (e.g. put in dummy rooms and don't include them), but I think I'd like to see what my other options look like at this point.  A different choice of layout strategy could even turn out to make hallways route more cleanly, so it's an opportune time to consider it.

Oh, I also found an interesting paper that seems very applicable to this problem, discussing a method for drawing planar graphs with vertices and edges that take up space rather than being infinitesimal.  I'm still mulling over their algorithm, but it's nice to find some relevant recent work.

No comments:

Post a Comment