The Mechanical Heart

Development Blog

Sorry for the laps in journals lately I have recently (by recently I mean 4 months ago) acquired a job as a Mobile game Developer. In this Journal I will discuss the room generation system in The Mechanical Heart. We have already discussed map generation in the game, which can be found Here.

Goal

We want to be able to randomly generate rooms. We don't know the minimum or maximum size the room can be, so the algorithm needs to be flexible and cater for many different possibilities.

Each room will have walls, floors and ceilings. They will also have entrances and exits to other rooms. The map will contain an undetermined amount of rooms.


Prologue
I was stuck for a while on how to randomly generate rooms, most games which use a random room generation system are put together like a jigsaw. That is, there are lots of different pre made pieces and they are put together to generate a room. I did not want this, in the true style of random random random, I wanted it to be fully randomly generated.

After searching around on the internet for a bit, all it took was one word. Shape. I could randomly generate a shape and that shape would determine the...shape, of the room.

*Please note: The following images have been aligned in such away that they cut of some of the tiles ( one and a half tiles from the top and the right), this was just for formatting reasons*

Creating the shape

Creating a random shape shape isn't to hard, we just need to generate random points and link them up. However, We do not wish to make a Complex Polygon. To prevent this, we have 4 set areas for our points to spawn in. and make sure a point is always proceeding of the next point.

Here we can see 4 different areas that the points can spawn in, one for the ceiling two for the walls and one for the floor.

We need to keep in mind:
(with 0,0 being top left)
When generating Ceiling points -Each new point's X needs to be greater than the previous points X
When generating Right Wall points -Each new point's Y needs to be greater than the previous points Y
When generating Floor points -Each new point's X needs to be Less than the previous points X
When generating Left Wall points -Each new point's Y needs to be Less than the previous points Y

We also need to keep in mind that the first point, and the last point is the same point.

Outlining the shape

Great! so now we have a random shape which is what our room will look like, the next step is filling any tiles outside of the shape with a tile. To do this we can use an In/out algorithm. We cast a ray from each tile position and counts the amount of times the ray intercepts the rooms shape. If the number of interceptions is even (or 0), the tile must be outside the shape. If the number of interceptions is odd, it must be inside the shape.

Here is an image of the tests. The blue line intercepts the shape twice, and green line intercepts once.

because I can ensure that there will always be an outline of tiles to the room's shape, I can combine this check with a flood fill algorithm so we do not have to check ever tile space in the room.

Setting Room boundaries
Now we have a simple room shape we can fill out the parameter of the shape with more details, setting the wall tiles to walls, and floor to loor tiles ect.

To do this we need to traverse each edge of the shape. Because we know the room shape is wound clockwise, we can say that when we are traversing the edge with a positive X this will be the ceiling, when we traverse the edge with a negative X it will be the floor.

When we traverse the edge with a positive Y this will be the Right wall, and When we traverse the edge with a negative Y this will be the Left wall.

Combining these will allow us to deal with slants.

There are some other checks that I do, however this will depend on the tile set.

Corners

The Next step is to set the corner tiles. Its important we do this last as it requires to check the surrounding tiles, and depending on their configuration it will change accordingly. if we did it in the previous step, a tile may not have been set yet, thus it will chose the wrong tile.

Here is the check we need to perform, this is the worst case scenario, often we don't need to check all 8 Tiles. For example, if we know it is the floor (nothing above the tile) we can stop after the first check.

Exits
This is the final step is to have entrances and exits, All that needs doing is to place points of the room shape outside of the room boundaries, then run the generation. The final result should look something like this:

Why not just flood fill and check each tile?

My dear friend TheChubu said I was overcomplicating this, and suggested that I just check the surroundings of each tile and choose the tile accordingly. This would have been fine if I knew that I wanted only small rooms, but I wanted to create a versatile system which would work with many rooms. I also wanted to be able to put nest the room shapes, that is have a shape in side the room shape, to give a solid block of tiles inside the shape.

This system works very well and is very flexible and is capable of working with many games.

Here is the final image of the room.

I am very happy with this algorithm, it sets out to achieve every thing I wanted it too

Until next time!
Dsm