Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I came up with a method for recursively generating simple dungeon maps by starting with one room and recursively connecting new adjacent rooms randomly to it.

Maps are represented as two dimensional arrays where each cell contains a value of 0-15. 0 represents no room while each direction is represented by north=1, east=2, south=4, west=8.

I wanted to start with a single non room ([[0]]) and then expand the 2d array as necessary to fit the generated map. The difficulty I face with this tree like recursion is that if the arrays have to be unshifted to add rows and columns to the left and top of the map, I have to adjust the current position of the function, what row and column it is at. This makes it so that separate branches are not aware of array index adjustments from other branches, only their child functions will know because they have the adjusted position passed to them as their row and column arguments.

Is there a way to do this? I tried storing row and column offset values outside of the recursion, but it did not work for some reason.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

Is there a reason you must use a 2D array, or would some a hash table or other kind of map work? Then the x,y indices just continue into negative space, but it doesn't matter.

If you're concerned about memory or CPU speed, 1) Don't be, hash tables are very efficient at things like pairs of dense integers, 2) you can build the level in a hash table and then post-process it into an array once you know the final size.

share|improve this answer
    
so the hash function would accept an x and a y argument and this would be mapped to basically an associative array with keys like 1x1, -1x3, etc? –  user4820 Jan 23 '11 at 11:06
    
Yeah. In C++ I'd just use an std::pair<int,int>; in Python, a dict with (x,y) tuples for keys. I'm not sure what language you're using. –  user744 Jan 23 '11 at 13:43

I'm doing a similar thing, in Python. (Or at least the elastic part).

I have a dictionary of (x,y) tuples mapping to the cells. In pseudo code:

map = dictionary( (0,0) : cell at (0,0), (1,0) : cell at (1,0) ... (2, 2) : cell at (2,2)
getCell(x,y):
    return map[(x,y)]
    catch error if out of bounds:
         map[(x,y)] = new cell and return

A hash table would be very good for this kind of thing.

share|improve this answer

The minimum effort solution is to pick a maximum size (X and Y extent) that you want the dungeon to reach, put your starting point in the center of that, and don't allow growth outside of it. No need to do any shifting. Depends on a fixed extent being acceptable, of course.

share|improve this answer

You would want to use a graph instead of the 2D array.

Each room would be a node in the graph and knows which other rooms are adjacent to it:

Room {
    long x;
    long y;
    List adjacentRooms;
}

That way you don't have to define how large your map can become.

The x,y-Coordinates can be used as unique key in a hashmap for fast access to each room. Adding a new room would just add entries to the adjacentRooms lists of the rooms close-by.

The graph is also great for path finding algorithms, if you need them.

share|improve this answer
    
This will perform poorly and require much more bookkeeping than a hash table or array. There's no benefit in the rooms having both an X,Y hash key and forming a directed graph. –  user744 Jan 23 '11 at 13:45
    
How would you do fast access of rooms with only the directed graph? How would you do path finding with only an X,Y hash key? This would require additional logic to determine the adjacent rooms. The hash key is really just another view of the game world. I agree that handling a graph is more trouble, but will benefit algorithms using the graph. Performance depends on the size of the game world. So this has to be prototyped. Thx for the down-vote. Cheers! –  Stephen Jan 23 '11 at 14:41
    
Nothing in pathfinding precludes using a hash of X,Y pairs. Successor states are successor states, it doesn't matter if you maintain a crazy graph or look it up on a hash table, except that the hash table is faster and uses less memory. –  user744 Jan 23 '11 at 17:56
    
The hash key solution is less abstract. As I wrote before the pathfinder must know which rooms are adjacent to each other, how to calculate the distance to the target room etc. You would put knowledge about the game world into your pathfinding algorithm. If the setup of the game world changes e.g. movement from rooms which are diagonal to each other is permitted or a third dimension is added, you would need to change every algorithm accessing the game world. Graphs abstract this away. Nothing crazy about it. There are always drawback to every solution. –  Stephen Jan 23 '11 at 20:24
1  
"Graphs abstract this away." So does any iterator, generator, coroutine, or list-building method, and they don't require O(n) structure bloat nor more build-time bookkeeping. –  user744 Jan 23 '11 at 21:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.