The idea is to make a huge world where you can wander (e.g. top down, Zelda gb like). Normally, that would mean a huge memory reserved for the tilemap. But if the map could be generated so that it is the same in each play session, but do not require excessive memory.
1 Like
Well, Iām sure there are as many answers as there are programmersā¦ But for fun, Iāll bite.
For my part, I would divide the world into regions. The set of āactiveā regions would be a 3x3 area, with the central region being the current one explored by the player. As they move to the boundary edges, it would push and pop regions out-of/into the active region. I would index the regions by dividing their upper left corner by the region size and subsequently flooring. I would then use the indices as the seed for a PRN generator to load the region using whatever more granular algorithm populates this hypothetical game.
Is that an answer to the question being posed? Or were you more interested in my hand-wavey, mystical, āgranularā algorithm? i.e., the more nitty gritty? If so, this is a fun place to read: Map Generation - Procedural Content Generation Wiki Iām sure RogueBasin has a ton of fun map generation references, too.
Edit: and hereās the RogueBasin link: Articles - RogueBasin Iād bet that a good many of these would be more complete in their descriptions.
5 Likes
Hmmm, some years back I tried a semi-procedural approach to a huge world on Arduboy. You could hand-sketch the big shapes like rivers and then let the small details be generated procedurally.
Basically my approach would be to create a function getTile of x and y (and maybe time) that would return a tile, computed procedurally ā using the traditional things like different frequency noises run through filters ā based on the hash of the coordinates (so that the same tile is always returned for the same coordinates). For inspiration Iād look at the popular minecraft-type games that e.g. have different biomes which each have their own generating algorithm. Then Iād create some kind of cache for playerās surrouding area as you wouldnāt want to keep calling the slow getTile function over and over during rendering etc. This cache would be updated as the player moves. The challenge would be to update the cache so that there would be a minimum of tearing or āloadingā times. Perhaps if the cache is updated ācontinuallyā by single tiles you can get rid of tearing caused by updating by big chunks.
4 Likes
You mean 3x3 tiles or something else?
Do you mean the tile bitmap pixels are computed procedurally?
Such regions are referred to āChunksā in Minecraft.
So basically, a chunk/region is a whole piece of your map, which, if youāre using a tilemap for rendering, would contains your tiles.
Using 3x3 (2x2 could do well but would load more often) regions around the players allows to render the ālocalā, āloadedā maps area, relevant to the camera - and interactions such as monsters or anything else
3 Likes
I mean that I would define a region as being composed of MxN tiles, so that my active portion of the world map is 9xMxN tiles.
So if I were using a 11x11 pixel tileset, and defined my regions as a 10x8 grouping of tiles (e.g., to fit on one Mode 13 screen), there would be 720 tiles in memory at any given time.
1 Like
Thanks, yes! Much better explanation that even included my underlying rationale 
Thatās not what I meant, is that what your question was about? I just assume that you can fit a tilemap into the program, but maybe you need a huge tilemap? Then Iād first consider compression before procedural generation, always uncompressing only the tiles that you currently need. You can perhaps reduce the size of a tilemap by only including ābaseā tiles and generating the transition tiles automatically (like sand-grass transition in all directions).
No, I meant the same as you. So you are computing the tile index procedurally. I suppose that is so that we do not get just random ānoiseā of different tiles but that the tiles are somehow related to the neighboring tilesā¦
Yes, a simple white noise will give you just completely chaotic output, but if you use some more sophisticated noises and combine them, you can get nice bigger scale natural-looking structures for rivers, forests, or even cities etc. Here are some noises I once experimented with:
The very basic one is Perlin Noise, that alone should get you pretty far. You can threshold that noise to decide which tile you should return. (A more complex noise can e.g. be achieved by modulating one noise with another, i.e. you take the value of one noise and that value tells you an offset at which you take a different noise relative to given position, basically you distort one noise with another. Also the noises can be generalized to 3d if you want to add time dimension.)
Of course you can further employ more sophisticated stuff in your algorithm, such as the ābiomesā I mentioned, you can e.g. use one of the noise textures to decide where a city vs nature is, and then apply a different algorithm for city and for nature, e.g. in a city youāll want to be generating square houses while in nature youāll be generating trees. As I say, the function can be relatively smart and slow because youāll be caching it anyway.
Letās say you can see 16x16 tiles on the screen and you only cache the visible tiles, then you have 256 tiles cached (using something like a āpaletteā this cache may be e.g. 4 bit so in the end it could take just 128 bytes of RAM). Now letās say every time you move the camera one tile in a specific direction youāll need to load a new line of tiles that come into view into the cache. In this case youāll need to call the generating function 16 times, which really is not very much, the function can take its time. This can further be done gradually during the scrolling animation (for the animation youād need to have cached also one line outside of the view in every direction, i.e. 4 * 16 more tiles in the cache).
5 Likes
If you want some source code to dig into, hereās a demo I made for Arduboy two years ago using a combination of a hash function, āturbulenceā and smoothing:
It uses what @drummyfish is talking about - deriving tile values from hash functions, with some extra processing to āsmoothā things out a bit and make it look a bit less ugly.
It shouldnāt be too hard to adapt it for the Pokitto.
Hereās the page from the forum topic that spurred its creation:
(Note: thereās quite a few topics on the Arduboy forum discussing procedural generation, so I think it would be well worth the time to have a dig through som old topics over there.)
You may also want to look into Wang Tiles:
http://www.cr31.co.uk/stagecast/wang/intro.html
Though I think youād have to do that in combination with chunking.
I did something related for my Punk Game Jam entry Flight of the Steam Rocket Glider. The airflow map in the game is procedurally generated horizontally infinite tilemap.
It uses TAS and a tilemap that is twice as wide as what can fit on the screen at once. New columns of tiles are drawn using the _getTile(col, row) function as the camera scrolls left or right. The tilemap holds two copies of the visible tiles in a way that the column left to the leftmost visible column is same as the rightmost visible column and vice versa. When camera reaches left or right edge it can jump back to the opposite edge with the duplicate tiles and continue scrolling.
To implement both horizontally and vertically scrolling tilemap with this technique, you would use a tilemap that is twice as wide and twice as high as the visible area, and 4 copies of the visible tiles.
Anyway, if you decide to use some perlin like noise, you might be interested in my fixed point implementation of simplex noise.
1 Like
I see. So you need to update only one column (and a duplicate of it) each time the screen is scrolled 16 pixels right (if the tile size is 16x16 pixels).
Hmmā¦what a single pixel represent in your image?
Is it a single pixel in the game screen?I suppose not as the dimensions to do not match the Arduboy screen. Or does this represent the hash function so that a single pixel in the image represents a tile in the game screen?
1 Like
A single pixel represents an integer value between some minimum value (almost certainly 0) and some maximum value (I expect itās 9), thus the integer value can be interpreted as a tile index or as something else entirely.
You could decide that values less than 4 are water, values between 4 and 8 are grass and values above 16 are snow. The core hash function provides noise, the transformation on top alters that noise to create structure, and then you are free to interpret that structure however best fits your intended use-case.
For example, I believe this is the same map with different values interpreted as particular colours rather than shades of grey:
In this case it looks like a water-filled canyon, perhaps with some forested areas and more barren mountaintops.
I find that interpreting values below a certain point as water tiles and values above a certain point as earth tiles is typically a good way to create islands or landmasses.
In the source code I gave as an example, the values are interpreted as tile indices between 0 and 9, and the tiles used in the drawing phase are (I think) simply arabic numerals. They could just as easily be water, grass, snow et cetera. The point is that the numeric functions are producing structure just from coordinates, a hash function and some additional numeric processing.
Thereās a single buffer, which only stores enough tiles for a full frame worth of tiles, and new tiles are written into the buffer as the player moves (the player moving simply causes the buffer to scroll).
This is just an example though, youād have to find an arrangement that worked well for your needs.
Note also that this example map is 256x256 because of the limitations of using a 16-bit input to the hash function: 256 * 256 = 65536, the limit of a 16-bit value. A single-dimensional hash function is used and itās treated like a 2D hash function just by designating 8 of the bits as the x value and 8 of the bits as the y value, so you end up with 256x256 tiles. (Which is an impressive map size for something that uses such a tiny 16x8 tile buffer.)
Using a 32-bit hash function comprised of two 16-bit coordinates could afford you a map of 65536x65536 by the same principle.
Thatās not quite āinfiniteā, but I doubt anyone truly needs āinfiniteā.
3 Likes
Makes sense, lower grounds get flooded. You can make high points snowy.
Hey, I just tried to write a simple fractal noise with integers only. Here it is, feel free to copy paste it and modify to your needs (CC0):
uint8_t randValues[32] =
{
0x0f,0xd6,0x42,0x38,0x23,0xf6,0xae,0x91,
0xf5,0x27,0x44,0x8f,0x17,0x1c,0x33,0x58,
0x4b,0x7f,0xb6,0xf6,0xe5,0x60,0x96,0xa5,
0x3f,0xec,0x9e,0x19,0x44,0xc2,0xcc,0x1e
};
uint8_t whiteNoise(uint16_t x, uint16_t y)
{
return randValues[(x ^ y) % 32] + x * y;
}
uint8_t noise(uint16_t x, uint16_t y, uint16_t freq)
{
uint16_t dx = x;
uint16_t dy = y;
x >>= freq; // get the block coords
y >>= freq;
dx -= x << freq; // get the coords withing the block
dy -= y << freq;
uint16_t tl = whiteNoise(x,y), // get random values in 4 corners of the block
tr = whiteNoise(x + 1,y),
bl = whiteNoise(x,y + 1),
br = whiteNoise(x + 1,y + 1);
uint16_t blockSize = 0x01 << freq; // block size in pixels
uint16_t t1 = (dx * 256) / blockSize; // interpoaltion parameters
uint16_t t2 = 255 - t1;
tl = (tl * t2 + tr * t1) / 256; // interpolate horizontally at the top
bl = (bl * t2 + br * t1) / 256; // same at the bottom
t1 = (dy * 256) / blockSize;
t2 = 255 - t1;
tl = (tl * t2 + bl * t1) / 256; // interpolate vertically
return tl;
}
uint8_t fractalNoise(uint16_t x, uint16_t y)
{
return
(noise(x + 310,y + 53,6) >> 1) + // 0 - 127
(noise(x,y + 10,5) >> 2) + // 0 - 63
(noise(x + 20,y + 1,4) >> 3) + // 0 - 31
(noise(x + 2,y + 100,3) >> 4) + // 0 - 15
(noise(x + 350,y + 50,2) >> 5) + // 0 - 7
(whiteNoise(x,y) % 13); // add up to 255
}
This noise adds up multiple frequencies of a noise to create a fractal like surface, which you can see in the nature (i.e. mountains have smaller hills on them with yet smaller bumps etc).
Not sure how fast it is, you can prolly remove the % 13 or some of the noise frequencies to make it faster.
4 Likes
I was experimenting with this a while back. I wanted to generate an Autoduel type tiled map. My idea was to use the Pitfall! method of generating a pseudo random number generator that could move forward and backward. For variety the map would be divided into counties that would have different tiles: Farm, Forest, City, Beach etc. I hadnāt planned on it being infinite, the idea would be that you could select an interesting segment and lay that out as the route between two cities. Since itās a low res game you donāt really need any blending, I just added a cross road at each county junction.
I uploaded it to github if it would help anyone. Itās just some PC winforms code I wrote to test out the concept. https://github.com/DWidel/AutoDuelTileTest/wiki
3 Likes
I must admit, I was genuinely surprised to find it implemented in VB rather than C#.
LOL, Yeah, not many of us left. But I did it that way for 40 hours a week for over 20 years, so I can write code really fast. C# is just not as fast for me yet.
2 Likes