Maze generation (Part I)

#Stencyl: Maze generation (Part I)

Difficulty: (7/10)

Estimated time of work: 4-5 hours

Maze generation problem

In some games you move from room to room while encountering various types of monsters along the way. Classic examples involves dungeon crawlers RPGs, Metroid or Binding of Issac. Today we will be generating a maze.

Binding of Issac as an example of game using room map (map of rooms at the top left)

Analysis of problem:

While playing this type of game you usually start at some starting point while looking for the exit. All of the generated rooms should be connected. Otherwise the map would be made of islands and it would be impossible for player to visit some of the generated rooms. What would be even worse is the case where the starting point is on one island and exit point is on another. This situation makes for player impossible to proceed.

Example of properly generated maze - all rooms connected (red - start, blue - exit)

 Example of badly generated maze - player won't be able to get to the exit

Follow the link to get to the finished game:

http://www.filedropper.com/metroidmap

Link to video of the game:

https://www.youtube.com/watch?v=MbXKNUlxxi0

Algorithm:

1. Create matrix with width and height of your choice representing map with no rooms
2. Declare number of rooms you want to create (no bigger than number of cells in matrix)
3. Create empty list(room list), we will keep there coordinates of rooms
4. Pick a cell at random, add it to the list
5. Pick one room from room list, with some probability if neighbouring cell is empty try to create a room
6. If 5) succeed in creating a room add its coordinates to the room list
7. Repeat 5) and 6) until you reach desired number of rooms on the map (as defined in 2))

Problems while creating match game involves:

1. Matrix in Stencyl - creation, adding value
2. Generating map
3. Not getting caught in endless or inefficient loop while generating map
4. 
   Creating exits upon entering the room
5. Updating matrix while moving to another room

Working example:

In my Stencyl game there are green squares representing exits from the current room. You click on the square to move to the other room. The map of rooms is generated in console(2- current room, 1- room, 0 - empty space). The map is updated after each switching of the room.

The solution was made for problem where you can move from room in 4-way fashion(up, down, left, right), no diagonal movement is allowed.

Creating matrix:

Stencyl does not support matrix so we need to handle it on our own. If you ask on forum about "how do I make matrix in Stencyl?" the answer you are most likely to get is "create list of lists". It does work however we will present different approach. Using width of matrix we can write matrix as list and use it as matrix by properly translating the (x,y) into list index.

Input Matrix (M)

Matrix written as list(List) - yellow numbers are equal to the index in list

Let's assume in our matrix we start counting from 0 in both rows and columns so M(0,0)=10. In order to get M(x,y) from M represented as list we take List(width of matrix*y+x). For example we want to get M(1,2)=12. We have our matrix written as list and we know that the width of matrix is 5. We get list(5*2+1)=list(11)=12. Similar thinking can be done in order to put value into Matrix.

Generating map:

Map generation goes according to algorithm. 

 

Start - upon entering the room

<do after> is important because we will have plenty of custom events along the way and Stencyl can't see them in "When created" moment so we give him some time - as little as possible. We set width and height of maze. If there is no map generated we go to generating the map. Then we create exits based on current room we are in.

Generate map - part I

We set numbers of rooms we want to create. Then we check if there is enough place in the matrix for the rooms. We create empty list filled with 0s; 0 marks place in matrix where is no room. (As check) we print empty list to console. We pick our starting cell for building maze. We move to actual map generation: <generate_maze2>. 

 

Generate map - part II

We mark with 1 our starting cell. (As check) we print matrix to console with 1 in place cell where we start.

Generate map - part III

We add x and y to the list of rooms. In while loop(Generate map - part IV) we generate rooms until numbers of generated room will be equal to number of rooms that we wanted to create. <helper_2> is used to move through the list of already created rooms.

Once we are out of loop we print generated map to console. We set it as game attribute <map matrix> so that we won't lose it while switching between rooms. We set <2> in matrix in order to mark our starting position.

Generate map - part IV; pick the already created room and check neighbours around the picked room, if any of them is empty try to create room(using room_check)

<helper_3> stores the index under which there is x coordinate of already created room. List is created in such way that under index <helper_3>+1 there is y coordinate of already created room. <Remainder+length of list> construction makes sure we won't ask indexes out of list.

The rest of the code says for each of the neighbouring cells(top,down, left, right) try creating the room(Generate map - part V).

Generate map - part V; For current neighbour if its empty space (0 in matrix) try to create room from it

Two ifs at the beginning check if input values(coordinates of matrix cell) are ok = are they corresponding to cell inside the matrix. Code then asks about value inside the cell. If it's zero(= there is no room there) and there was no error while asking about the value we try to make it from free space into room.

There is a random chance that current free space will become a room. If the probability test is passed empty space is changed into room(Generate map - part VI).

Generate map - part VI; change empty space into room

Increase number of already created room by one. Add coordinates of newly created room to the list of rooms. Change value inside matrix from 0 to 1(in the coordinates of newly created room).

Generate exits upon entering the room

Generate exits based on your coordinates of the current room

This code triggers upon entering the room. Once we have our map generated we ask cells in map that are neighbours of the current one if they are rooms(=1) or empty spaces(=0). If they are rooms we create exits actors that lead to them. We set attributes of the exits so that each exit knows where it leads. We will need that in formation to move to another room when we click on exit.

Change of room upon clicking exit

Change rooms when you click on exit

Firstly we check if we clicked on exit actor(using 2 ifs). If we clicked on exit actor we change to 1 value in map as we are living the current room. Exit actor knows to which room it leads using X and Y attributes. We update the current room based on information from exit actor, we change the value in map to 2. Then we reload the scene with new X_room and Y_room.

It may seems strange why we are reloading the scene instead of switching it. In my solution things specific to the current room(such as monsters or items) are generated on room creation based on value of variables X_room and Y_room.

Further development

The present algorithm creates a map that has all rooms connected to the neighbours. It's good because there are no islands which can crush the game. On the other hand to make things more interesting it would nice to add walls between rooms, so that even if there are two rooms next to each other there can be wall between which would prevent creation of exit and making things to easy for player.

Tags:

Stencyl, maze, Metroid, Zelda, RPG, room