4 replies to this topic

[IceMetalPunk]

I'm practicing for the Jam (in case I actually have time to create something for it!) by tackling arbitrary programming challenges. The one I'm working on now is a type of procedural generation that creates a number of rectangular rooms in a building (all assumed to be the same size, 32x32, for now) and generates the building's layout. It does this by connecting rooms together at their edges, and also adding new floors at random (and connecting the new floors to old ones with stairwells).

The problem I'm having is that the generated buildings aren't correct when I actually place the room instances. They lack stairwells (which should be created whenever a new floor is added) and more rooms are generated than I've actually specified (I run the room addition code 20 times, but get arbitrarily more rooms in the final result).

You'll need a bit of information about the structure of the layout, I suppose.

• Firstly, each floor is a different value in a map, where the key is the floor number. I figured this would make it more efficient since I'd only need one floor at a time, and finding a floor in a map is O(log n).
  
• The floors themselves are stored as ds_lists, with each entry in the list representing either a room or a stairwell.
  
• Rooms and stairwells are ds_maps. They have a key called "type" that identifies whether it's a room or a stairwell.
  
• Rooms have a key called "floor" that indicates which floor the room is on, and a key called "connections" that is a 4-element ds_list specifying the other rooms and stairwells it's connected to. More details about this below. They also have a list of "invalid" rooms, that is, rooms which it can physically not connect to at any time in the future (though this is irrelevant to the problem at hand).
  
• Stairwells also have "floor" and "connections" keys. The "floor" is the lower floor it's connected to. The "connections" is a ds_list with only two elements, which are the room it's connected to on the lower floor and the room it's connected to on the higher floor, respectively.

A little more detail about the "connections" list of a room: a room can only have at most 1 room or stairwell connected to each side, meaning 4 connections maximum. The connections list holds the ds_map ID of the connected rooms to the North, East, South, and West (up, right, down, left) respectively. Where there is no connected room, a -1 is used instead of an ID.

Whew. Now that all that information has been explained, here's the problem: given all that structure, how would I go about drawing the layout of the building? For simplicity, let's just assume I'm only drawing one floor at a time. How can I figure out the relative positions of the rooms given their connections?

I first tried a basic depth-first search, placing a room object whenever a room was popped off the stack. While that showed some nice room layouts, it also showed some problems. Firstly, even though I used repeat(20) to add exactly 20 rooms, I'm somehow showing more rooms than that being generated (in arbitrary numbers; one time I had over 50, another time I had 38). Secondly, stairs don't exist. I know the stairwell creation code is being executed, yet when the room objects are created, they all have type ROOM and none have type STAIRS (even though there are several floors to the generated buildings).

I don't know if the problem is in the way I'm doing my DFS or if it's actually in the underlying data structures, so any help would be nice.

Here's all the code I'm using:

InitRooms() - Initializes variables used for the building generation

Spoiler

global.minfloor=0; /* The lowest floor created. Negative numbers indicate subterranean floors, while 0 is the ground floor. */
global.maxfloor=0; /* The highest floor created. */
global.floors=ds_map_create(); /* The map containing the lists of rooms in each floor. */
global.buildup=1; /* Whether we can build upwards or not (create a room on floor maxfloor+1). Becomes 0 when all rooms on the highest floor have no space for stairs. */
global.builddown=1; /* Whether we can build downwards or not (create a room on floor minfloor-1). Becomes 0 when all rooms on the lowest floor have no space for stairs. */

AddStairs(lowFloor, highFloor, room) - Adds a stairwell to connect the two floors, always connected to the given room. Returns "false" if there is no place for a stairwell between these floors.

Spoiler

var rm, lower, upper, checkcon, stairs, p, check, checkflr, flrlist, valid, connections;
lower=argument0;
upper=argument1;
rm=argument2;

stairs=ds_map_create();
connections=ds_list_create();
ds_map_add(rm, "type", TY_STAIRS);
ds_map_add(rm, "floor", lower);
ds_map_add(rm, "connections", connections);

if (lower==ds_map_find_value(rm, "floor")) {
  ds_list_add(connections, rm);
  checkflr=upper;
}
else { checkflr=lower; }

flrlist=ds_map_find_value(global.floors, checkflr);
valid=ds_list_create();

/*str="Floor list contains: {";
for (p=0; p<ds_list_size(flrlist); p+=1) {
  str+=string(ds_list_find_value(flrlist, p));
  if (p<ds_list_size(flrlist)-1) { str+=", "; }
}
show_message(str+"}");

if (!ds_map_exists(global.floors, checkflr)) {
  show_message("Tried to check floor "+string(checkflr)+", but it doesn't exist!# #(Passed {"+string(lower)+", "+string(upper)+"})");
}*/

