Big open world map


(Miloslav Číž) #1

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.

out

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

Please note:

  • 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 rand function – 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.

The workflow

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.

(Kevin) #2

Interesting! This is incredible, how does this compare in tile size to the Arduventure map?

Are the elements like trees and bushes and other sprite tiles within a given vector area always show up in the same spot? Like, if a user walks back over the same area does the computational algorithm use random numbers to put those there or is it based against a seed I’m assuming?

This is cool because the 32u4 has pretty significant processing power relative to the internal flash memory it has.


(Matt) #3

This is really cool. It’d be nice to figure out where this approach wins and when it doesn’t. I’d guess it’s similar to vector vs raster graphics. Really busy or really small dimensions, usually raster is smaller, and vice versa.

There is probably a balance in there where you could have a nice size map, define like 6 towns or so, and have room for a dozen enemy types or so for a nice sized rpg.

Nice work @drummyfish!


(Miloslav Číž) #4

Yes, the map is always the same. It does use pseudorandom numbers, but the point is this is a form of 2D noise, so for a given tile position (and given seed) the generated random number is always the same. I’ll edit this in the orginal post as it’s important: do not use the rand function – you can reuse a function that I made in the code, or create your own.

My noise function is super primitive. Perlin noise would make this so much better and easier.

I don’t know exactly how big Arduventure is, but I think pretty large too. When I played it it look like it was just made of chunk patterns which felt a bit repetitive, like walking through a set of rooms that looked the same.

EDIT: I’ve found some info that Arduventure is even something like 3k x 3k? That is amazing but anyway as I say, it didn’t feel very open world to me – more like a maze of similar rooms. And the memory was completely full. The approach I am presenting here can create arbitrarily sized maps in terms of tiles, taking much less space, and make them truly “open”.

As I see it the reason raster graphics is generally so prevalent is in the creation process, and the fact that personal computers have huge amounts of memory. Cameras, screenshots and physical measurements, these all yield raster graphics, so IRL that is our default. In order to obtain vector graphics we have to convert it, usually manually. In the end vector graphics is more superior than what it seems, it’s just hard to obtain.

BUT when we’re creating the map, we can start creating it right as a vector, not as bitmap as many people think. It’s just a matter of someone creating a nice tool.

I think raster representation still wins in these situations:

  • Really tiny images (like 10 x 10) where the initial overhead of vector still kill it. This is the case with sprites.
  • Images that correspond to high entropy data that can’t really be compressed and have to be recorded the way they are. That is for scientists really and we won’t ever meet these in Arduboy games.
  • Cases where you simply have enough memory and prefer straightforward representation and fast computation. That is the case with non-embedded computers, but Arduboy is the exact opposite here.

So I do believe in vector format for Arduboy.


I have been also thinking about vector format images for Arduboy – something like a tool that would convert an SVG image to a more compact representation that could be rendered on Arduboy, with possible transformation (rotation, scale, …) which are impossible with current sprites. If anyone wants to give this a go, feel free :slight_smile:


(Pharap) #5

I know someone who did something like this, but never published it.
It was going to be for a game that went unfinished.


(Miloslav Číž) #6

Too bad they didn’t release it :confused: I would like to see some “vector” games in the style of web flash games. Most games on Arduboy are tile/array/grid-based – that’s good, but would also be good to see different games as well.


(goes by "spacebruce" elsewhere) #7

Neat, I’m working half-heartedly on an open world game at the moment and have been exploring ways of getting a big-ish map into the size restraints. I’ll have a play with this and see if I can iron out slow framerate issues.

-Pharap
It wasn’t really a vector image format, just a big progmem blob of line definitions that was fed recursively into drawLine. Recreating it would literally take minutes of coding + art time.

Image and video of that thing

https://pbs.twimg.com/media/CoOCSXOXYAUsaCY.jpg
https://twitter.com/spacebruce/status/757559955327254528


(Pharap) #8

Technically speaking that still constitutes a vector image format, just a very crude one.
(Much like how Arduboy’s sprite format is a very crude 1bpp sort of affair.)


(Kevin) #9

Yeah interesting. Arduventure was huge but it was extremely tile based. I think it was two layers of meta tiles double RLE encoded if I remember correctly. So the “maze like” feeling would come from this. I really like this approach you’ve got here because making maps is super fast. For arduventure obviously everything has to be hand coded and ensure your tiles are doing what you want.


#10

How well does this handle empty maps (just ground tiles, no trees/rocks/buildings) at 4096x4096? Right now on an empty map of that size I use 34% memory and get no framerate issues, however I have yet to actually try it on my arduboy (I tried to recreate the same “world viewer” program you showed so that i can get a fair measurement)

(your tiles look so much better than mine :o)
Yours is most likely better than that though, since I store tiles in a “compressed” array which will get bigger the more detailed I make the map.


#11

As is Minecraft.
It had a terrain generation thing, and stores the chunks (16x16 blocks) that you had seen at least once (to speed up graphics and store map data this way).
It is infinite, because of terrain generation algorithm.
The other thing you will notice is that you can’t use command to place a block outside your view range … and stuff.

Great job.

Next step was to have structure generations …
such as villages, dungeons, caves …

We can have houses, at least.
… which started to make it more or less similar to Arduventure’s …


(Miloslav Číž) #12

Thanks for pointing this out – this approach is a bit like Minecraft, but not completely, because Minecraft creates kind of “completely random maps”, whereas here you have control of where exactly to put things like rivers, roads, mountains, houses, … The Minecraft-like algorithms are used in places where you don’t care very much, i.e. in between these points of interests. I would rather compare this to games like Daggerfall – it had a map so huge you couldn’t possibly travel by foot between the cities, thanks to procedural generation, but the cities were hand-creafted (at least AFAIK).