6
\$\begingroup\$

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/

\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ There was also a very elegant method for handling both corner and edge transitions. I cannot find the site which I originally found it, and explanation kinda requires pictures...so I'll update this answer later with that algorithm if that is desired by anyone. \$\endgroup\$ – XNargaHuntress Sep 5 '14 at 12:32
  • \$\begingroup\$ So I may be going about it in the wrong way because even if I do get it looking right it will still look like strips of forests and unnatural. Correct me if I'm wrong but I believe what your saying is to generate the map and place the trees where they need to be. Then iterate over the map to clean up the graphics and place the appropriate tile? \$\endgroup\$ – zachdyer Sep 5 '14 at 17:14
  • \$\begingroup\$ Correct. When iterating, you either need a second array to store the "cleaned" up tiles, or you need to account for the different tile values for the same type in the iteration (if editing the array in-place). \$\endgroup\$ – XNargaHuntress Sep 5 '14 at 17:27
  • \$\begingroup\$ Added a simple live example to the answer \$\endgroup\$ – XNargaHuntress Sep 5 '14 at 17:55
  • \$\begingroup\$ This is kind of off the subject but I've never seen this before "|=". What is that? \$\endgroup\$ – zachdyer Sep 5 '14 at 20:54
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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:

XCom: Ufo Defense overview map

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.

\$\endgroup\$
  • \$\begingroup\$ I like the super tile concept that is cool. Its an amazing way to make interesting maps without hand crafting it all. \$\endgroup\$ – zachdyer Sep 5 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.