How to Procedurally Generate a Dungeon in Phaser – Part 1

Some games have a fixed number of levels created by a level designer. This way, the designer can create the levels so as to provide the desired gameplay experience to the player. However, it reduces the replay value of the game, since the levels will always be the same every time they are played.
Another alternative is to procedurally generate levels using an algorithm instead of a level designer. This results in a virtually infinite number of levels, and the player will never play the same level twice. However, since the game designers have no full control on the levels, they probably won’t be so good as if they were generated by a experienced level designer.
Each kind of game level (manual or procedural) has advantages and disadvantages, and can be applied in different kinds of games (both strategies could even be used in the same game). In this tutorial, we will procedurally create a dungeon with multiple rooms, using a simple algorithm. Notice that there are several ways of doing so (as you can check here), and each one can be recommended for a specific kind of game. So, if you’re building a game and need procedurally generated content (not just levels), take a look in different approaches to see which one better fits your game.
First, I will explain the algorithm we are going to use to generate our dungeon. Then, we will build a demo that creates a dungeon with multiple rooms and load them using Tiled maps.
To read this tutorial, it is important that you’re familiar with the following concepts:

  • Javascript and object-oriented concepts.
  • Basic Phaser concepts, such as: states, sprites, groups and arcade physics
  • Creating maps using Tiled

Learn Phaser by building 15 games

If you want to master Phaser and learn how to publish Phaser games as native games for iOS and Android feel free to check Zenva‘s online course The Complete Mobile Game Development Course – Build 15 Games.

Source code files

You can download the tutorial source code files here.

Creating the Tiled maps

We will start by creating room templates using Tiled for each possible room in our game. Then, our game will load the correct room map according to the current room configuration. For example, if the player is currently in a room with a single door in the north direction, it should load the “room_N.json” map.

The figure below shows an example of room created using Tiled. If you’re not familiar with Tiled, you can check one of my previous tutorials, where I cover it with more details. Even if you’re familiar with it, I highly suggest using the maps provided by the source code, since it is necessary to create one for each room configuration (resulting in a total of 15 maps). If you still wish to create your own maps, the only required things to follow is that you must create a layer called collision with a collision property set to true, and you must set the object properties as shown below, as this will be required for our demo.

maplayer_properties object_properties

The Dungeon Generation Algorithm

We’re going to procedurally generate a dungeon with multiple rooms in a grid structure. We will do that by creating a given number of rooms by traveling a grid, and then connecting the neighbor rooms.
Given a grid and a desired number of rooms “n”, we generate the dungeon with the following steps:

  1. Add the cordinate of the middle of the grid in a list called “rooms_to_create”
  2. While the number of created rooms is less than “n”, repeat:
    1. Get the first coordinate in “rooms_to_create”
    2. Create a room with this coordinate
    3. Add this room in a “created_rooms” list
    4. Add a random number of neighbor coordinates of the current room to “rooms_to_create
  3. After all rooms are created, connect all neighbor rooms

Notice that, for this algorithm to work we must guarantee that each iteration of the while loop in step two adds at least one new room to “rooms_to_create”, so the algorithm may continue until all rooms are created. We guarantee that by making the grid big enough so the dungeon can always be expanded to any direction (this is possible if the width and height of the grid is twice the number of rooms, for example) and by forcing the last step of the while loop to always add at least one neighbor coordinate to “rooms_to_create”.
The code below shows the implementation of this algorithm. The algorithm is implemented in the “generate_dungeon” method. First, it initialize the grid with its dimensions equals twice the number of rooms, and add the middle coordinate to the “rooms_to_create” list. Then, the while loop repeats the process described by the algorithm, creating a new room and adding a random number of neighbors to “rooms_to_create”. After creating all rooms, it iterates through all of them connecting them.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.Dungeon = function (game_state) {
    "use strict";
    this.TILE_DIMENSIONS = new Phaser.Point(32, 32);

    this.game_state = game_state;
};

