The Mechanical Heart

Development Blog

In this issue I would like to talk about the map generation in TMH, if you're unaware of the storyline I would recommend catching up and read the first development blog. True to most rogue-like( like)s TMH will feature randomly generated, room based maps. TMH will challenge the player of navigating through lots of different rooms to get to the destination room(s). I wanted the player to feel lost in The Inventors factory, and constantly twisting and turning through different rooms. This is so the path that player will take will take will mimic the crazed pathways of The inventors mind.

When designing the algorithm for the map generation there are X goals to keep in mind, they are:

1. Destination room to be accessible from any room in the map.
   
2. Start room to destination room path should not be as the crow flies.
   
3. Able to handle different sized rooms.
   
4. Conforms to Euclidean spacing.
   

Firstly, I decided on a simple two dimensional array to hold each room that the player would be traversing. For the Number One and Number Two goal I decided to use a path finding algorithm to generate nodes from the start room to the destination room. The location of each node would be the location of a room in the array. I based the path finding algorithm of A* algorithm, however I had to devise a way of making the path it would create... less efficient, and here is the point I coin the name A[sup]-[/sup] algorithm (maybe I need a better name, suggestions?).

This is pretty simple to do, I simply add a random number between 0 and X to the cost of each node, the higher X is the more random the path would be. However, there does seem to be a sweet spot, as if X is too high the cost of the node will be negligible and the path will no longer bend and twist towards the destination room. I Also added dividers and barriers the A[sup]-[/sup] would have to work around.

I have created a small program so you can try the A[sup]-[/sup] for yourself.

The next step in the map generation is to use the path generated to fill the map with different rooms. There are a couple of assumptions that we have to make before we do this. The first assumption is that all rooms that are about to be filled are the size of the smallest room, and that 1 element in the array has that size 'in the real world space'. This is to ensure there will always be an adjacent room when we start to add and remove rooms. However this causes problems as demonstrated in the gif below. Because there are different sized rooms the is a chance that the map will not conform to Euclidean space, rooms that clash with Euclidean space are marked in red.

Room Based Euclidean Space Algorithm (RBES)

RBES is an algorithm that takes a generated map, conforms it to euclidean space and then links the rooms together. This algorithm is needed because there are rooms with different sizes, and the rooms are selected randomly. This leaves the rooms in the map prone to overlapping each other. This can cause problems with linking of rooms, and logical path taking of the player, which leads to confusing gameplay experience. This, overlapping or sharing the same space, is known as non-eclidean space or non-eclidean geometry. non-eclidean space allows for deformation of 'normal' space allowing objects and places to occupy the same space as each other, this lends itself well for some games which aims to confuse the player with the nonsensical world layout. However this does not fit the theme of the game, and thus the game world will need to conform to Euclidean space.

RBES has two main steps in the algorithm, the first step is checks and set, this step checks that the rooms to conform to Euclidean space and handles them if they don't, and the second step links the rooms together using portals. When the player enters a portal the main character will be teleported to the corresponding room.

Check and Set
Rooms The first step of RBES is to conform the generated map to Euclidean space. It checks that none of the rooms overlap and if they do it deals with the overlapping room accordingly. This is a fairly simple process, cycle through each room and check if the room the relative position of the subroom(a subroom is the area of a room that could be divided into the smallest possible size for a room) in the matrix contains a room.For each sub room If there is a room in that subroom's relative position Delete that room

This is simple and quick, however this algorithm has a major flaw, it doesn't take into account for any rooms that are prior to the current room's position, for example:

To correct this each matrix entry before the current subroom on the X axis will need to be checked.
The altered algorithm is:For each subroom If there is a room in that subroom's relative position Delete that roomFor each subroom on the Y axis For each room before current subroom on the X axis While there is a room and that room intercepts current subroom Replace that room with another random room

Linking rooms
Now we can be sure that the map conforms to Euclidean space we can place portals to link the rooms together. This will allow the player to travel from one room to another. Each portal contains the information of the destination room, player position in that room, and camera position. All of these things can be worked out from: The size of the room and adjacent room and the position of the room and adjacent room in the array.

Rooms can be linked in a one to many fashion, this means that a room can be linked to multiple different rooms, how many rooms said room is inked to depends on two factors; room size and if there is an available room. To link the rooms, each room and its subrooms need to check if there is an adjacent room(or subroom) in real world space.For all of the rooms For the perimeter of the room If there is a subroom of any previous room adjacent to any of the current subroom set a portal from the current subroom to the adjacent subroom set a portal from the adjacent subroom to the current subroom

?
?
?
?

The final map looks like:

This can be ran multiple times to create different routes that the player can traverse.


I am pretty happy how the map generation worked out, it meets the specification pretty neatly, and creates some interesting pathways. I may end up tweaking it and or making it more efficient. I was also thinking of making an article about it, but I am still undecided...

Until next time,
dsm?