This is a proof of concept showing a 1024 x 1024 tiles map on Arduboy. That is over 1 million tiles and such map would take 1 MiB if stored in traditional array format – this program as a whole takes just 43% of program memory. It was inspired by a discussion with @city41.
Someone could take this idea further and create a tool and/or a framework for creating such maps.
This is a debug map of the world (there are a few villages and other things that are too small to be seen here):
sauce.pdf (31.5 KB) <— rename to sauce.zip and extract
This is not a tidy thing – I made it in two days and am releasing it AS IS for anyone who wants to make use of it on their own risk. The whole thing is CC0. I’m not even making a repo, I don’t want to maintain this.
I aimed for a stress test and overdid the map size on purpose. There is a noticeable tearing due to caching when transitioning between parts of the map. My experiments suggested that a more reasonably sized and complex map will either not need caching at all, or will have very fast caching with almost unnoticeable tearing.
I lay the basic ideas down here, you should figure out the rest from the source code. I tried to comment it and leave it open for modifications and extensions.
You can use this idea even for much smaller maps than that I made here, and with much less code.
What’s this about
AFAIK basically what Daggerfall did.
We usually store game maps as 2D arrays – that requires a huge amount of memory in the same way raster images do by storing every single pixel (tile).
If we continue to think of the map as an image, consider alternative formats such as vector representation or procedural generation graph.
In practice instead of storing an array of tiles
mapTiles[x][y] create a function
getMapTile(x,y) that for given position computes and returns the tile at that position. This way we compress the data by substituting them with an algorithm that generates the data.
The key ideas are:
vector representation – Exploit the fact the world is mostly made up of nice mathematical shapes. Create functions that represent these basic shapes and apply set operations (union, intersection, … – these correspond to logic operators) on these primitives to create more complex shapes such as coastlines, rivers and so on.
procedural generation – Fill the empty space between interesting places with procedural generation. Make use noise functions, fractals and so on. Do not use the
randfunction – the random numbers have to be the same for the same position.
neighbour rules – Have rules for things such as borders between tiles.
tile patterns (dictionary compression) – You can create common tile patterns such as trees or houses, which you can paste into the world as a whole.
This will allow us to have world whose tile size is limited only by the data type ranges. However, the complexity of the world is what consumes the memory, so we can’t create infinitely rich worlds.
A disadvantage of this approach is the computational complexity of retrieving each tile – that is understandable, we’re purposefully trading memory for computation. A huge and very complex world will require a lot of computation for every tile and will slow down the program.
Here we have to create a cache into which we precompute a small area around the player every time they significantly change position. This will however introduce loading times when moving across the map – these are very short, but cause a noticeable tearing with a rich world. However with reasonably simple maps cache either isn’t needed or almost isn’t noticeable.
You can create a large map even without any advanced tools.
Create a PC program that will render previews of the map – previewing on Arduboy or in emulator is slow. The preview can be as simple as a plain ASCII output in terminal – for smaller maps. For a bigger map output an image file where one tile equals one pixel. That file can be embedded in an HTML document that automatically refreshes itself every few seconds. Have that file open in a web browser on a second monitor and watch the map change in real time as you edit and compile the map code.
Things to improve and work on
Things that would bump this to another level:
- Better noise function(s), like a Perlin noise. My noise function here is extremely primitive and is basically a white noise. Perlin noise would allow smooth, natural shapes, which I awkwardly tried to mimic with circles.
- More shapes, mainly an ellipse. I only created a circle function but found that I’m missing the option to “stretch it”. The ideal ellipse would be the one that could also be rotated, not just aligned with the main axes. Also some kind of a smooth curve or a polygon would be great.