ProceduralGeneration.Dungeon.prototype.generate_dungeon = function (number_of_rooms) {
    "use strict";
    var grid_size, rooms_to_creates, current_room_coordinate, current_room, created_rooms, initial_room_coordinate, final_room_coordinate, max_distance_to_initial_room, distance_to_initial_room;
    // initialize the grid
    grid_size = 2 * number_of_rooms;
    this.initialize_grid(grid_size);

    // add the middle coordinate as initial
    initial_room_coordinate = new Phaser.Point((grid_size / 2) - 1, (grid_size / 2) - 1);
    rooms_to_creates = [];
    rooms_to_creates.push({row: initial_room_coordinate.y, column: initial_room_coordinate.x});
    created_rooms = [];
    // iterate creating rooms
    while (rooms_to_creates.length > 0 && created_rooms.length < number_of_rooms) {
        current_room_coordinate = rooms_to_creates.shift();
        // create room with current coordinate
        current_room = new ProceduralGeneration.Room(this.game_state, current_room_coordinate, this.TILE_DIMENSIONS);
        this.grid[current_room_coordinate.row][current_room_coordinate.column] = current_room;
        created_rooms.push(current_room);
        // add random number of neighbors to rooms_to_create
        this.check_for_neighbors(current_room, rooms_to_creates);
    }

    // iterate through rooms to connect them
    created_rooms.forEach(function (room) {
        room.neighbor_coordinates().forEach(function (coordinate) {
            if (this.grid[coordinate.row][coordinate.column]) {
                room.connect(coordinate.direction, this.grid[coordinate.row][coordinate.column]);
            }
        }, this);
    }, this);

    return this.grid[initial_room_coordinate.y][initial_room_coordinate.x];
};

ProceduralGeneration.Dungeon.prototype.print_grid = function () {
    "use strict";
    var row_index, column_index, row;
    for (row_index = 0; row_index < this.grid.length; row_index += 1) {
        row = "";
        for (column_index = 0; column_index < this.grid[row_index].length; column_index += 1) {
            if (this.grid[row_index][column_index]) {
                row += "R";
            } else {
                row += "X";
            }
        }
        console.log(row);
    }
};

ProceduralGeneration.Dungeon.prototype.initialize_grid = function (grid_size) {
    "use strict";
    var row_index, column_index;
    this.grid = [];
    // initialize all rooms as null
    for (row_index = 0; row_index < grid_size; row_index += 1) {
        this.grid.push([]);
        for (column_index = 0; column_index < grid_size; column_index += 1) {
            this.grid[row_index].push(null);
        }
    }
};

ProceduralGeneration.Dungeon.prototype.check_for_neighbors = function (room, rooms_to_creates) {
    "use strict";
    var coordinates_to_check, available_neighbors, number_of_neighbors, neighbor_index, random_number, room_frac, available_neighbor_index;
    coordinates_to_check = room.neighbor_coordinates();
    available_neighbors = [];
    // find neighbor coordinates that are free
    coordinates_to_check.forEach(function (coordinate) {
        if (!this.grid[coordinate.row][coordinate.column]) {
            available_neighbors.push(coordinate);
        }
    }, this);
    // select random number of neighbors
    number_of_neighbors = this.game_state.game.rnd.between(1, available_neighbors.length - 1);

    // select the neighbor coordinates
    for (neighbor_index = 0; neighbor_index < number_of_neighbors; neighbor_index += 1) {
        random_number = this.game_state.game.rnd.frac();
        room_frac = 1 / available_neighbors.length;
        // assign a range to each neighbor and select the one whose range contains room_frac
        for (available_neighbor_index = 0; available_neighbor_index < available_neighbors.length; available_neighbor_index += 1) {
            if (random_number < room_frac) {
                rooms_to_creates.push(available_neighbors[available_neighbor_index]);
                available_neighbors.splice(available_neighbor_index, 1);
                break;
            } else {
                room_frac += (1 / available_neighbors.length);
            }
        }
    }
};

