A navigable randomly generated multi-level maze.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.vscode
build
src
test
.gitattributes
.gitignore
README.md
maze-gameplay.gif
package-lock.json
package.json
tsconfig.defaults.json
tsconfig.json
tslint.json
webpack.config.js

README.md

Maze of Seasons

Navigate through a randomly generated multi-level maze towards your goal (the checkered flag). When you hit a wall, change the season.

Gameplay

Here's what it's like to play the game (fast-forwarded quite a bit):

GIF showing gameplay

On desktop there's some keyboard shortcuts (hidden by CSS until the screen is large enough)... also, keypress events are so cool.

The code

I wrote almost everything in TypeScript - it's easier for debugging than JavaScript, and static types are wonderful.

I initially used jQuery in the View and Character classes because I wanted some practice with the library. Since then I've converted to using vanilla JavaScript.

This was my first time using CSS Grids to handle the layout. (Definitely using grids again... so much nicer than floats!)

Growing Tree Algorithm

I needed a bit of mental gymnastics to get my head around the growing tree algorithm. It's a method of creating a maze out of a grid. Here's the steps.

1. Create a multi-level array (a grid)

My grid:

  • z: 4 (levels/seasons)
  • y: 8 cells (rows)
  • x: 8 cells (columns)

Each cell is an object from the Cell class.

Cells have cardinal directions (North, South, East, West, Up a layer, Down a layer). Those directions can be true or false.

  • true: indicates a path that direction
  • false: indicates a wall that direction

For details on each class see the declaration file at: build/maze.d.ts

2. Create a temporary cell stack to hold the cells as you create them

As a cell is created, it's added to the stack, before the end of this process, it'll be removed.

For this project, I used an array as JavaScript and TypeScript don't explicitly have stacks.

3. Choose a starting point on the grid

I used z:0 y:0 x:0.

4. Choose a direction at random

North, South, East, West, Up a layer, Down a layer

If you can't go that way, (the cell is already full) choose a different direction.

5. Once you find a direction you can go:

  • Add it to the stack of cells.
  • Add the cell to the grid.
  • Set the current cell's direction to true and the next cell's reverse direction to true

e.g.:

Cell#1
location:	grid[0]0][0] -> grid[z][y][x]
North:	false
South:	false
East:	false
West:	false
Up:	false
Down:	false

// direction chosen: South
// Every false will become a wall if it doesn't eventually point at a cell

Cell#1:
location:	 grid[0][0][0]
North:	false
South:	true
East:	false
West:	false
Up:	false
Down:	false

Cell#2:
location:	 grid[0][1][0]
North:	true
South:	false
East:	false
West:	false
Up:	false
Down:	false

6. Keep going until you can't move in any direction

All of the directions have cells in them.

7. Backtrack until you can go another direction

To backtrack, we pop the last cell off the cell stack and start the process over at step 4.

8. Repeat steps 4-7 until you've filled the entire maze

The number of cells left on the stack will be zero (we backtracked all the way to the beginning.)

See links in Credits to Jamis Buck's work for more details.

Display

1. Loop through the multi-layer array (the grid)

// grid[z][y][x] = grid[layer][row][column]

2. If a direction is false, set that border wall

In CSS parlance: top border, east border, south border, west border

location:	grid[0]0][0]
North:	false	= border top
South:	true	= transparent border (a path)
East:	false	= border right
West:	false	= border bottom
Up:	false
Down:	false

Up and Down aren't used for display in my maze.

TO DO

Procedural mazes

I now have the ability to generate procedural mazes. I'll use that to create different levels that users can try.

Next I'm creating a maze solving class (CharacterNavigator) to determine how difficult a maze is to solve based on how many moves it takes to solve. It's not going to be perfect since there's

Location of "IsMazeSolved"

Currently the maze is marked as "solved" in Character/ICharacterView, logically it makes more sense to have that in Maze, should I change that?

Re-design in canvas?

Might want to go to using canvas and making it look good.

Check out Localstorage to hold procedural mazes?

Credits

This project would not be possible without Jamis Buck and his posts on Maze Generation: Growing Tree algorithm and Minecraft Maze Generator. My algorithmic and display code borrows heavily from his, and lessons learned in his blog posts.

The icons are from Vecteezy, go check them out.