Procedurally Generated Top View 2D RPG Map Generation

Question

Procedural generation is a fascinating concept and is gaining popularity in the gaming industry. The thought of playing a game that has new content every-time the game is played is very exciting to me.

My question is how would I go about generating top view 2D maps with the appropriate transition tiles?

I know how to create top view maps with stand alone tiles. For example I can generate a procedural map with grass and trees. However I can not generate forests of different sizes and shapes. How do I know which forest sprite to put where? I'm trying to loop over the map tiles and accessing the surrounding tiles to pick which tile is the appropriate one. However wouldn't this approach lead to error in which forest tile is placed where? The computer would have to know the size of the forest and how the forest is shaped.

The problem seems too complex for me. Any ideas on how to break this problem down would be much appreciated or if you just want to talk about procedural generation I'm game for that too.

So far I've generated a forest but I'm having trouble making it look right. Here is what I have so far. https://76295db93db3812642fa5ba984c042fa81ffc37c.googledrive.com/host/0B6H3TRExU5M9eEkyd2FreHhiNlU/

Answer 1

The question appears to be about how to go about selecting the correct tiles after generating a map, so that is what I'll answer.

What you are talking about is called "autotiling" or "auto tiling" (depending on who you ask).

Here's a simple-ish method for handling that:

Given a single tile, we can find it's neighbors. Each tile then has a 4 bit state for the edges and a 4 bit state for the corners, giving us a total of 256 states per tile. Given the images provided, we can assume that we only need to care about the edge neighbors of each tile:

.#.
#X#
.#.

For the sake of sanity, we'll also assume that tiles either transition with only 1 other tile type (e.g. trees -> grass), or that tiles contain transparency and are layered on top of other tile types.

There will then need to be 16 different images for each tile, one for each neighbor state:

e.g.
0: ... 1: .#. 2: ... 3: .#. etc.
   .X.    .X.    .X#    .X#
   ...    ...    ...    ...

To determine which image is needed, you only need to iterate over the map once after generating to determine which tile to render. This shouldn't be to expensive to do at run-time, or you can pre-process the map if needed.

If you pre-process the map, you should probably make a separate map in which to store your actual renderable tiles instead of editing the existing map in-place. This will make it simpler to process and not introduce any errors that can come of changing the tile types while processing.

Update: Simple live example below:

var canvas = document.getElementById('canv');
var ctx = canvas.getContext('2d');

var map = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 1, 1, 1, 1, 1, 1, 0, 0,
  0, 1, 1, 0, 1, 1, 0, 0, 0, 0,
  0, 1, 1, 0, 1, 0, 0, 1, 1, 0,
  0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
  0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
  0, 1, 0, 0, 1, 1, 1, 1, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0
]
var tiles = new Image();
tiles.src = 'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKoAAAAKCAYAAAAkasVsAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsIAAA7CARUoSoAAAADxSURBVFhH7ZfBCcJQEESNZQhe9CJiJSrYjUXYjaBWIuJFL4JtKF/54ikzg5/sByfXTGZn398kbLO/Dx894loMboTqLZlf1q3aw3hDezF+SaN41pwPZSvdaz4Ill9UvkYZVBQyN1tKlw8F+bG6yHzMm5nyleqVqadqIvP11bDWm0AEAQ9qBHXXlAl4UGVkfiCCgAc1grprygSkZUp27/gBtIhELlPsVt0xsk85xI5dWBWd0qs0qKPtstX7utq97pfSJa/kifyyDsGOHNTz8QTPRemVYQILfgkmsymUe+uHiCz4dwLSF7V2WDV/Uf3r/216nslTmhyOBL3DAAAAAElFTkSuQmCC';

var mTemp = [];
for (var i = 0; i < map.length; i++)
  mTemp.push(0);

for (var y = 0; y < 10; y++) {
  for (var x = 0; x < 10; x++) {
    if (map[y * 10 + x] == 1) {
      var val = 0;
      if (y > 0 && map[(y - 1) * 10 + x] == 1)
        val |= 1;
      if (x < 9 && map[y * 10 + x + 1] == 1)
        val |= 2;
      if (y < 9 && map[(y + 1) * 10 + x] == 1)
        val |= 4;
      if (x > 0 && map[y * 10 + x - 1] == 1)
        val |= 8;

      mTemp[y * 10 + x] = val + 1;
    } else
      mTemp[y * 10 + x] = map[y * 10 + x];
  }
}

for (var y = 0; y < 10; y++) {
  for (var x = 0; x < 10; x++) {
    var tile = mTemp[y * 10 + x];
    ctx.drawImage(tiles, tile * 10, 0, 10, 10,
      x * 10, y * 10, 10, 10);
  }
}

<canvas id="canv" width="100" height="100"></canvas>

Answer 2

For random tile generation, using a cellular automata algorithm is a good approach.

http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

This is a good tutorial on the basic idea. Essentially you have some some random (or noise) function that generates initial tiles. Then the process gradually groups similar areas together, which can give you nice looking "random" shapes.

You could do this with more than just binary values to achieve more complex tiled worlds.

Answer 3

A common technique is to construct your maps from premade sections of n*n tiles which can fit together in different ways ("super-tiles" if you would like to call them that way). My favorite example for this is the good old X-COM: UFO Defense. They become very visible on the overview map, especially in the "farmland" biomes:

When you want your map to be easily navigable (player can move from any supertile to any adjacent supertile), you need to make sure that there is a section at both the north/south and the east/west border of every supertile which must not be blocked on any supertile so players can always move between them. X-com solved this on Farmland biomes by having every tile being completely open to the south and east, which allowed to place the exit to the north and west whereever they want.

When you want your maps to be more labyrinth-like (the player can only move between some adjacent supertiles), you need to create different supertiles for dead ends, straights, curves, t-junctions and crossing sections. At a bare minimum you need:

• 4 dead-ends (entered from south, west, north and east)
• 2 straights (horizontal and vertical)
• 4 curves
• 4 t-junctions
• 1 crossing

With just one of each of these 15 basic supertiles you can already create quite intereting maps using a standard maze generation algorithm. But when you want even more variety, you can create multiple alternative versions of each of these 15 basic tiles. As long as they all fulfill the contract of having the opening at the same place, they will be interchangeable. Here are some examples of north-east curves which all fulfill the same function and should be interchangeable without affecting the playability of the map:

### ###   ### ###   ### ###   ### ###   
### ###   #     #   ###  ##   ##  ###
###       #         ####      #   #  
#######   ##    #   #######   ###   #
#######   #######   #######   #######

To make these more interesting, super-tiles can also have randomized internal variations in form of features which only have a small chance to appear on each supertile as long as these do not interfere with how the supertile can be navigated. A room supertile in a dungeon, for example, could have a 50% chance each of having a chest in the upper-right corner, a bookshelf in the upper left, a weapon rack in the lower right and a table in the lower left. This already gives you 16 different supertiles for the price of one.