Acorn Arcade forums: The level generator

Previously, on Bob and Trev: Resurrection...

Previously, on Bob and Trev: Resurrection...
The current dungeon level.
For simplicity, I won't be having a scrolling map. This means that the largest level possible would be 40 by 25 tiles; in reality I'll only be using 40x22, as 3 rows will be required for displaying the players' status and game messages. And since the dungeon is fairly simple in design, I'll only need at most 1 byte per tile - so a full map of the current dungeon level will require 880 bytes of memory.

Until now, I haven't really gone into any detail about what the dungeon structure will be like. Since you don't find many BBC users in Gnomish mines, I realised quite early on that the traditional underground dungeon setting wouldn't work very well for this game. So instead I turned the game world on its head - you'll start at the bottom of a skyscraper and work your way up. In particular, if I have the time I'll make the first and last levels unique - the first level will be an underground parking lot, and the last level will be the rooftop, where you will find your nemesis (Don't ask me who he is - I haven't decided yet!) These unique levels will require only simple generators, but how will the office levels inbetween be generated?

The Office: A roguelike workplace

The Acron Suicide Clan Member hits! ####-####-########################-##### #.........#..........#.........#.......# #.>.......#..........#.........#.......# #....@S...#..........#.........#.......# |.........######-#########-#####.......| #.........|....................|.......# #####################-################## #......................................# #......................................# |......................................| #......................................# #......................................# #......................................# #......................................# |......................................| #......................................# #####-#####............................# #.........#............................# #.........#............................# |.....<...#............................| #.........#............................# ####-####-####-####-####-####-####-##### Floor:XX £123456 Hungry Conf xx/yy ACXX StXX InXX CoXX DxXX WiXX ExXX

Above is a fairly simple mockup of what the screen could look like while playing. Windows line the edge of the level; if he wants, the player could break through one of them and jump to his death. Or perhaps push a monster out. Doors seperate the different rooms. Rooms can contain furniture such as chairs and desks, interactable items such as water coolers and plant pots, and hidden traps to thwart any invaders. There will also be toilets, urinals, sinks and cubicle walls, to add some more variety to the design. But how can I generate the levels?

Luckily, I already have an algorithm that works quite well for indoor areas - it's the one I've discussed before that's used by GAIO. With a few tweaks, I can easily adapt it to generate office-like levels for this game.

The algorithm

The best way to describe the algorithm is in terms of how it differs from the GAIO algorithm. For example, it won't split a room if it's a thin corridor. But the more interesting differences are how the new algorithm deals with memory management.

The GAIO algorithm used a lot of scary linked list structures to maintain lists of rooms and edges. This resulted in the code being larger and more complex, and the algorithm using a fair amount of memory (Memory which simply won't be available on the BBC). Furthermore, BASIC doesn't really support dynamic memory allocation, so if it would all have to be done manually. There's also the rather archaic algorithm that randomly connects rooms until all rooms in the map can be connected.

I'm pleased to say that all these issues have been dealt with in the new algorithm. The memory requirements are even low enough for the algorithm to store its temporary data in the 1414 bytes of per-level object data (Which will be free for use, because the game will be halfway between levels at the time).

To start with, I'll talk about how it tackles the problem of room connectivity. Since I won't be having a way for the player to blast through walls, it's important for the player to have a route of doors leading from the start room to the exit room. But how can you generate a level which is guaranteed to have all rooms connected?

Take a look at the following diagram:

......######### ......#.......# ......#.......# ##########-########## #.....#.......#.....# #.....#.......#.....# #.....|.......|.....# #.....#.......#.....# #.....#.......#.....# ##########-########## ......#.......# ......#.......# ......#########

By looking at it, you can see that all the rooms are connected. If we split the middle room, we could end up with the following arrangement:

......######### ......#.......# ......#.......# ##########-########## #.....#....#..#.....# #.....#....#..#.....# #.....|.A..#B.|.....# #.....#....#..#.....# #.....#....#..#.....# ##########-########## ......#.......# ......#.......# ......#########

Suddenly, the rooms aren't connected anymore. The two on the right are inaccessible to the four on the left. The obvious way to reconnect them is to introduce one or more doors on the new edges - the three edges to the north, west, and south of room B. And if we turn any of those new edges into a door, the map will remain fully connected. And that's all there is to it - making sure that when a split is made, at least one of the new edges introduced is a door edge.

In reality, the algorithm works slightly differently. Assuming 3 new edges are created, it picks two random numbers from 1 to 3, and turns both those edges into doors. Sometimes it may pick the same number, sometimes it may pick different ones - thus ensuring that all rooms are connected without the level degenerating into a linear route or a fully connected graph where each room is connected directly to each of its neighbours.

The other major difference is how the room and edge lists are handled. Instead of storing them in linked lists, they are stored in linear lists. The room list starts at the bottom of the 1414 byte temporary memory block, filling it from the bottom up, and the edge list starts at the top, filling it from the top down. Some quick maths suggests that under normal circumstances the algorithm won't run out of memory - but if needed I can put in an extra clause to stop the room splitting algorithm when the buffer becomes full.

For each room, 5 bytes are stored - 4 bytes for the coordinates, and one byte for the room style (Empty, meeting room, 'office space', toilets, etc.). For each edge, 3 bytes are stored - 2 bytes contain the room IDs of the rooms the edge lies between, and the 3rd byte contains the flags (contains a door, contains window(s), etc.)

The splitting algorithm has also been changed slightly. The recursion used by the original splitting algorithm isn't needed, as it doesn't really matter which order rooms are split in. The new algorithm simply runs through the room list in order, repeatedly splitting the current room until it becomes too small. Each new room created is appended to the end of the room list.

Edge handling is slightly more compelx, however. Whereas each room in the GAIO algorithm maintained its own list of edges, the new algorithm only has one global edge list. The only way to get the list of edges for a room is to iterate the full list and check each edge individually. Although this will be slower, it simplifies the code significantly. In reality the loss of speed won't matter much, due to the small size of the levels, and speed gains made elsewhere (e.g. not relying on a seperate stage to connect rooms with doors).

Room styles

As mentioned above, I'm hoping to have a few different room styles. The room style will be determined by several factors - the size and shape of the room, and how many of its edges contain doors. For each style, there will be a different filler function - the function which creates the interior of the room. For example, the filler function for a 'toilets' room will split the room into a series of smaller toilet cubicles. These will only be 'virtual rooms' - i.e. no new entries will be added to the room or edge lists.

Traps

There will also be a few traps dotted around levels. These will start out as a special, 'hidden trap' tile, and only when a monster or the player walks over them will the game decide what trap to transform them into.

Monsters and other items

These will be placed randomly throughout the level. For each item and monster type, the static game data contains the probability of the item appearing, and the range of levels it can appear on. This means that the game can easily pick a random number between 0 and the sum of the probabilities, then scan through the type list to find out what item should be spawned. Monsters will have an experience level that increases in relation to the dungeon level. I'm also hoping to include monster inventory information in the static dungeon data; so that when a Stylophone Clan member is spawned, he will automatically be wielding a Stylophone.