Friday, March 23, 2012

Something in the Way

I put in some changes to door placement code, which has stopped hallways from being blocked at the source.  However, the general issue of existing hallways blocking where other ones need to go persists.  This is an artifact of the discrete nature of the grid -- while it may be true that I have a planar graph layout,  so that rooms can be connected without hallways crossing, there's nothing to guarantee that the hallways actually have enough room.

Currently I've got it taking a trial-and-error approach with different pairs of door locations for each hallway.  This works out in a larger number of cases (I've had it generate reasonable levels, some of the time at least, for 5 or 6 rooms), but past a certain point of complexity it just gets stuck in a hopeless state and runs forever.

Improving on this situation is a significant challenge; I'm still thinking of what I want to try.  One thought I've had is to change the A* heuristic to discourage hallways clustering around rooms.  This would particularly address a situation I commonly see where a hallway wraps tightly around the perimeter of a room, blocking most possible door locations for other hallways yet to be routed.  However, it's clearly a band-aid idea, and I'm not sure it wouldn't create problems when rooms are close together (currently the levels are quite spread out, another matter I hope to address in due course).

What I'd like to do more ideally is let the hallways "shove" each other around until they fit.  I'd like to be able to treat the grid as a rubber sheet and just stretch out new areas when I need more room.  It sounds like a good general solution, if I can manage to implement it reasonably.  I expect deforming existing dungeon features without messing up structure to be pretty hairy, though.  Going to ponder this one for a while.

In a way, the existing approach is a simplified rubber sheet.  Having chosen a particular scaling factor and failed to lay out the level within that size, it bumps up the scaling factor and tries again until it succeeds (or enters a quagmire).  At first blush it would seem that this solves the problem, albeit gracelessly, since if you expand endlessly there should eventually be a big enough gap wherever you need one.  However, since it re-routes every hallway after it re-scales, the same exact situation can simply occur again because it will just hug the corners that much tighter.  So, something more sophisticated is called for.  I'm still convinced it's tractable, though.


  1. Stretching and shrinking dungeons reminds me of a method for shrinking pictures without shrinking the salient features. What they did was remove pixels in a path from the top to the bottom that avoided as many important things as possible. The path could jig from side to side as long as it was still connected diagonally.

    You could do the reverse of this very easily to allow stretching without messing up features.

  2. Oh, that's pretty clever. I had thought about removing vertical/horizontal strips where possible, but what you suggest is a lot more flexible.

    I'd have to overcome some architectural barriers to make something like that happen, since I don't quite have the full level graph laid out in a useful form at the point in time when I'd need it. I reckon it's doable, though. I might, though, start by focusing on just getting the things to be closer together to begin with, rather than trying to fix it up after the fact.

    Thanks for your interest and comments, by the way! I wanted to respond to that first comment you made and thank you for being the first follower of this blog, but I didn't come up with anything to say that time. :)