The worst part of programming your own game is the fact that it’s hard to enjoy a game you know inside and out. It’s no fun finding the secret treasure chest on stage 4 when you’re the one who put it there in the first place.

One solution to this is to randomize your content. If the exact setup of the map changes every time you open the program then suddenly even the creator can be surprised by the outcome of his game.

Of course, in a serious game project you have to balance the replay value of a game that is always different against the high quality of a game that was crafted entirely by hand. Turns out “infinite replay value” isn’t so valuable if all your random content is boring.

But this is a programming project! We don’t care about the end user, we just want to practice writing cool stuff and a random dungeon generator would be a cool thing to add to our little mini browser maze.

It Sure Is Dark In Here…

Before we go write a program for building an entire random dungeon let’s make sure our engine can actually handle something bigger than the 2×2 closet we’ve been experimenting with so far. Update your maze generator function with the following code to make it 3×3 instead.

var mazeGrid = [Array(3), Array(3), Array(3)];

mazeGrid[0][0] = new MazeCell(true, false, false, true);
mazeGrid[0][1] = new MazeCell(true, false, false, false);
mazeGrid[0][2] = new MazeCell(true, true, false, false);
mazeGrid[1][0] = new MazeCell(false, true, false, true);
mazeGrid[1][1] = new MazeCell(false,true,true,true);
mazeGrid[1][2] = new MazeCell(false,true,false,true);
mazeGrid[2][0] = new MazeCell(false,true,true,true);
mazeGrid[2][1] = new MazeCell(true,false,true,true);
mazeGrid[2][2] = new MazeCell(false,true,true,false);

return mazeGrid;

Now load up your maze, walk around a bit and see if you can see any problems. Or more accurately if you can NOT see any problems.

That’s right, half your walls are missing!

You first instinct here is probably to double check your mazeGrid definition and see if maybe there was a problem with the code I gave you to copy paste. Maybe a few walls were accidentally left out or pointing the wrong direction? But have a little more faith in me! That maze definition is perfect.

The real problem here is lighting. Our entire maze is currently lit by a single point light that hangs out in in the middle of the <0, 0> cell. That means that only walls facing towards <0, 0> get any light*, and now that our maze is a little bigger we have a lot of walls that face away from it.

Several options here. We could replace the point light with a universal light source. Or we could add more point lights as the maze grows. But I think the best choice is just to have our one light follow along with the player to give him that sort of “Adventurer with a lantern/torch/flashlight” feeling.

This is also really easy to do. Just go to the end of your “state == MOVING_FORWARD” code and add this:

playerPointLight.position.x = camera.position.x;
playerPointLight.position.y = camera.position.y;
playerPointLight.position.z = camera.position.z;

Now the light will update it’s location at the same time the player does. No more pitch black invisible walls. That means we’re ready to randomize our maze.

Roll The Dice, Build Some Walls

There are a LOT of different ways to randomly generate a maze, each with their own strengths and weaknesses. In particular a lot of the simpler algorithms have predictable patterns that make them trivially easy to solve.

But for a first person dungeon crawler this isn’t really a big deal. A pattern that would be obvious when seeing the maze from above can still be tricky to exploit when you can only see the walls and passages right around you.

So lets get our feet wet by using one of the simplest maze generation algorithms out there.

1)Start with a maze full of closed off cells.

2) For every cell randomly open a path either to the west or to the north.

That’s it. Despite its extreme simplicity this algorithm is guaranteed to create a maze where every single cell is reachable from any other cell; no cells ever get fully blocked off. This means the player can always get to the exit from the entrance or, in our case, to the collectables from their starting point.

The weakness of this method is that it creates one long boring hallway all along the western and northern edges of the maze. This is because the cells along the west wall can’t open a path to the west without going out of bounds and so instead have to all link to the north. Similarly the cells along the north can’t open any paths to the north without going out of bounds so they all have to link to the west.

But that’s an acceptable tradeoff for an algorithm so simple we can program it in a few dozen lines of JS.

First off we need to redefine our function to accept a width and height so we can tell it how big we want our random maze to be. Our inner function/object MazeCell can stay the same:

function createMazeGrid(width, height){
   function MazeCell(northWall, eastWall, southWall, westWall){
      this.northWall = northWall;
      this.eastWall = eastWall;
      this.southWall = southWall;
      this.westWall = westWall;
   }

We can then use that width and height to build a starting maze where every single cell is completely closed off. This will replace the hand-crafted array we used to have:

var mazeGrid = Array(height);

for( var i = 0; i<height; i++){
   var row = Array(width);
   for(var j = 0; j<width; j++){
      row[j] = new MazeCell(true,true,true,true);
   }
   mazeGrid[i] = row;
}

You could even end the function right there with a return mazeGrid, although the end result would just leave you trapped in a 1 x 1 prison forever. That would make for a horrible game experience so let’s move on and start knocking down walls.

Looping through the maze and randomly opening a passage either to the west or north in every cell seems like a simple algorith, but there are a couple pitfalls to watch out for.

1) The origin shouldn’t try to open a passage

