Friday, 2 January 2015

Procedural Generation - Part One - Making A Dungeon

Procedural generation is a technique used in computer graphics, simulations and games to create content on demand. For example, the worlds in Minecraft are not installed with the game, they are created by algorithms whilst the game is being played. Often the algorithms introduce variations to allow unique content to be created every time the game is played. Fractals are an example of procedural generation as are many on the HTML5 demos on this blog.

This is the first in a series looking at Procedural Generation using Dart. The example will be generating a 2D dungeon as might be found in a game such as NetHack.

First step is to create some utility classes to create a map and store information at each point.

// Block is the smallest unit of a map.
class block {
  int base = VOID;

// Point - cell on the map.
class point {
  int x = 0;
  int y = 0;
  point(this.x, this.y) {}

// Rectangle - defines a rectangular area on the map.
class rectangle {

  int x = 0;
  int y = 0;
  int width = 0;
  int height = 0;
  int x2 = 0;
  int y2 = 0;

  rectangle(this.x, this.y, this.width, this.height) {update2ndPoints();}

  point getMidPoint() => (new point(x + (width / 2).round(), y + (height / 2).round()));

  void update2ndPoints() {
    x2 = x + width;
    y2 = y + height;

The generation algorithm will add a requested number of rooms and then connect them via corridors. Walls will then be added around rooms and corridors. Finally corners where walls meet are marked on the map. Of course, we want to actually see the dungeon so to start with will display it in text in a much simplified form.

Code is available on Github and a live demo is available here. Hitting the button a few times shows how many varied dungeons can be.

Next time we will look at providing a Canvas display instead of text.