You're writing a 2D tiled map style game, but you want it to be large and you don't want to have to craft a huge map by hand; or perhaps you want a different map on each game.

Well, the solution is that you need a procedural map generator…

The trick with these is that you write a function to select a tile for any grid location, and the only parameters of the function must be the X and Y coordinates of the tile. The function has to act as if it is random but must not actually be random, because if you scroll off that part of the map and return to it later, you want the tile to be redrawn exactly as it was the first time you saw it.

If your map can consist of just a random array of tiles, that's really all you need to do, but most games need maps that have more structure to them or are in some way more interesting. So the trick I want to show you here is how to create maps where the tiles have some consistency with their immediate neighbors. For my example we'll create a map that has roadways all over it. In fact it willt look a bit like the board game Carcassonne…

First we note that each map square/tile has 4 points where a road can enter or exit. So the tiles available will look something like these:


Now, you can't just pick one of these tiles using our simple random tile-picker. Any tile you place has to join up with its 4 neighbors, so when you pick a tile you need to look at edges of the adjacent tiles. Well, using a similar lookup function to the simpler map above, you write a function that returns whether or not a road crosses the boundary and you call it 4 times, once for each side. Once you know how the roads enter the tile, you can select a tile whose appearance matches its topology.

Because you're making decisions based on the boundaries between tiles, when you select the tile for the next adjacent square, it too will be chosen based on that boundary, and so the roadway that exits the previous tile continues through the next one.

If there are any more decisions to be made in choosing the specific tile costume, for instance “when there are 4 roads entering a tile, do you want a crossroads or two corners?”, then to make those decisions you just add another function whose result is again dependent only on the X/Y coordinates of the tile.

That's really all there is to it. This will generate a map where every tile is defined and consistent with its immediate neighbors. An example using the above algorithm can be seen at https://scratch.mit.edu/projects/102145767/

However in the project at https://scratch.mit.edu/projects/102170546/ , I start with the same algorithm as above, but then I check the paths that are generated and I extract just one connected set of roadways, so that we have a finite map rather than an infinite one.

But this technique doesn't just work for road-style maps. It can work for terrain maps as well, where squares are perhaps woods, farmland, housing, lakes etc…

Again we make our decisions based on boundaries rather than just the main tile itself. This time, instead of just two choices for a boundary (ie ‘road present’ vs ‘no road’), we allow all the land types as boundaries… then we choose our tile based on the neighboring land types. For instance if there is grassland to the east and north and water to the west and south, we choose a tile that has a grass/water boundary running diagonally.

There are obviously more costumes needed for a system like this compared to just picking tiles at random, but the advantage is that the map doesn't look nearly as rectilinear as a simple tiled map and also you can take advantage of rotations to fill in many of the combinations. With a little bit of Scratch costume trickery, you can cut down the large number of combinations needed by using sprites that take advantage of transparency to overlay one type (eg grassland on two adjacent corners) on top of any other sprite that fills the tile (eg water).

As long as edges of the same type join up seamlessly, your map will look great and it won't be obvious that it was built from rectangular tiles.

Wow, this is a really informative post, thanks!
Would you consider turning it into a Scratch Wiki article where it can get the exposure it deserves?

TRocket wrote:

Wow, this is a really informative post, thanks!
Would you consider turning it into a Scratch Wiki article where it can get the exposure it deserves?

I'd be happy to but I don't think I have write access to the wiki…

G

gtoal wrote:

TRocket wrote:

Wow, this is a really informative post, thanks!
Would you consider turning it into a Scratch Wiki article where it can get the exposure it deserves?

I'd be happy to but I don't think I have write access to the wiki…

G

Here's how you request it: http://wiki.scratch.mit.edu/wiki/Scratch_Wiki:Become_a_contributor
the process took me less than a day and you strike me as more than qualified, I'm sure the wiki-dwellers will be ecstatic to have your input

NickyNouse wrote:

Here's how you request it: http://wiki.scratch.mit.edu/wiki/Scratch_Wiki:Become_a_contributor
the process took me less than a day and you strike me as more than qualified, I'm sure the wiki-dwellers will be ecstatic to have your input

Done! thanks for the pointer…

bro is smart