Blog de tfe, Perl, Web et Libre...?

Game creation: maze generation!

PubliƩ le 10/10/2016 dans threejs

Here is the article 9 about my series of posts about the game creation.

If you missed it, check out the previous part.

Maze generation

So now we have the moving character, we will have to close some doors to create a real maze.

To do that, i used this simple algorithm:

  1. Identify all cells as "not used"
  2. Current cell is 0,0
  3. Randomly choose a neighbor-cell which is not already used, and mark it as connected to the cell 0,0
  4. Current cell is the new connected cell
  5. Go to step 3 until no more "non-used" neighbor-cell found

In the image bellow, those are the cells connected from 1 to 7. The cells 8/9/10 are not connected right now.

Threejs Maze generation 1

When there is no more "non-used" cells close to the current cell, we will have to connect all non connected cells to the path created.

  1. Pickup a "non-used" cell
  2. Connect it to a near-connected cell (if one is present)

After creating the maze, we have to randomly pick 2 cells for the start and end positions:

Threejs Maze generation 2

Here is the final result:

You can get: the source code or View the demo directly.