The method “check_for_neighbors” is responsible for adding the random neighbors to “rooms_to_create”. First, it finds how many neighbor coordinates are not occupied yet, putting them in the “available_neighbors” list. Then, it selects the number of neighbors that will be created randomly, using Phaser random data generator (you can learn more of it, in Phaser documentation). Finally, for each neighbor coordinate to be created, it randomly chooses one of the available neighbors. This is done by assigning a range to each available neighbor and generating a random number between 0 and 1. The chosen neighbor is the one whose range contains the generated number. For example, if there are two available neighbors, the first one will be selected if the generated number is up to 0.5, otherwise the second neighbor is selected.
We still have to create our Room class, which is shown below. The room will have its coordinates and should be able to inform its neighbors and the name of its map file. The method “neighbor_coordinates” simply returns the neighbor coordinates in each direction. The method “connect” is used to define the neighbors that actually exist and the “template_name” method returns the name of the JSON map to be loaded for this room. This name always starts with “room_” and it’s followed by the directions that there are rooms, in clockwise order. For example, if the room has doors in the north, south and west directions, its template name is “room_NSW.json”.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.Room = function (game_state, coordinate, tile_dimensions) {
    "use strict";
    this.game_state = game_state;
    this.coordinate = coordinate;
    this.tile_dimensions = tile_dimensions;

    this.neighbors = {};
};

ProceduralGeneration.Room.prototype.neighbor_coordinates = function () {
    "use strict";
    var neighbor_coordinates;
    neighbor_coordinates = [
        {direction: "N", row: this.coordinate.row - 1, column: this.coordinate.column},
        {direction: "E", row: this.coordinate.row, column: this.coordinate.column + 1},
        {direction: "S", row: this.coordinate.row + 1, column: this.coordinate.column},
        {direction: "W", row: this.coordinate.row, column: this.coordinate.column - 1}
    ];
    return neighbor_coordinates;
};

ProceduralGeneration.Room.prototype.connect = function (direction, room) {
    "use strict";
    this.neighbors[direction] = room;
};

ProceduralGeneration.Room.prototype.template_name = function () {
    "use strict";
    var template_name;
    // the template name is room_ followed by the directions with neighbors
    template_name = "room_";
    this.neighbor_coordinates().forEach(function (coordinate) {
        if (this.neighbors[coordinate.direction]) {
            template_name += coordinate.direction;
        }
    }, this);
    template_name += ".json";
    return template_name;
};

Phaser states of our demo

We will save the level data of our demo in a JSON file, which will be read when it starts. The JSON file I’m going to use is shown below. This file will define the game assets and groups, which will be the same for any room. This way we can preload all the assets in a LoadingState and create all groups before loading the map. Since the map file will be different for each room, it will be passed as a parameter, instead of being defined in the JSON file.

{
    "assets": {
        "dungeon_tileset": {"type": "image", "source": "assets/images/terrains.png"},
        "hero_spritesheet": {"type": "spritesheet", "source": "assets/images/player.png", "frame_width": 31, "frame_height": 30}
    },
    "groups": [
        "doors",
        "heroes"
    ]    
}

Our demo will have four states: BootState, LoadingState, DungeonState and RoomState. The frist two states are simple and responsible for loading the game JSON file and all the necessary assets before starting any room. Their codes are shown below. You can see that BootState simply loads the JSON file in its “preload” method and starts the LoadingState in the “create” method. The LoadingState, by its turn, loads all the assets in the “preload” method, by using the asset type to call the appropriate Phaser method. When all assets are loaded, it starts the next state (in the “next_state” variable) in the “create” method.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.BootState = function () {
    "use strict";
    Phaser.State.call(this);
};

ProceduralGeneration.BootState.prototype = Object.create(Phaser.State.prototype);
ProceduralGeneration.BootState.prototype.constructor = ProceduralGeneration.BootState;

ProceduralGeneration.BootState.prototype.init = function (level_file, next_state, extra_parameters) {
    "use strict";
    this.level_file = level_file;
    this.next_state = next_state;
    this.extra_parameters = extra_parameters;
};

ProceduralGeneration.BootState.prototype.preload = function () {
    "use strict";
    this.load.text("level1", this.level_file);
};

