Large-Scale 2D worlds with a “world texture” to draw to causing memory issues

Background:

I've currently implemented a world class where the dimensions are provided in meters and those dimensions are translated to pixel values for an allegro (4.x) memory bitmap to be created so objects can be draw to it. This seemed like a good idea...until I learned the hard way that world dimensions translated to pixel dimensions such that the bitmap created would be upwards of 100,000,000 pixels causes um..."issues" and allegro (4.x) barfs.

Question:

How would I implement large-scale worlds such that they can be any arbitrary size and still have a bitmap/surface/texture to draw to that's small enough to fit into memory along with everything else? Please limit answers to allegro 4.x solutions.

The problem you're running into is that 100,000,000 is a big number for a 32-bit floating-point value.

There are two approaches to fixing this. First, consider whether you actually need such big unit. Do you really need a world 100,000,000 pixels across? Can you consider a system where 1px == 100m or something along those lines? Simply scaling down your units is a very easy and simple solution in many cases.

If that doesn't work, consdier breaking your world up into chunks. Each chunk can be a fixed-size square of some smaller and easily handled size, say 1000x1000 meters/pixels. You can identify a position by a combination of a chunk ID (really, the 2D integer coordinates of the chunk in the world chunk map) and a position vector inside the specific chunk. You can with a little thought efficiently figure out which chunks are visible (a maximum of four at a corner if the chunks are bigger than the screen; maybe more for wider monitors/resolutions).

Going the chunk route is a good idea even with smaller worlds for various reasons, but don't discount the idea of rescaling the world if you can.

This really has nothing to do with Allegro in any way.

• I'm already scaling the world, but the other way: 1 meter to 100 pixels. I've noticed that the scale calculation has its hands in everything anytime I want to draw something to the screen, create a camera (they need to know their dimensions and position in the world), draw to a camera, or put the mouse position in the world there is a call to a scale function: ToScreenScale(meter value) or ToWorldScale(pixel value). This seems way more tightly coupled than it needs to be. – Casey Sep 10 '13 at 13:18

As Sean points out, your issue is nothing to do with Allegro, this isn't an Allegro limitation. If your texture is 10000x10000, you're talking about something over 1GB in size (10000 x 10000 x 3 bytes per pixel). If it's really 100,000,000 across, then you're talking terabytes of memory. This just simply isn't feasible, not on Allegro, not on any library. You're talking fundamental hardware limitations. And the vast majority of that texture would be unused. Blank. A waste of memory. So my gut instinct is that you're coming at whatever problem you have from the wrong angle. However vast, sparse worlds are nothing new, and there's a wealth of research out there on how to do them well. The keyword to search for is probably terrain streaming / generation.

However, to answer your question as it is: forget about Allegro for the moment, and consider the two aspects you need to solve here: density, and sparseness. Well, three if you count accuracy, but just stay well away from floating point anything (use 64-bit integers for positions / distances) and you should be fine.

If you can see all the world at once, then you're seeing it on a screen let's say 1680 x 1050. So no matter how dense your actual world data is, each pixel on screen is going to be an average of a bunch of source pixels. Even when you zoom in, it'll still be several pixels, and you've going to have to zoom in quite far before each pixel in the world data is visible on screen. So you probably want to be thinking about precalculating and storing layers, like mip-maps, for each potential level of zoom. When you're zoomed right in, you can see the data as it was originally drawn. As you zoom out, at some point you stop showing the 1:1 layer, and instead show a layer where each pixel is the average of four pixels, then sixteen, then thirty-two.

Crucially, you're never looking at an area of more than 2048 x 2048 in size - and your graphics card / library should be able to handle that. Your top level texture, the most-zoomed out level, is 2048x2048 but your entire world can fit on it. As you zoom in one level, you need 4 2048x2048 textures, one for each quadrant. Depending on where you are looking in the image, you may be looking at just 1 of those 4 textures, or you might be looking at a border between 2 or 4 of them. As you zoom in one level more, you need 16 2048 x 2048 textures to display the whole world, but crucially, you can never see more than 4 of them at any one time (your screen simply isn't big enough). So you can pick and choose which 4 to be loaded based on where you are looking. This is the key to the whole thing - by breaking up your world into chunks and levels, you can selectively load parts of it.

This feeds into the sparseness aspect. At the most zoomed in level, your real data is just a matrix of 2048 x 2048 textures. Given a coordinate in your 2D world, you can map it to which texture contains the data for it by simply dividing the coordinates by 2048 (e.g. <5000, 2000> is in cell <2, 0>). If the content is being drawn onto the world data by users, most of it will start empty. And if it's empty, you can avoid having to store anything for it at all. When the users try to paint into a cell that hasn't been created yet, just make a new 2048x2048 texture for that cell, and let them paint into that.

Bear in mind the more zoomed-out levels can be generated automatically from the high detail, zoomed-in layer. Only the zoomed-in layer has real data in it. When you have to generate the zoomed out layers, you can simply assume that any chunks that didn't have anything painted in them remain at their default colour (white, or green, or transparent, whatever).

As users change values in the zoomed in cells, sections of the layers above them will have to change to reflect that. Change an entire cell at the fully zoomed in from white to black, and a quarter of the cell in the layer above would change, a sixteenth of the cell in the layer above that, and so on; once you get to the top level you'd probably barely notice the tiny shift in colour of one pixel. But you can imagine this to be the effect you'd get of painting the roof of your house black instead of white, you might see it from a helicopter, but you wouldn't be able to see it from space.

With additional experience I've learned that what I was trying to achieve was just stupid.

The real answer is to use off-screen textures and only draw the area and entities that are visible to the camera to that off-screen texture. The very last step is to draw that texture to the backbuffer. With that, your world can be as large as you want it and it'll never cause an issue.