for (p=0; p<ds_list_size(flrlist); p+=1) {
  check=ds_list_find_value(flrlist, p);
  if (ds_map_find_value(check, "type")!=TY_ROOM) { continue; } // Can't connect stairs to stairs
  checkcon=ds_map_find_value(check, "connections");
  if (ds_list_find_index(checkcon, -1)<0) { continue; } // Can't connect to filled rooms
  ds_list_add(valid, check);
}

/* If all rooms on the floor are filled, return false and destroy stairs */
if (ds_list_size(valid)<=0) {
  ds_list_destroy(valid);
  ds_list_destroy(connections);
  ds_map_destroy(stairs);
  return false;
}

/* Otherwise, pick a random valid room and connect away! */
ds_list_shuffle(valid);
check=ds_list_find_value(valid, 0);
ds_list_destroy(valid);
checkcon=ds_map_find_value(check, "connections");
p=ds_list_find_index(checkcon, -1);
ds_list_replace(checkcon, p, stairs);
ds_list_add(connections, check);

if (upper==ds_map_find_value(rm, "floor")) {
  ds_list_add(connections, rm);
}

ds_list_add(flrlist, stairs);
//show_message("Added stairs to floorlist, ID = "+string(stairs));

return true;

Connect(room, dir) - Attempts to connect the new room "room" to the existing building in direction "dir". Dir indicates which wall to connect; 0=north, 1=east, 2=south, 3=west. Returns false if no rooms on the same floor have a place to connect to it from that side.

Spoiler

var rm, flr, check, dir, connections, checkcon, dir2, p, valid, invalid;
rm=argument0;
dir=argument1;
dir2 = (dir + 2) mod 4;

connections=ds_map_find_value(rm, "connections");
if (ds_list_find_value(connections, dir)>=0) { return false; }

flr=ds_map_find_value(rm, "floor");
flr=ds_map_find_value(global.floors, flr);

valid=ds_list_create();
invalid=ds_map_find_value(rm, "invalid");

/* Find all valid rooms */
for (p=0; p<ds_list_size(flr); p+=1) {
  check=ds_list_find_value(flr, p);
  if (check==rm) { continue; } // Can't connect a room to itself
  if (ds_map_find_value(check, "type")==TY_STAIRS) { continue; } // Stair connections are handled separately
  if (ds_list_find_index(invalid, check)>=0) { continue; } // Can't connect to invalid rooms
  checkcon=ds_map_find_value(check, "connections");
  if (ds_list_find_value(checkcon, dir2)>=0) { continue; } // Can't connect to a room w/ the position filled
  ds_list_add(valid, check);
}

/* If no valid rooms exist, return false */
if (ds_list_size(valid)<=0) {
  ds_list_destroy(valid);
  return false;
}

/* Choose a random valid room */
ds_list_shuffle(valid);
check=ds_list_find_value(valid, 0);
ds_list_destroy(valid);

/* Add the old room's connections to the invalid list of the new room */
checkcon=ds_map_find_value(check, "invalid");
Concat(invalid, checkcon);
checkcon=ds_map_find_value(check, "connections");
Concat(invalid, checkcon);

/* Connect the rooms */
ds_list_replace(checkcon, dir2, rm);
ds_list_replace(connections, dir, check);

return true;

Concat(list1, list2) - Concatenates list2's unique values into list1, basically converting list1 into the union of the two lists. This is used as a helper function to build up the "invalid room connections" lists of each new room from the connections of the rooms it's connected to; this prevents physically impossible room layouts

Spoiler

var l1, l2, val, p;
l1=argument0;
l2=argument1;

for (p=0; p<ds_list_size(l2); p+=1) {
  val=ds_list_find_value(l2, p);
  if (ds_list_find_index(l1, val)<0) {
    ds_list_add(l1, val);
  }
}

And, the piece de resistance:

AddRoom() - Attempts to add a new room to the existing building. Returns false if that's not possible (i.e. all walls of all existing rooms are occupied; should never happen)

Spoiler