ProceduralGeneration.BootState.prototype.create = function () {
    "use strict";
    var level_text, level_data;
    level_text = this.game.cache.getText("level1");
    level_data = JSON.parse(level_text);
    this.game.state.start("LoadingState", true, false, level_data, this.next_state, this.extra_parameters);
};
var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.LoadingState = function () {
    "use strict";
    Phaser.State.call(this);
};

ProceduralGeneration.LoadingState.prototype = Object.create(Phaser.State.prototype);
ProceduralGeneration.LoadingState.prototype.constructor = ProceduralGeneration.LoadingState;

ProceduralGeneration.LoadingState.prototype.init = function (level_data, next_state, extra_parameters) {
    "use strict";
    this.level_data = level_data;
    this.next_state = next_state;
    this.extra_parameters = extra_parameters;
};

ProceduralGeneration.LoadingState.prototype.preload = function () {
    "use strict";
    var assets, asset_loader, asset_key, asset;
    assets = this.level_data.assets;
    for (asset_key in assets) { // load assets according to asset key
        if (assets.hasOwnProperty(asset_key)) {
            asset = assets[asset_key];
            switch (asset.type) {
            case "image":
                this.load.image(asset_key, asset.source);
                break;
            case "spritesheet":
                this.load.spritesheet(asset_key, asset.source, asset.frame_width, asset.frame_height, asset.frames, asset.margin, asset.spacing);
                break;
            case "tilemap":
                this.load.tilemap(asset_key, asset.source, null, Phaser.Tilemap.TILED_JSON);
                break;
            }
        }
    }
};

ProceduralGeneration.LoadingState.prototype.create = function () {
    "use strict";
    this.game.state.start(this.next_state, true, false, this.level_data, this.extra_parameters);
};

The DungeonState will be responsible for generating the dungeon, and it is shown below. It initializes the Dungeon object in the “init” method and generate a new dungeon in the “create” method. After generating the dungeon it starts a RoomState with the initial room of the dungeon.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.DungeonState = function () {
    "use strict";
    Phaser.State.call(this);

    this.LEVEL_FILE = "assets/levels/room_level.json";
};

ProceduralGeneration.DungeonState.prototype = Object.create(Phaser.State.prototype);
ProceduralGeneration.DungeonState.prototype.constructor = ProceduralGeneration.DungeonState;

ProceduralGeneration.DungeonState.prototype.init = function (number_of_rooms) {
    "use strict";
    this.number_of_rooms = number_of_rooms;
    this.dungeon = this.dungeon || new ProceduralGeneration.Dungeon(this);
};

ProceduralGeneration.DungeonState.prototype.create = function () {
    "use strict";
    var initial_room;
    // generate new dungeon
    initial_room = this.dungeon.generate_dungeon(this.number_of_rooms);
    // start RoomState for the initial room of the dungeon
    this.game.state.start("BootState", true, false, this.LEVEL_FILE, "RoomState", {room: initial_room});
};

Finally, RoomState is where most of the game will run. In the “init” method it starts the physics engine, sets the scale and save data for other methods. In the “preload” method it loads the map file given by the room template name. Then, in the “create” method it creates the map, the map layers, the groups and the prefabs. Notice that when creating the layers we check for the collision property to make it collidable. The “create_object” method is responsible for creating the prefabs. First, it adjusts the positions, since Tiled and Phaser coordinate systems are different, then it instantiate the correct prefab using the “prefab_classes” property (initially empty). Notice that, this is possible because all prefabs have the same constructor, defined in their base class shown below.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.RoomState = function () {
    "use strict";
    Phaser.State.call(this);
    
    this.MAP_KEY = "room_tilemap";
    this.MAP_TILESET = "dungeon_tileset";
    
    this.prefab_classes = {
        
    };
};

ProceduralGeneration.RoomState.prototype = Object.create(Phaser.State.prototype);
ProceduralGeneration.RoomState.prototype.constructor = ProceduralGeneration.RoomState;

