Map generation

This is a discussion on Map generation within the Game Programming forums, part of the General Programming Boards category; I am writing a game containing a randomly generated map. It would consist of a map with rooms, each having ...

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    6

    Map generation

    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!

  2. #2
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704
    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.
    Code:
    // 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.
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    6
    Thanks! I shall give this a try when I get home!

  4. #4
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704

    Spoiler!!

    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:
    Attached Files Attached Files
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  5. #5
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704

    Spoiler

    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.
    Attached Files Attached Files
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  6. #6
    Registered User
    Join Date
    Oct 2003
    Posts
    6
    Thanks, I'l try this too!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Adding a Map to a program
    By Shogun32 in forum C++ Programming
    Replies: 1
    Last Post: 05-04-2009, 10:42 AM
  2. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 09:32 AM
  3. Creating a map engine.
    By suzakugaiden in forum Game Programming
    Replies: 11
    Last Post: 06-21-2005, 06:06 AM
  4. the effects of textures on my frame rate
    By DavidP in forum Game Programming
    Replies: 37
    Last Post: 10-03-2003, 12:24 PM
  5. Searching STL Map Inside STL Map Object :: C++
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2002, 09:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21