Stage 2 - Map Generation

In this step, we want to generate a map to play on.

A map is often stored as a 2D array, which is nothing more than an array where every element is another array. Specifically, our map will be an array of columns and each column will be an array of tiles. You could do it with rows, whatever, same thing. Make a new class called in tile.js. Each tile will have and coordinates, a (simply the numeric position in the spritesheet), and a flag. For the most basic maps, all you need to know is how to distinguish between walls and floors and does that for us. You can also see that we're using like we did for the player.

Let's extend to make floors and walls. We have the code for floor and wall tiles, but we need the sprites.

Drawing Map Tiles

In map.js, we're going to start making the map. This makes a 2D array called and populates it with about 30% walls and 70% floors.

It does so by looping over the columns and then, for each column, looping over the rows and creating new wall/floor tiles in each spot as appropriate. So our map is actually there and the way you can confirm this is by going into the dev tools and simply typing "tiles".

But let's draw it. All we need to do is iterate over every tile and call on it.

But first, I want to wrap access to the tile array in a function called . There are a lot of reasons for doing this. For one it reads a little cleaner, but it also lets us pull off shenanigans like returning tiles outside the bounds of the array and which don't actually exist (which might happen if, for instance, the player casts a giant area of effect spell that extends past the outer dungeon walls).
Now with that out of the way, we can get to drawing simply by looping over each tile and telling it to draw itself. Cool. We haven't added an outer wall though. Let's reuse the function to make one.

Only thing is the walls are not doing anything. We start on a wall and we're walking right through them!

To fix that first problem, we're simply going to teleport the player to a random floor tile when the game starts.

How do we find a random floor tile though? One really dumb, easy way to do so is repeatedly grab random tiles until we find a floor tile. This pattern works really well for a variety of map generation techniques: try to do something at random and keep doing it until we get it right. Add a timeout to make sure we don't get stuck in an infinite loop on accident. You don't want to lock up your browser after all.

We'll also need a simple utility function to generate random integers within a given range. Our function needs to be passed a callback that attempts something and returns only if it worked. That's why we're passing an anonymous function that rolls some random coordinates, gets the corresponding tile, and returns true only if the following expression is true: (the tile is passable and has no monster).

Notice that nowhere else in our program have we defined . Thanks to JavaScript's lenient property and type handling, this will work fine. A missing property will have a value of and that will get coerced to and we're good. Let's take out for a spin by teleporting the player to random tile as mentioned earlier. Refresh several times and you'll see that the player spawns in random locations, none of which are walls.

Our map is generated and our player is spawned in the correct place. We're almost done.

Banishing disconnected islands (a roguelike developer's greatest enemy)

One more big problem first and this one is a super common headache when procedurally generating the maps. With our extremely dumb way of making the levels, there are often areas of the map not connected to other areas. Disconnected islands. We need a way a check that everything is connected.

This part is a little tricky, so first let's some write some pseudocode: That's the basic idea. Now let's convert that into real code: They key here is . Imagine you are drawing a dungeon map on grid paper and you want to color in all the connected floor spaces. How would you do it?

One way is pick a random floor tile on the grid, expand outwards repeatedly, and color connected floor tiles until you're done. You obviously would ignore wall tiles and you wouldn't recolor floor tiles once you drew them the first time. That's exactly the idea behind the flood fill algorithm and here's more pseudocode for a function that does it: We'll convert that to JavaScript as well by breaking it down into several smaller functions: OK, that seems like a lot so let's break it down.

is pretty straightforward. It's a wrapper around . Even though it's a simple wrapper, this method is useful when implementing all sorts of mechanics. Also note that it works for more than just adjacent neighbors.

returns the adjacent neighbors of a tile and shuffles them before returning.

additionally filters out non-passable tiles (e.g. walls). is a nifty JavaScript array function where we pass in a callback and we return true for only the elements we want to keep.

does exactly what the pseudocode said. It uses again and also , which adds one array to another. And finally is an implementation of Fisher-Yates shuffle. All it's doing is a random swap for each element in an array, leading to a perfectly shuffled array.

To reiterate: we keep trying to make levels until we find one that has no disconnected islands. The way we know there are no disconencted islands is when we've made only a single connected "island". If we have one big island of floor tiles, the number of tiles on that island should match the total number of floor tiles on the map. When we're able to satisfy that condition, we're happy with our level and we can stop.

So now let's check our work. Refresh a bunch of times and you'll never see a disconnected island again. Just for fun, you might try out different values of . Here's what I got with a value of 24 (much higher and the timeout was usually reached): In the next section, we'll create our monsters and make sure the player can't walk through walls.