OSDev.org

To pass boredom of class, I'm writing a roguelike during it, using C++. Now I've stumbled across the biggest challenge of it: The random dungeon generator.

The algorithm I had yesterday didn't quite work. It wasn't quite possible to make correct corridors. I've changed to an algorithm where I first place a room, place random doors, from each door placed, draw a corridor... and that's where I'm stuck.

After the corridor's drawn, it should check if there's place to place another room, then place it, or add a turn in the corridor (which eventually should end in a room, anyways). The level should have at least two rooms, too.

That part in the algorithm's something I'm stumped at. If any of you have any suggestions, I'd be very grateful

go here
http://roguelikedevelopment.org/

then pick MAP on the side...

I have written several in my roguelike writings (you can get OLD version of underdark off my site)...

my version creates non circular dungeons. eg: you can get dead end corridors, sometimes halls link back, sometimes they dont etc...

mostly I

generate a room of random size... pick random wall.. pick random position along wall.. check to see if I can create corridor, do so.. and then %% decide if i want to create corridor from that end point or a room at that end point or nothing at the end point...

loop...

generate a random number of rooms...

creating a roguelike is actually really hard...
also, build saving in RIGHT AT THE START, otherwise it will be VERY hard to add it later on...

there is some newsgroups dedicated to RL development too, which are good (you can find me on there sometimes)..

Already visited Roguelikedevelopment, and already got Underdark. RLD helped me on the way of getting a decent algorithm (I first tried doing it in steps, first step being adding all the rooms, second step getting me in a knot, which's adding the corridors) A random amount of rooms'd work, if I'd build in checking if the provided space's big enough to place the new room.

As for the saving... that'd be writing both the player-object and the map-object, together with all the monster-objects to a file, right?

underdark source is old and nasty...

saving would be, player, monsters, maps, items, etc etc etc...

an RL is a complex thing to try and OOify.. the interactions and such... its a nasty hot topic on rec.games.roguelike.dev all the time..

The random dungeon's already tough enough for me. It keeps freezing from time to time. Already managed to get rid of alot of endless loops in certain occasions, but can't find anything else anymore, yet it acts pretty weird. Sometimes, when there ought to be 8 rooms or 5 rooms or so, it'll show only 1. Also, it'll freeze, like an endless loop, while all possibilities for endless loops're already taken care of (or so I think)

I think I'll take care of that first, before saving'n such. Code's turning out pretty messy, too ::)

Ah, smells like a bad case of design-while-coding...

I learned the hard way that about the only way to get a complex algorithm "right" is to completely draft it on-paper using anything but source code. When you think you're done, start implementing it. When you hit a point where your on-paper design doesn't "suit reality", stop editing your sources and return to the drawing board. Never implement something that isn't drafted on-paper.

It's far too easy to get tangled up in spaghetti code and losing sight of the algorithm's workings.

Moreover, how about adding assert() statements in crucial places, and possibly some similar function wrapped by [tt]#ifndef NDEBUG[/tt] that prints trace information to screen to tell you where the algorithm chokes on which data?

That's what I've been doing, and worked some bugs out (like a -1 index number in a double array, and parts of the algorithm getting the entire thing stuck). The trouble is... what now is being an @$$, isn't traceable anymore. I think it really is best to redesign the whole thing.

What I had in mind, was keeping track of first placing all the rooms, with the doors per room, then check which door's the closest, and which's preferably not from the same room. Dunno 'bout this, though. It'll be overly complicated for something that, in the end, would have a simple, elegant solution.

Right now, I'm doing it the way I've seen on Roguelikedev.
1) Get a random amount of rooms (between 2 and 10)
2) Take a random spot on the map
3) Calculate a random width and height (both > 3 and < (MAX_X-x) or (MAX_Y-y)
4) Draw the room on the map and add 1 to the counter of rooms added.
5) Run through each wall and place a door when the randomizer hits it (Kind of like roulette. Usually leaves a good variety of doors set), each door'll increase a counter. The loop stops when this counter > 0
6) From one tile aside the door (outside of the room. This's checked too, based on which wall the door's placed on), randomize a direction to take a corridor to (but not back into the room)
7) Randomize a number of tiles for the corridor, between 1 and the edge-1
Keep adding as many tiles in the direction of the corridor as specified, or until it hits a wall
9) Go one further (or stay on the spot if it hits a wall)
10) If the counter of rooms added's not equal to the total amount of rooms, go back to 4 (after justifying x and y to fit on the map. Can't have out-of-bound rooms)

to get a good start, what you can do is,

have an array of say, 100x100,

and turn it into a 5x5, of 20x20's.

pick first grid (q1), randomly pick where to put a room. move to next grid (q2). random place a room.. now join the two together, pick place on right wall in q1, go right some.. then go up or down some.. then go right some.. etc.. and join into the left wall in q2...

continue so you have a loop.. then you can pick rooms in the top row and if you like, join into the bottom row..

this way you dont get clashes when placing rooms, since you know onl1 quad can have 1 room.

sure it makes circular maps, but its a start, and a nice and easy start!