ProceduralGeneration.RoomState.prototype.init = function (level_data, extra_parameters) {
    "use strict";
    var tileset_index, tile_dimensions;
    this.level_data = this.level_data || level_data;
    
    this.scale.scaleMode = Phaser.ScaleManager.SHOW_ALL;
    this.scale.pageAlignHorizontally = true;
    this.scale.pageAlignVertically = true;
    
    // start physics system
    this.game.physics.startSystem(Phaser.Physics.ARCADE);
    this.game.physics.arcade.gravity.y = 0;
    
    // get current room
    this.room = extra_parameters.room;
};

ProceduralGeneration.RoomState.prototype.preload = function () {
    "use strict";
    this.load.tilemap(this.MAP_KEY, "assets/maps/" + this.room.template_name(), null, Phaser.Tilemap.TILED_JSON);
};

ProceduralGeneration.RoomState.prototype.create = function () {
    "use strict";
    var group_name, object_layer, collision_tiles;
    // create map
    this.map = this.game.add.tilemap(this.MAP_KEY);
    this.map.addTilesetImage(this.map.tilesets[0].name, this.MAP_TILESET);
    
    // create map layers
    this.layers = {};
    this.map.layers.forEach(function (layer) {
        this.layers[layer.name] = this.map.createLayer(layer.name);
        if (layer.properties.collision) { // collision layer
            collision_tiles = [];
            layer.data.forEach(function (data_row) { // find tiles used in the layer
                data_row.forEach(function (tile) {
                    // check if it's a valid tile index and isn't already in the list
                    if (tile.index > 0 && collision_tiles.indexOf(tile.index) === -1) {
                        collision_tiles.push(tile.index);
                    }
                }, this);
            }, this);
            this.map.setCollision(collision_tiles, true, layer.name);
        }
    }, this);
    // resize the world to be the size of the current layer
    this.layers[this.map.layer.name].resizeWorld();
    
    // create groups
    this.groups = {};
    this.level_data.groups.forEach(function (group_name) {
        this.groups[group_name] = this.game.add.group();
    }, this);
    
    this.prefabs = {};
    
    // create objects (prefabs)
    for (object_layer in this.map.objects) {
        if (this.map.objects.hasOwnProperty(object_layer)) {
            // create layer objects
            this.map.objects[object_layer].forEach(this.create_object, this);
        }
    }
};

ProceduralGeneration.RoomState.prototype.create_object = function (object) {
    "use strict";
    var object_y, position, prefab;
    // tiled coordinates starts in the bottom left corner
    object_y = (object.gid) ? object.y - (this.map.tileHeight / 2) : object.y + (object.height / 2);
    position = {"x": object.x + (this.map.tileHeight / 2), "y": object_y};
    // create object according to its type
    if (this.prefab_classes.hasOwnProperty(object.type)) {
        prefab = new this.prefab_classes[object.type](this, object.name, position, object.properties);
    }
    this.prefabs[object.name] = prefab;
};
var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.Prefab = function (game_state, name, position, properties) {
    "use strict";
    Phaser.Sprite.call(this, game_state.game, position.x, position.y, properties.texture);
    
    this.game_state = game_state;
    
    this.name = name;
    
    this.game_state.groups[properties.group].add(this);
    this.frame = +properties.frame;
    
    if (properties.scale) {
        this.scale.setTo(properties.scale.x, properties.scale.y);
    }
    
    this.game_state.prefabs[name] = this;
};

ProceduralGeneration.Prefab.prototype = Object.create(Phaser.Sprite.prototype);
ProceduralGeneration.Prefab.prototype.constructor = ProceduralGeneration.Prefab;

By now you can already try running the demo to see if its correcting loading the room maps. Try running multiple times and see if the initial room is changing.

dungeon

Navigating through the rooms

