Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Unreal Engine - Maze

What do you need to build a maze?

To begin we need a construct that will hold a logical representation of our maze, this is achieved through the use of an Array. An array is constructed with dimensions derived from the size of the maze we wish to generate, this is then prepopulated with a series of placeholder values. Zeros representing walls and ones representing paths. An algorithm is then applied to walk through the maze and generate paths.

This example will only conside square mazes (Dimension x Dimension)

Blueprint

For Unreal I needed to create an array to hold the maze structure, this was where I encountered my first challenge, Unreal blueprints do not support 2D arrays! This meant I needed to think outside the box and use 1D arrays. To use a 1D array I would need some method to keep track of which logical row and column a value belonged to. For an example let’s assume we want to generate a maze on with dimensions 10 x 10. This gives us 100 cells to work with and in a 1D array with index values 0 - 99. So how do we generate x and y co-ordinates? based on the index number and the number of tiles per row. E.g. index number 15 in a Grid of size 10. We can do some maths to calculate position.

X = Floor (Fraction(Index / Dimension ) x Dimension )

Y = Floor (Index / Dimension )

What does this look like?

Maze - Index shown as grid

Maze - Index converted to co-ordinates

Navigation

So we can calculate a grid of co-ordinates using just a 1D array, however there is another problem. When we want to navigate in our array we still only have the index to work with. How will we cope with this? As an example lets consider that we are in cell 45 and we want to see who are neighbours are. 

North Cell = Current Index - Dimension (35)

East Cell = Current Index + 1 (46)

South Cell = Current Index + Dimension (55)

West Cell = Current Index - 1 (44)

Ok great! we can find our neighbours, but look what happens when our cell is on the edge of grid, lets use cell 59 as an example.

North Cell = Current Index - Dimension (49)

East Cell = Current Index + 1 (60)

South Cell = Current Index + Dimension (69)

West Cell = Current Index - 1 (58)

So we can see that the east cell is calculated as 60, this is actually the first cell on the next row in our maze. We need some way of getting round this limitation of using a 1D array. The answer is to identify all the cells that form a virtual border around the edge of our maze and add these into an array we can check. All our maze calculation from here on out will be based on a grid within a grid. By doing this we can be sure our navigation rules will only return values that are vaild.

Maze - Index with border tiles identified

Navigation Cont.

Lets take cell 28 to work with. Now we have borders identified we can include a check for InBorder and return null for a given direction if it ends up being in the border. 

North Cell = InBorder(Current Index - Dimension) = No (18) 

East Cell = InBorder(Current Index + 1) = Yes (null)

South Cell = InBorder(Current Index + Dimension) = No (38)

West Cell = InBorder(Current Index - 1) = No (27)

In creating the border array we no have a workable method for traversing our maze within a maze

 

Next Post

Please follow this link for the next post in the series