log in | register | forums
Show:
Go:
Forums
Username:

Password:

User accounts
Register new account
Forgot password
Forum stats
List of members
Search the forums

Advanced search
Recent discussions
- WROCC March 2024 meeting o... Hughes and Peter Richmond (News:1)
- Rougol March 2024 meeting on monday with Bernard Boase (News:)
- Drag'n'Drop 13i2 edition reviewed (News:)
- South-West Show 2024 talks (News:4)
- February 2024 News Summary (News:1)
- Next developer fireside chat (News:)
- DDE31d released (News:)
- South-West Show 2024 Report (News:)
- South-West Show 2024 in pictures (News:)
- Big NVMe news for the RISC OS at the South-West Show (News:)
Related articles
- Bob and Trev: Resurrection: Just in time
- Monster AI
- Combat
- Visibility and pathfinding
- Static game data
- How to fit a roguelike in 32k
- Bob and Trev: Resurrection
- Wakefield 2003 - the preview
- Newsround
- Arculator updated to add A4 emulation and more podule support
Latest postings RSS Feeds
RSS 2.0 | 1.0 | 0.9
Atom 0.3
Misc RDF | CDF
 
View on Mastodon
@www.iconbar.com@rss-parrot.net
Site Search
 
Article archives
Acorn Arcade forums: News and features: The level generator
 

The level generator

Posted by Jeffrey Lee on 00:00, 13/3/2007 | , , , , , , , ,
 
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.
 

  The level generator
  Phlamethrower (00:35 13/3/2007)
  monkeyson2 (00:48 13/3/2007)
    Phlamethrower (00:56 13/3/2007)
 
Jeffrey Lee Message #99865, posted by Phlamethrower at 00:35, 13/3/2007
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15100
It's a map generator update!

I've been waiting a long time for this article to go live.

The map generator is in, and for the most part works fine, as can be seen from the attached screenshots. There isn't any code for different room styles yet, but that can always come later if there's enough time.

Current issues with the generator are:

* Short walls sometimes have doors in them, resulting in doors being placed in the corners of rooms. This doesn't restrict the player's movement, but will result in confusion when he tries to work out if the door is open or not. And, it looks silly. Unfortunately there isn't much that can easily be done about the problem. I could delete adjacent wall tiles, but that would just lead to problems with the line-of-sight code.

* There's a bug in the code that makes sure the rooms are connected! I'm currently not sure what the problem is, but every so often a level will have one room which has no door leading into it. I've also seen one level which had two connected rooms which couldn't be entered from the outside. To fix this, I've changed the algorithm slightly; it will now always add a door to the wall that is inserted at the split point. To keep the overall number of doors in the level the same, I've also reduced the number of "random doors in the new edges" from 2 to 1. These changes have resulted in a slightly different layout and feel of the levels, but I think the new levels actually look a bit better than the old ones.

The one thing I am pleased about with the generator is its size. Looking back to the original code I wrote on Saturday, the level generator was 3.6K in size. Performing some optimisation at the same time as adding new features (simple item & monster spawning, stairs leading up) has only resulted in the code growing to 3.7K in size. Crunching it with StrongBS brings it down to 2.7K; but by merging a couple more functions together, I think I can squeeze an extra 400 bytes out of it, and improve the execution speed by simplifying some pointer math.
batr2.png 320x250 736bytes
batr2.png
320x250
736bytes
batr4.png 320x256 1.2KB
batr4.png
320x256
1.2KB

  ^[ Log in to reply ]
 
Phil Mellor Message #99867, posted by monkeyson2 at 00:48, 13/3/2007, in reply to message #99865
monkeyson2Please don't let them make me be a monkey butler

Posts: 12380
That second screenshot isn't Mode 7!
  ^[ Log in to reply ]
 
Jeffrey Lee Message #99869, posted by Phlamethrower at 00:56, 13/3/2007, in reply to message #99867
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15100
No.

But it has colours! 4 of them! For people with 64K
  ^[ Log in to reply ]
 

Acorn Arcade forums: News and features: The level generator