Archived

This topic is now archived and is closed to further replies.

Codejoy

random map generation for rooms in a 10x8 grid

Recommended Posts

Suppose I have a map that is 10x8 squares big, each square is a room, there are 15 room types that denote the possible exits based on the directions: north, south, east, west. I.e. the room type 0, has exit north, roomtype 1, exit north and east, room type 2 exit north and south, roomtype 3 exit north and west, then of course room type 4 would have an exit east and south, etc... I store all the room types that make up the dungeon in a map thats a int map[80]; (stored linearly). So that means the top left room space is 0, and th bottom right room space is 79. So what I need to do, is randomly generate a map, where I know the start position, it is possible to get anywhere else in the map, if not with a few twist and turns.i.e. id like u to say start in the center (about 5,4) in the game screen (where each of the 8 rows of 10 columns each represent where a possible room is, (imagine a blank square)...but the starting room 5,4 is where u start, its randomly selected to be one of the above types, that is have one or more exits) then from there the map is generated where u can get to the exit in the dungeon (some other square), and perhaps every square inbetween for sure...to maximize the used space of the dungeons total area.... hmm let me try a graphical represnetation [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][S][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][E][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] S is starting point, E is ending point. now suppose that there is one exit in S to the north: [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][*][ ][ ][ ][ ][ ][ ][ ] [ ][ ][S][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][E][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] First possible move is represented by star, then suppose that there is exits north, south (again) and to the left and right...and so: [ ][ ][*][ ][ ][ ][ ][ ][ ][ ] [ ][*][*][*][ ][ ][ ][ ][ ][ ] [ ][ ][S][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][E][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] * Possible moves again. So i want the algorithm to give a starting point (at random) and ending point (at random) and then be able to create a compeling dungeon of interlocking rooms to get the player from S to E with some exploration in between, im mean looking above obviously from S ud go up, then right to try to get closer to E, but there could be a nifty path of rooms to the up left, down down down left, down down down where ultmiatly there is a cool item. Is there anyway to create such an algorithm to do this? i mean at its most basic its just filling out an int map[80] with numbers that range from 1-15 representing the room types, it just has to be smart to give each room an entrance and an exit to the other, i.e.. if u have S where there is an exit North, then to the north there MUST be a room that has an exit South to get back to where u were. *woo* I hope that covers the question I have in detail. Thanks for any algorithms, or ideas to how it might be approached to solving this. Thanks, Shane

Share this post


Link to post
Share on other sites
I guess the best method would be to make an algorithm, that would generate a path between the two rooms. The could be a degree of randomness in how this works. Basically you decide what quadrant one room is with respect to another... either NE, SE, SW, NW... then measure how many rooms in either two perpendicular directions you need to move. Then generate a path that permutes these movements in a random order...eg

East, South, South, East or
South, East, South, East etc.

with a chosen route, you go from start to end, adding the direction to both rooms (ie if the route is south... add a south exit the current room... and a north entrance to the next room).

When this basic path is added... you can make a set of transformations that can add (1 room at a time) exits from the correct path to adjacent rooms. The number that are added can be controlled to make a more, or less "complex" map. I''m sure you can come up with some more complex transformations on the map to allow for a more interesting journey (such as blocking the primary path, and adding a patch path parallel to it). I''m not sure how efficient htis would be... but I assume this map would only be generated once per game... so it shouldn''t be a problem.

Not sure how useful this is.. but I saw no replies, and thought I''d have a go

Share this post


Link to post
Share on other sites
thanks for the reply, yep no replies i figure its not as easy as that, it sounds like your method actually adds in the exits somehow, from what i gathered at least...ill have to reread and think more later after i havent been coding all day as my brain is fried

thanks for the reply
Shane

Share this post


Link to post
Share on other sites
If your maps are small / pregenerated, there''s always the easy brute force choice. Simply generate a map of random rooms, then use a path finding algorithm (of which there is lots of information on the web) to make sure the map is ''valid'' (no gaps / doors that don''t match up, the map is traversable from start to finish, ect..). A 10x8 grid would be no problem, on the other hand if you''re planning to scale this up to a larger size (say 1000 x 800 grid) you''ll find it rather inefficient. The pros are that the maps generated will be extremly diverse. I used this method once for a random maze generator for a school project, so it does work quite well.

Share this post


Link to post
Share on other sites
start with a grid of rooms with no doors. assign each room a "sector number", which is just an integer that is unique (you can even number them {0,1,2,3,4...}.

then, do the following in a loop for each room:

randomly pick a direction (north, south, east, or west). if the next room in that direction has a DIFFERENT sector number, knock down that wall, and set the sector number of all rooms with the second room''s sector number to the first room''s sector number.

i.e. say it picks "south". the secotr number is 4, and the sector number of the room to the south is 17. knock down the wall between, and set all rooms with sector numer 17 to have sector number 4.

repeat this loop until ALL rooms have the same sector number. at this point you will have a maze where there is exactly one path between any two rooms. you can knock down additional random rooms if you want multiple valid paths.

i do not remember who told me about this method on gamedev.net, or i''d give them credit (sorry whoever that was). but, it works nicely to generate random mazes.

Share this post


Link to post
Share on other sites
in addition, if you want "large rooms" in the maze (i.e. bigger than one grid square, as the previous algorithm generates hallwal-type mazes), you can first knock down the inner walls of any number of rectangles (for the large rooms), and assign all of the grid squares in each rectangle the same sector number. then, follow the previously outlined algorithm to connect them with hallways.

Share this post


Link to post
Share on other sites