2) If a cell is on the west edge it should always open a passage to the north

3) If a cell is on the north edge it should always open a passage to the west

Also don’t forget that when opening a passage you need to modify two cells, not just one! For instance, to create a western passage from <2,1> to <1,1> it’s not enough to just remove the west wall from <2,1>, you also have to remove the east wall from <1,1>.

//Randomly open a west or north passage in every possible cell
for( var i = 0; i<height; i++){
   for(var j = 0; j<width; j++){
      if(i>0 && j>0){ //If it is not an edge cell open a passage randomly
         if(Math.random()>0.5){
            mazeGrid[i][j].northWall=false;
            mazeGrid[i-1][j].southWall=false;
         }
         else{
            mazeGrid[i][j].westWall=false;
            mazeGrid[i][j-1].eastWall=false;
         }
      }
      else if(j > 0){ //If it is along the north edge open a west passage
         mazeGrid[i][j].westWall=false;
         mazeGrid[i][j-1].eastWall=false;
      }
      else if(i > 0){ //If it is along the west edge open a north passage
         mazeGrid[i][j].northWall=false;
         mazeGrid[i-1][j].southWall=false;
      }
   }
}

This is one of those big but easy to understand functions. For every non-edge cell we choose to randomly create a west or north passage by calling Math.random(). This function returns a decimal value between 0 and 1 so by checking whether it is bigger than 0.5 we should get a mostly even mix of west and north passages.

Of course for the edge cells we don’t need any random math. We just build the only possible passage. Just be sure you know which edge you’re on! The way this code checks for things is kind of counter-intuitive. Basically we know that if (i>0 && j>00) failed that means we are on one of the two edges. We then use j > 0 to prove we are NOT on the west edge, meaning we have to be on the north edge. If that fails we use i > 0 to prove we are NOT on the north edge, so we have to be on the west edge.

And if they both fail? We must be in the corner and don’t need to open any walls at all.

You can see this all in action by updating your main function. Just replace the old createMazeGrid() call with something like: var mazeGrid = createMazeGrid(5,5);

Feel free to build even bigger mazes if you want. Our wall objects are pretty simple so you can probably place quite a few before your computer has too much trouble. A ten by ten maze with a hundred cells should be perfectly doable, for instance.

Still Not Random Enough

Now that we can build a random maze there’s a handful of final touches I’d like to try and implement to make it feel more like a real game. Specifically I’d like to also randomly place the collectibles and make it so grabbing them all triggers some sort of “win” condition. That shouldn’t be very hard but this post is already getting pretty long so let’s put it off until next time.

* Interesting note: The simple point light can shine through walls. As long as a wall is pointing towards the light it doesn’t matter if other objects are in the way. This is fine for our simple maze but more complex games would probably want to have shadows along with lights. Can ThreeJS do that? Probably! Go read the docs.

Somebody Keeps Leaving Their Collectables Lying Around The Dungeon

While our game engine has basic movement it’s honestly still pretty boring, mostly because it’s pointless. You walk around a little maze, look at the walls and then eventually give up and close the browser window. There is no goal to work towards, no way to win or to tell if you are doing good or bad.

That’s why real dungeon crawlers have monsters and treasure chests and traps and special events and also why even the most amateur of rural corn mazes makes sure to include something like an exit to look for.

Now obviously we’re not going to try and build an entire RPG framework in a single Let’s Program, but we can at least try to add one interesting feature: some collectibles that the player can hunt for while exploring the maze.

Our requirements are simple: We want floating cubes that we can place on our map. When the player enters the same square as a cube “something” should happen, like a message being displayed. The floating cube should then disappear.

Like all non-trivial programming problems there are roughly a zillion different ways to accomplish this and I almost got sucked down an infinite rabbit hole of trying to figure out the best way to build a collectible system that could later be expanded into a full on custom event system.

That was dumb. Carefully planning out code is important but at some point you have to just give things your best shot and write some code. If it isn’t perfect you can always rewrite it.

So here’s the coding plan:

– We will have an array of “collectible” objects.

– Each collectible will keep track of it’s x location, y location, and what code to run when triggered.

– While setting the maze up we will loop through the “collectible” array, add a 3D cube to the scene for each collectible and then store a reference to that object inside the collectible.

100% Hand Crafted Artisanal Collectables

Let’s get started by writing a standalone function that returns an array of collectible objects. This way we can expand or change how this works without cluttering up our main dungeon code. Since this is just our prototype we will manually build an array and then manually push two manually built anonymous collectable objects onto it:

function createCollectiblesList(){
   var collectables = [];

   collectables.push(
      {
         x:0,
         y:1,
         action:function(){alert("You picked up a collectable");},
      });

   collectables.push(
      {
         x:1,
         y:0,
         action:function(){alert("You picked up a different collectable");},
      });

   return collectables;
}

Now that we have a sample collectable array let’s write a second function that can use that array to add some collectables to the map. Collectables that will be represented as dark blue cubes 1/4th as wide as our 1 unit maze cells. Only tricky part here is that because I did a horrible job of lining our 3D space up with our with our map grid our collectable’s X position will map to Z in the 3D plane and it’s Y will map to X.

function placeCollectableGraphics(scene, collectables){
   var collectableGeometry = new THREE.BoxGeometry( 0.25, 0.25, 0.25 );
   var collectableMaterial = new THREE.MeshStandardMaterial( {color: 0x000088} );

   collectables.forEach(function(collectable){
      var collectableObject = new THREE.Mesh(collectableGeometry, collectableMaterial);
      collectableObject.position.z = collectable.x;
      collectableObject.position.x = collectable.y;
      scene.add(collectableObject);
   });
}

Wow. I really need to get around to rotating 3D space so it matches grid space better. But for now let’s just give our prototype a test run by inserting these functions into the setup portion of our runMaze function.

function runMaze(){
   var mazeCanvas = document.getElementById("mazeCanvas");

   var scene = new THREE.Scene();
   var renderer = new THREE.WebGLRenderer({ canvas: mazeCanvas });
   var camera = new THREE.PerspectiveCamera( 75, mazeCanvas.width/mazeCanvas.height, 0.1, 1000 );

   var mazeGrid = createMazeGrid();
   placeWallGraphics(scene, mazeGrid); 
   
   //New lines
   var collectables = createCollectiblesList();
   placeCollectableGraphics(scene, collectables);

   //Rest of function as normal

Look around the maze now and you should see a blue box to the east and south of the starting location.

Hmm.. that’s a little bit boring. Let’s spice things up by making them spin. All we have to do is add a bit of code near the end of our constantly repeating render function. Put this right after all the switch statements based on player state but before the recursive call to render:

//Make our collectables spin
collectables.forEach(function(collectable){
   var collectableObject = collectable.objectRef;
   collectableObject.rotation.x += 2 * deltaTime/1000;
   collectableObject.rotation.y += 2 * deltaTime/1000;
});

Now for our last bit of functionality: When the user enters a block with a collectable the collectable’s function should trigger.

To implement this we are going to modify the code that runs when the player is MOVING_FORWARD. When this code detects the player has fully entered the new square it should cross reference the collectables list and look for matches before returning the player to the WAITING loop, which we can do with something like this:

if(state == MOVING_FORWARD)
{
   walkingDistance += 1 * deltaTime/1000;

   if(walkingDistance >= 1){
      walkingDistance = 1;
      state = WAITING;
      processCollectableCollisions(player.gridX, player.gridY,collectables,scene);
   }

   //Rest of the function stays as is

Pretty easy, mostly because we tossed all the hard work onto the processCollectableCollisions function. All we have to do is tell it what X and Y location the player is looking at along with what list of collectables and scene it should reference and it does all the hard work for us! Or at least it will after we write it.

Fortunately it’s not that hard to write. We just loop through the provided collectables and see if any match the provided player location. If we find a match we trigger the code linked to that collectable and then remove the collectable from both the 3D scene and from the list of collectables. Don’t want the player picking the same object up twice!

function processCollectableCollisions(x, y,collectables,scene){
   collectables.forEach(function(collectable,index){
      if(collectable.x == x && collectable.y == y){
         collectable.action(); //Run the object's event
         scene.remove(collectable.objectRef); //Remove graphics from scene
         collectables.splice(index,1); //Remove collectable from list
      }
   });
}

A little bit messy and the functional programmer in me hates the way the function deletes items from the array given to it… but it works! More or less. I think the way we’re using splice might break down if we ever have two collectables with the same X and Y location but for a rough draft prototype this will get the job done.

Beyond Collectables

Our only goal was to program a couple of collectables but we actually managed to prototype a pretty powerful event system. This is because we can put literally any JavaScript we want inside of collectable.action. Right now it just triggers an alert but there’s no reason we couldn’t have it increment a score or teleport the player across the map or add an item to their inventory or trigger a cutscene.

OK, we don’t have an inventory to add to or any cutscenes to trigger but if we took the time to program those sorts of things we could link them to our collectables pretty easily.

And what if instead of making all the collectables cubes we made it possible to assign them each different symbols? Treasure chests and warning signs and keys and silhouettes. Maybe even an invisible option for when we want something to happen on a certain square without the player seeing it ahead of time.

Now you have a flexible system for making any sort of location based event you can imagine. And while that’s not quite enough for building a complete dungeon crawler it would be a pretty good start.