/* Format:

  global.floors {key, val} = {floor #, ds_list of rooms on the floor}
  room {key, val} = {
    "type" : const TY_ROOM|TY_STAIRS,
    "floor" : real floor_its_on (-1 for stairs)
    "connections" : ds_list{N, S, E, W}|{UPPER, LOWER} rooms_its_connected_to,
    "invalid" : ds_list rooms_it_cannot_connect_to
  }
  
  When adding a room:
  
  1) Connect to random valid room on same floor if one exists
     *Valid means not in "invalid" list and at least one opening in "connections" list
     *Also, valid connections are NS and EW.
  2) If no such room exists, create a staircase on floor +/- 1 and connect to that
     *Staircases can only connect 2 rooms on floors w/ dz=1 (their connections list is 2-element upper/lower rooms)
  3) Once connected, invalid+=connected_rooms_invalid + connected_rooms_connections
  4) Repeat #1-3 n times where 1<=n<=4 (at least 1 connection, randomly up to 4 connections)
*/
var flr, flrlist, rm, connections, invalid, p;
if (ds_map_empty(global.floors)) {
  rm=ds_map_create();
  flr=0;
  connections=ds_list_create();
  repeat (4) { ds_list_add(connections, -1); }
  invalid=ds_list_create();
  ds_map_add(rm, "type", TY_ROOM);
  ds_map_add(rm, "floor", flr);
  ds_map_add(rm, "connections", connections);
  ds_map_add(rm, "invalid", invalid);
  
  flrlist=ds_list_create();
  ds_list_add(flrlist, rm);
  ds_map_add(global.floors, flr, flrlist);
//  show_message("Added first room to floor list, ID = "+string(rm));

}
else {
  flr=irandom_range(global.minfloor-global.builddown, global.maxfloor+global.buildup);
  if (!ds_map_exists(global.floors, flr)) {
    flrlist=ds_list_create();
    ds_map_add(global.floors, flr, flrlist);
  }
  else {
    flrlist=ds_map_find_value(global.floors, flr);
  }
  
  rm=ds_map_create();
  ds_map_add(rm, "type", TY_ROOM);
  ds_map_add(rm, "floor", flr);
  
  connections=ds_list_create();
  repeat(4) { ds_list_add(connections, -1); }
  invalid=ds_list_create();
  
  ds_map_add(rm, "connections", connections);
  ds_map_add(rm, "invalid", invalid);
  
  if (flr>global.maxfloor) {
    if (!AddStairs(global.maxfloor, flr, rm)) {
      ds_list_destroy(invalid);
      ds_list_destroy(connections);
      ds_map_destroy(rm);
      global.buildup=0;
      return false;
    }
  }
  else if (flr<global.minfloor) {
    if (!AddStairs(flr, global.minfloor, rm)) {
      ds_list_destroy(invalid);
      ds_list_destroy(connections);
      ds_map_destroy(rm);
      global.builddown=0;
      return false;
    }
  }
  
  for (p=0; p<4; p+=1) {
    if (irandom(100)<25) {
      Connect(rm, p);
    }
  }
  
  global.minfloor=min(flr, global.minfloor);
  global.maxfloor=max(flr, global.maxfloor);
  ds_list_add(flrlist, rm);
//  show_message("Added new room to floor list, ID = "+string(rm));
}
return true;

And lastly, I'm displaying the final layouts with this DFS script:

MakeFloor(floor) - Reads the data for the specified floor and places roomObj instances where the rooms are. Also sets the roomObj instances' "mytype" variable to the node's type, either TY_ROOM or TY_STAIRS.

Spoiler

var stack, node, cons, n, s, e, w, visited, type, xx, yy, flr;
flr=argument0;
if (!ds_map_exists(global.floors, flr)) { return false; }
flr=ds_map_find_value(global.floors, flr);
if (ds_list_size(flr)<=0) { return false; }
node=ds_list_find_value(flr, 0);

stack=ds_stack_create();
visited=ds_map_create();
ds_stack_push(stack, 0);
ds_stack_push(stack, 0);
ds_stack_push(stack, node);

while (!ds_stack_empty(stack)) {
  node=ds_stack_pop(stack);
  yy=ds_stack_pop(stack);
  xx=ds_stack_pop(stack);
  
  if (ds_map_exists(visited, node)) { continue; }
  
  ds_map_add(visited, node, 0);
  
  cons=ds_map_find_value(node, "connections");
  type=ds_map_find_value(node, "type");
  flr=ds_map_find_value(node, "floor");
  with (instance_create(xx, yy, roomObj)) {
    mytype=type;
    connections=cons;
    myfloor=flr;
  }
  if (type!=TY_ROOM) { continue; }
  
  n=ds_list_find_value(cons, 0);
  e=ds_list_find_value(cons, 1);
  s=ds_list_find_value(cons, 2);
  w=ds_list_find_value(cons, 3);
  
  if (n>=0) {
    ds_stack_push(stack, xx);
    ds_stack_push(stack, yy-32);
    ds_stack_push(stack, n);
  }
  if (s>=0) {
    ds_stack_push(stack, xx);
    ds_stack_push(stack, yy+32);
    ds_stack_push(stack, s);
  }
  if (e>=0) {
    ds_stack_push(stack, xx+32);
    ds_stack_push(stack, yy);
    ds_stack_push(stack, e);
  }
  if (w>=0) {
    ds_stack_push(stack, xx-32);
    ds_stack_push(stack, yy);
    ds_stack_push(stack, w);
  }
  
}
ds_stack_destroy(stack);
ds_map_destroy(visited);

