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 [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][E][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] S is starting point, E is ending point. now suppose that there is one exit in S to the north: [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][*][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][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: [ ][ ][*][ ][ ][ ][ ][ ][ ][ ]
[ ][*]
[*]
[*][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][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

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

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

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.