You may have noticed the Tiled maps provided in the source code have hero and doors prefabs, which will be used to allow our hero to navigate through the dungeon rooms. Now, we are going to implement them.
First, the Hero prefab code is shown below. The only thing it will do by now is walk, so it just needs a “walking_speed” property. In the “update” method we check for player input to move the hero, which is done with the “cursors” object. To properly control the hero, we move it to a given direction only if it is not already moving to the opposite direction. For example, the hero can move left only if it is not already moving right. Also, if the player is moving, we must play the walking animation, otherwise stop it.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.Hero = function (game_state, name, position, properties) {
    "use strict";
    ProceduralGeneration.Prefab.call(this, game_state, name, position, properties);
    
    this.anchor.setTo(0.5);
    
    this.walking_speed = +properties.walking_speed;

    this.game_state.game.physics.arcade.enable(this);
    this.body.collideWorldBounds = true;
    
    this.animations.add("walking", [0, 1], 6, true);
    
    this.cursors = this.game_state.game.input.keyboard.createCursorKeys();
};

ProceduralGeneration.Hero.prototype = Object.create(ProceduralGeneration.Prefab.prototype);
ProceduralGeneration.Hero.prototype.constructor = ProceduralGeneration.Hero;

ProceduralGeneration.Hero.prototype.update = function () {
    "use strict";
    this.game_state.game.physics.arcade.collide(this, this.game_state.layers.collision);
    
    if (this.cursors.left.isDown && this.body.velocity.x <= 0) { // move left if is not already moving right
        this.body.velocity.x = -this.walking_speed;
        this.scale.setTo(1, 1);
    } else if (this.cursors.right.isDown && this.body.velocity.x >= 0) { // move right if is not already moving left
        this.body.velocity.x = +this.walking_speed;
        this.scale.setTo(-1, 1);
    } else {
        this.body.velocity.x = 0;
    }

    if (this.cursors.up.isDown && this.body.velocity.y <= 0) { // move up if is not already moving down
        this.body.velocity.y = -this.walking_speed;
    } else if (this.cursors.down.isDown && this.body.velocity.y >= 0) { // move down if is not already moving up
        this.body.velocity.y = +this.walking_speed;
    } else {
        this.body.velocity.y = 0;
    }
    
    if (this.body.velocity.x === 0 && this.body.velocity.y === 0) {
        this.animations.stop();
        this.frame = 0;
    } else {
        // if not moving, stop the animation
        this.animations.play("walking");
    }
};

Now, we implement the Door prefab as shown below. It will have a “direction” property so we can know to where the player is navigating. In the “update” method we check for collisions with the hero, and if so, call the “enter_door” method. This method gets the next room using the door direction and starts a new RoomState for the next room.

var ProceduralGeneration = ProceduralGeneration || {};

ProceduralGeneration.Door = function (game_state, name, position, properties) {
    "use strict";
    ProceduralGeneration.Prefab.call(this, game_state, name, position, properties);
    
    this.anchor.setTo(0.5);
    
    this.direction = properties.direction;

    this.game_state.game.physics.arcade.enable(this);
    this.body.collideWorldBounds = true;
};

ProceduralGeneration.Door.prototype = Object.create(ProceduralGeneration.Prefab.prototype);
ProceduralGeneration.Door.prototype.constructor = ProceduralGeneration.Door;

ProceduralGeneration.Door.prototype.update = function () {
    "use strict";
    this.game_state.game.physics.arcade.collide(this, this.game_state.groups.heroes, this.enter_door, null, this);
};

ProceduralGeneration.Door.prototype.enter_door = function () {
    "use strict";
    var next_room;
    // find the next room using the door direction
    next_room = this.game_state.room.neighbors[this.direction];
    // start room state for the next room
    this.game_state.game.state.start("BootState", true, false, "assets/levels/room_level.json", "RoomState", {room: next_room});
};

Finally, we add both the Hero and Door prefabs to the “prefab_classes” property in the RoomState. And then, you can actually run the demo navigating through the different rooms in the dungeon.

this.prefab_classes = {
        "hero": ProceduralGeneration.Hero.prototype.constructor,
        "door": ProceduralGeneration.Door.prototype.constructor
};

hero
And this conclude this tutorial. In the next one we will populate the rooms with random obstacles and enemies. Then, we will add an exit, so the hero can leave the dungeon.