/* Since the rooms may have been off-screen, move them so the top-left is at (0,0) */
n=room_height*10;
w=room_height*10;
with (roomObj) {
  if (x<w) { w=x; }
  if (y<n) { n=y; }
}
with (roomObj) {
  x-=w;
  y-=n;
}

Wow. That's quite a bit of code. Mind you, I'm not getting any explicit errors, it's just an algorithmic logic problem somewhere. I know it's a lot to look through, but...can anyone help? Please?

-IMP

[torigara]

At the top of script AddStairs:

stairs=ds_map_create();
connections=ds_list_create();
ds_map_add(rm, "type", TY_STAIRS);
ds_map_add(rm, "floor", lower);
ds_map_add(rm, "connections", connections);

Aren't the first argument of those ds_map_add supposed to be "stairs" rather than "rm"? Otherwise, stairs.type will remain undefined (that will let MakeFloor treat it as a room in case the value of TY_ROOM is 0.)

Edited by torigara, 26 April 2012 - 05:20 AM.

[IceMetalPunk]

*Facepalm* Of course. All the time I spent developing that algorithm, and what gets me is a copy/paste issue .

Well, now I've got the stairs thing sorted out (all I changed were those rm's to stairs's). The only problem is that it's now making fewer than 20 rooms each time. Arbitrarily. That's not counting the stairs; if I count the stairs, it ends up making more than 20. I've checked with a simple show_message(), and it's never returning false, either.

What could possibly cause it to stop short of 20 rooms without returning false at any point?

Note: if this is also caused by a copy/paste error, I'm never pressing CTRL+V again. But don't hold me to that .

-IMP

[torigara]

Well, I think there are two possibilities. First, there can be isolated rooms those have no connection.

for (p=0; p<4; p+=1) {
    if (irandom(100)<25) {
      Connect(rm, p);
    }
  }

There is (3/4)^4 = 31% chance that Connect isn't called. (Of course, as Connect doesn't always succeed, there is higher chance that the room get isolated.) And the room won't be drawn unless it is connected to the first room in the floor (either directly or indirectly.)

Second, there can be rooms on top of each other. For example, suppose that three rooms are created, one pair is connected north-south and one connected east-west.

+---+  +---+
| 2 +--+ 3 |
+-+-+  +---+
  |
+-+-+
| 1 |
+---+

Two more rooms are added, connected to the third one.

     to room 3
         |
+---+  +-+-+
| 5 +--+ 4 |
+---+  +---+

When you create room objects out of this structure, two rooms will end up on top of each other, making it look as if there are only four rooms.

+---+  +---+
| 2 +--+ 3 |
+-+-+  +-+-+
  |      |
+-+-+  +-+-+
|1,5+--+ 4 |
+---+  +---+

Edited by torigara, 26 April 2012 - 07:08 AM.

[IceMetalPunk]

Well, I think there are two possibilities. First, there can be isolated rooms those have no connection.

for (p=0; p<4; p+=1) {
    if (irandom(100)<25) {
      Connect(rm, p);
    }
  }

There is (3/4)^4 = 31% chance that Connect isn't called. (Of course, as Connect doesn't always succeed, there is higher chance that the room get isolated.) And the room won't be drawn unless it is connected to the first room in the floor (either directly or indirectly.)

Second, there can be rooms on top of each other. For example, suppose that three rooms are created, one pair is connected north-south and one connected east-west.

+---+  +---+
| 2 +--+ 3 |
+-+-+  +---+
  |
+-+-+
| 1 |
+---+

Two more rooms are added, connected to the third one.

     to room 3
         |
+---+  +-+-+
| 5 +--+ 4 |
+---+  +---+

When you create room objects out of this structure, two rooms will end up on top of each other, making it look as if there are only four rooms.

+---+  +---+
| 2 +--+ 3 |
+-+-+  +-+-+
  |      |
+-+-+  +-+-+
|1,5+--+ 4 |
+---+  +---+

Right...

The first issue (with the chance of an isolated room) is an easy enough fix. But I have no idea how to fix the second problem. Keeping in mind the way these layouts are represented (as nodes with references to their connected nodes), what is an efficient way to determine if two rooms would overlap? There's no connection between (in your example) rooms 1 and 5. Would I have to do some kind of pathfinding process?

I'm trying to think of how I'd detect such a thing, and I'm coming up blank. I figured some sort of BFS that tracks the directionality of each edge could work, but I'm not entirely sure on the details of such an algorithm.

-IMP

*EDIT* Hm. I've also noticed yet another problem . Sometimes, it places 3 stairwells on one floor. This shouldn't be possible, since it only places stairwells if it makes a new floor above or below the current one, right? So that should limit it to a maximum of 2 stairwells per floor? So how is it making 3 sometimes?

Edited by IceMetalPunk, 26 April 2012 - 07:15 PM.