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
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.
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.
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
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)
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.
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?