How the level generator is going to work

I worked it out step by step and I now have a better idea on how to go about coding it. The level structure is going to look like a BSP-tree, since it's a simple and decent place to start. Instead of having a wall of text I made some handy-dandy images to break things up and help show what I mean. On the left is what the level will look like, on the right is how it got generated and is a representation of the connections between sectors. I'll try and spare the nitty-gritty details of it's inner workings and keep the explanation simple.

So, the game needs to build a new level, completely from scratch. Okay, to start, lets pick any valid location within the screen area. We will create sector '0' and drop it somewhere, like so:




It's a start. An ordinary room where the player will spawn. Now when a side room is generated, it may or may not have doors leading to other side rooms, closets, corridors, etc. A side room needs to have at least one door (to enter/exit through) but does not necessarily mean that it needs to have any others. When the starting room was created, the engine decided to make the sector have two doors: East and South, or sectors '1' and '2' respectively. The arrows represent the connection between the nodes in the tree or the sectors in the map.




Okay, now we're starting to get somewhere. We have a rough direction to work in. Where do we go from here? We have two doors, numbers 1 & 2, but what do we do with them? How do we decide which one to extend first? I'm going to start with the lowest and work my way up of course! (There is a flaw with this but I'll get into it a wee bit later) After a few checks and random rolls, the engine decides to put a corridor on the other side of sector 1 (east door), which will be sector 3. The engine does the same for sector 2 (south door), decides there will be a corridor there as well, and it will be sector 4. Because of the proximity of sectors 3 and 4 when they are generated, they can be (but are not required to be) connected.




So now we have a starting room, and a corridor outside it with two connections. Things are starting to shape up! Now, there are actually 3 steps I compacted into that one image:

1. Draw sector 3 off of 1
2. Draw sector 4 off of 2
3. Sector 3 is next in line, and before it draws any attached doors or other corridor pieces, it checks if a direct connection (no door) to another corridor can be made. If it can be done, a decision is made to whether it does indeed connect or not.

After it decided to connect with sector 4, now sector 3 checks for doors and other corridor pieces. When sector 3 was created, the generator flagged the sector as having one door to build, and two corridor directions. The connection with sector 4 would not have happened if it would have interfered with what sector 3 was flagged to draw. The door is put on the east side, towards the north edge (sector 5). One corridor piece will branch off the north face and head west (sector 6), while the other will branch off the south face and head east (sector 7).

Looking good! The map is getting just a tad more complicated now that it's heading in two directions (east and west). Sector 5 (the door) is up next. There's going to be a big room on the other side of this door (sector 8, because 6 and 7 were already taken). The big room is actually just a side room resized. (in 64x64 chunks).

I'm starting to run into a bit of a complication. It started with the creation of the corridors outside the starting room, and is being aggravated with every step. Can you tell what it is yet? Lets keep moving forward. The next sector we're going to expand is #6. Even though the last sector created was #8, #6 is the lowest sector that still has yet to be checked for expansion. This sector, like the starting one, is going to have two doors, one on the south and west walls, sectors 9 and 10 respectively.

That complication was just made worse. As the sectors expand and splits are added, two adjoining sectors can have ID numbers that are way off (sector 6 adjoins sectors 3, 9, and 10, #3 adjoins #1, and #4 to #7, etc.). However, as long as I stay aware of it and code for it, it shouldn't be too big a problem. It's just another complication in a nontrivial system. Still, it's worth the mention because it is an interesting issue. Moving forward, sector 7 is next to be expanded. Being a corridor, it checks to see if it can connect to another corridor. There are no other corridors to connect to, but it does detect that it could connect to a side room. It checks if it should, gets the go-ahead, and places a door (sector 11) between #7 and #8. The corridor was also flagged to have a door anyways, so it puts one on the east side (sector 12).

Now we hop all the way to the other side of the map (but only separated by two nodes) to sectors 9 and 10. The engine decides to put a side room behind each door, but the created sectors are NOT flagged to have any doors. They are a dead end.

There's only one sector do expand at this point: #12. It's another side room, with no flagged doors either. It's the last sector, #15

So there it is: a nice, small little map. It isn't a terribly complicated concept (the tree is easy to follow (well, to me it looks easy anyways...)) but I have to think of, and code for every possible condition and conflict that could appear. The goal here is to make a flexible and fast level generator, so I have to compromise from time to time.

Now, keep in mind that it won't just be the levels that are randomly generated: as much as I can get away with randomly generating is where I'm drawing the line =D Much of how the generation will work is already expressed in how the levels are generated, so once I have the initial design of the system I can modify it to generate other things =)