Map generation

[Trig]

I am writing a game containing a randomly generated map.

It would consist of a map with rooms, each having one or none of the following : - An east, west, north and south exit.

Not all the potential rooms in say, a 10*10 grid, would be used, but whichever ones are need to be connected.

I currently have some AWFUL code written to make the map (too long to post here, but I may attach it tommorow if I remember to bring it in).

It basically creates a room, then an exit, then a room in that direction (if possible, i.e. it is not at the boundaries). Then it creates an exit between the two, then loops and starts on the newly created room.

If a room has no valid exits, a random, already existing room is chosen, and the loop starts again.


I doubt any of that made sense, please ask if it needs clarifying.

Is there a better way than this?

Thanks!

[Jeremy G]

I dont know if this is a better way....


Start by creating your 10*10 grid.

Use a basic nested for loop to traverse your grid

At each grid intersection, generate a random number

Based on the biase(explained later) set the grid status to room*
----------------------------------------------------------------------------------

Re-use the basic nested for loop to traverse your grid once again

This time, at each intersection check the left, right, top, bottom neighbor.
:If any intersection has a status room-and has no neighboring rooms randomly pick one of 4 directions neighboring intersection and make it a room and continue through the loop
:If any intersection has a status room-and has at least one neighbor do nothing and continue through the loop
:If any intersection has a status of not a room - leave it alone and continue through the loop

REPEAT until all rooms have at least one neighbor - this insures you can move to every room in the grid.
-----------------------------------------------------------------------------------

Re-traverse your grid one last time, configuring each intersection with status of room to have its exit(s) point to the next neighbor.
-----------------------------------------------------------------------------------


I think that algorithym should work out for you. I actually just thought of it when reading your post--Im about to go code it to see how it actually works.

More on the bias:
Basicly a seed value that determines how "full" a grid will be of rooms. The random number generator my always be from 1 to 10, and an example bias might be 4. Every time the random number is 4 or below, the intersection is made a room. etc.
Unfortunatly due to the random nature of room creation in the continuity part of the algorithem (second section) this density setting may be fruitless. Perhaps you might want to use a better more intelligent method of connecting broken rooms.


by setting the intersection status-i was implying you would have a 2d array of mapPoints.

// example struct
struct mapPoint {
     bool status; // 0 - not a room, 1 - room
     exit north;
     exit east;
     exit south;
     exit west;
}
struct exit {
     int x;    // grid value
     int y;    // grid value
}

Hope that is clear enough to get an idea that works for you.

[Trig]

Thanks! I shall give this a try when I get home!

[Jeremy G]

I took a crack at it myself. I like it a lot.

Caution, the file I have attached has takin my suggestion and realized it. If you wanted to figure out the code for yourself dont view it yet!!


This code generates the random dungeon. Actually the code should be seeded by using getSystemTime or some other method to randomize the dungeon - other wise it creates the same one over and over :P

Theres a problem with the map creating islands of inaccessable land, I described the problem in detail in the code, and offered a possible fix--which I will be coding and posting a little later for the fun of it.

Heres the solution thus far:

[Jeremy G]

Wow, that took less time then i thought.

Well the fix kinda works. Theres still a possibility of getting islands, for the most part it links everything together.

Unfortunatly a lot of "rooms" are made for the linking. So it might be a good idea to make only rooms created on the initializing pass (.pass == 0) to have any special meaning.

[Trig]

Thanks, I'l try this too!