next »

[JasonPickering]

So I am having trouble making a dungeon generation algorithm. I have done this a bunch of different ways but I am struggling with making the dungeon a very specific way fornthisngane idea. I need long hallways one space wide running left and right and then one space hallways connecting them. Think of it almost like brickwork. I don't need the code so much as just to figure out the logic behind it. I can post an example tomorrow if need be.

[valrus]

Do you want to fill the plane with dungeon (like, say, in an old-school maze game), or do you want a dungeon of a potentially arbitrary shape that merely fits within the plane?

Either way, I think the most fun way of achieving your particular needs would be by running a semi-random cellular automaton, generating the dungeon in a single pass through the grid.  Take for example a dungeon style like this:

XXXXXXXXXXXXXXXXXXXXXXXXXX

XXX XXXXXXXXX XXXXXXXXX XX
XXX XXXXXXXXX XXXXXXXXX XX
XXX XXXXXXXXX XXXXXXXXX XX

X XXXX XXXX XXXXXXX XXXXXX
X XXXX XXXX XXXXXXX XXXXXX

XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX
XXXXXXXX XXXXXXXX XXXXXXXX

That's sort of what you want, right?  Each cell in this dungeon and similar ones can be generated locally in one pass, based on checking the status of a few neighboring, already-generated cells and occasionally consulting an RNG.  (Like if you're in a cell, and the cell above you is empty, and the one to the left of you is filled, you have to be empty.  Whereas if the cell above you or above/right of you is filled, you could potentially be the start of a new horizontal hallway, so consult the RNG.  Rules like that.)

[JasonPickering]

It doesn't need to fill the entire pane, just stay within it. A couple rules I need to follow is vertical hallways are only one space and only t junctions. I don't want any cross sections because it will mess with my controls.

[valrus]

So something like this?  (I'm guessing that you have one button that jumps lanes, so to speak, and don't want the ambiguity of a crossroads, right?)

XXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXX..............XXXXXX
XXXXXXX.XXXX.XXX.XXX.XXXXXX
XXX..................XXXXXX
XXX.XXXXX.XXXXXX.XXXXXXXXXX
XXX..............XXXX....XX <= 2
XXXXX.XXXXX.XXXX.XXXX.XX.XX
XX.......................XX
XX.XXXX.XXXXX.XXXX.XXXXXXXX
XX.................XX1XXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXX

I'm also assuming that you don't want a three-way junction like:

X.X
X..
X.X

Or a dead end like:

XXXXXX
.....X
X.XXXX

(Not that it really matters.  Just for concreteness' sake.  Although no-dead-ends is easier.)

This could also be generated linearly in a single pass.  At each step, you just need to know:

• the values of a few already-generated cells, the left, left-above, above, above-right, left-left, above-above, and above-right-right.  (Those are the ones I can foresee, but there might be a cleverer way to use fewer.)
• the dimensions of the plane, so that you don't start generating a new hallway complex when there's not going to be the possibility of later hallways to connect it up, and know when you have to stop a horizontal hallway.  Like you can't start a new hallway at (1) or else it will be stranded; there's got to be a margin where the normal "go ahead and start a hallway" rule can't apply.
• the parity (odd or even) of the current row.  If you always do horizontal hallways on odd rows, then even if you start a new hallway complex out to the east (as in 2) and later run a horizontal hallway over to it, they line up properly.  Otherwise there's the chance you get a multiple-square-tall vertical or horizontal hallway.
• the column number of the last empty cell in the previous row.  You need this on odd rows, so that you don't cease extending a horizontal hallway before it joins up with the last vertical hallway of the previous row.  (This is inelegant and eliminates some otherwise entirely ok layouts, but I can't think of an easier way to guarantee that all generated hallway complexes join up, not without rules that constrain possible layouts even more strictly.

Anyway, that's a fun exercise, I enjoyed it. Let me know if you want the specific rules for the layout style above.