I am working on a project that requires a tile map that can expand continually in any given direction. It also requires that any given tile can be replaced with a new one. This is to allow rooms to overwrite one another (render-wise). Simply put: The player may have a number of doors that need to open into the same visual space on screen, but have entirely differently layouts, sizes, and contents.

It needs to expand *to within reason*. I don't expect a player to walk 2 million tiles to the left in order to reach the lower limits of an integer. If they do, they are playing wrong and wasting a lot of their own time.

My gut is telling me to simply use `std::map<int64, Tile>` the int64 representing both x and y. Then separately keep track of the current visual space so I can look up the tiles I need to draw. I have a voice in the back of my head telling me this is dumb however. Instead perhaps I should make a vector of vectors that represents a screen's worth of tiles.

So I am asking here. If you needed a tile map that can expand its current size, replace current tiles, and efficiently iterate through what it needs to draw how would you go about storing your tiles? Additionally, would you use that container for rendering or would maintaining a secondary container be beneficial for those purposes.

If you are only going to be changing rooms when a player is in adjacent rooms, an (x,y) index may not be necessary, but something more of a "neighboring rooms" list for each room. Again, if you are only going to change rooms when their is a possibility(player adjacent to room) that the player might go through the door, a neighbor list would work. An (x,y) index could still be kept track of for lower level functionality and for completness sake.

Edit: Agree

[qoute]

including the viewport area and about half as much again in all directions

[/qoute]

My gut is telling me to simply use `std::map<int64, Tile>` the int64 representing both x and y.

By default, prefer std::unordered_map over std::map, unless you need your elements to remain ordered within the container. Otherwise, you're using a slower container for no reason.

That said, std::unordered_map and std::map are both the wrong containers to use here. Maps are optimized for lookups, but you primarily need iteration speed: you render your tiles by doing for(). That'd slow way down under maps.

Instead perhaps I should make a vector of vectors that represents a screen's worth of tiles.

vectors of vectors are not two-dimensional arrays. vectors of vectors are arrays of arrays.

A two-dimensional array can be visualized like a square or a rectangle. An array of an array looks like many separate unequally lengthed lines that you'll spend too much coding-labor trying to keep in sync with one another.

If you need a 2D array, use a 1D vector, and just size it to (width * height).
When you need to do lookups by index, do: ((y * width) + x)
You can wrap it in a constexpr convenience function if desired:

constexpr size_t Index2D(size_t x, size_t y, size_t width) { return (y * width) + x); }

If you needed a tile map that can expand its current size, replace current tiles, and efficiently iterate through what it needs to draw how would you go about storing your tiles?

In 2D chunks of tiles.

If each chunk is 20x20 tiles (in a 2D array stored in a single std::vector or std::array), and you have a 2D array of pointers (std::unique_ptr) to those chunks, you can add/remove more chunks by just shuffling around the pointers, or just make the world be a fixed large number of chunks, and optimize away the blank chunks by making them be null pointers.

You also unload the chunks that are outside of view, and load new chunks when they come into view.

I currently use 20x20 for my chunks, but I might make mine larger. It'd depend on your tilesize to some degree also, my tile sizes are a tad larger than normal, so my chunks are smaller. One game I'm familiar with intentionally used 21x21 to make the maps oddly-sized for aesthetic purposes.

I currently custom container for the chunks, that allows me to append new columns or rows of chunks on either side, though I'm *this close* to deciding to just using a large fixed number of chunks (i.e. 1000x1000) because it makes things simpler. The chunks themselves are just a single std::vector sized to (Width*Height).

For extra fun, once you pick your upwards bound, you could make your entire world invisible wrap-around if players eventually reach the end.

Suppose you are using 32x32 pixel tiles. And 30x30 tiles a chunk. And 1000x1000 chunks per world. If the player walks 5 tiles a second, that means it'd take him slightly over an hour of holding the movement key down in a solid direction to walk from one end of the world to the other. And that's ignoring obstacles (trees, mountains, rivers, etc...) and enemies. Not large enough? 32x32 pixels per tile * 50x50 tiles per chunk * 2000x2000 chunks = 3.7 hours to walk across, ignoring obstacles (which could easily double the time).

As an added bonus, you can still store entity positions in 32 bit integers.

You could make your world contain even more chunks (up to 4 million chunks wide, assuming 32x32 pixels per tile and 30x30 tiles per chunk) and still use 32 bit integers, but you'll run into a few additional complications you'd have to code around. Not too difficult though.

My gut is telling me to simply use `std::map<int64, Tile>` the int64 representing both x and y.

By default, prefer std::unordered_map over std::map, unless you need your elements to remain ordered within the container. Otherwise, you're using a slower container for no reason.

That said, std::unordered_map and std::map are both the wrong containers to use here. Maps are optimized for lookups, but you primarily need iteration speed: you render your tiles by doing for(). That'd slow way down under maps.

If you needed a tile map that can expand its current size, replace current tiles, and efficiently iterate through what it needs to draw how would you go about storing your tiles?

In 2D chunks of tiles.

If each chunk is 20x20 tiles (in a 2D array stored in a single std::vector or std::array), and you have a 2D array of pointers (std::unique_ptr) to those chunks, you can add/remove more chunks by just shuffling around the pointers, or just make the world be a fixed large number of chunks, and optimize away the blank chunks by making them be null pointers.

I don't have a routine for rendering yet, so it could be done using two containers or perhaps while avoiding a for loop. What I am trying to say is that the render routine can be designed as efficiently as possible after committing to how I store the tile map as a whole. I could have a container for the tile map in its entirety, and yet another for what will be rendered which then could in turn be updated as efficiently as possible.

Moving onto the second part regarding how you would go about this using chunks of (tiles wide x tiles high). I guess there is one more specification I didn't consider. Everything is sized differently. Even rooms that would share the same visual space can be different sizes. When you leave Room A and enter Room B only half of Room A might be replaced.

So how would you design chunks around that little caveat?

One option would be to separate the notion of chunks vs room.

..parts of a chunk might belong to no rooms.

Figure out exactly what a "room" is and what a "room" requires. Then I think it will make it more clear how to separate the "room" concept from the "these are the tiles at this location" concept.

I have already been working under the premise of the chunks and rooms being entirely separate. Well, more accurately I've been working with premise that the tile map is separate from the world data.

If I go with chunks in the tile map, I'll probably go with the design requirement that parts of the chunk may be empty.

In the meanwhile, unless I see a post that really stands out as the obvious answer, I will do the last part that you said. Figure out exactly what a room is and what it requires. Hopefully from that vantage point it will be clear how to design the tile map.

As it stands now my world data has no concept of what it looks like, only what it is; I currently have one class for the data and one class for how to interpret the data so it can be rendered (the tile map is separate from both of these). Maybe the data needs to be redesigned to create an optimal solution though.

your low-order bits of your tile coordinates will specify a tile within the chunk.

To organize chunks you can use the high-order bits to index into an unordered set as you original proposed. If lookup performance becomes problematic, you can keep a smaller unordered set as a cache of recently-used chunks (using least-recently-used, and say 2-4 times as many chunks as will ever/typically be onscreen).

I don't understand.

How would the low-order bits of the tile coordinates specify a tile within the chunk?

>Why wouldn't I translate the current tile map coordinates to the local space of the chunk that begins at the current tile map coordinates?

Why would I organize the chunks according to the high-order bits?

>Shouldn't I organize the chunks according to their start or end positions on the tile map?

I was under the impression that I'd have something like the following with chunks.

class TileMap

{

container<chunks>

..other members

void AddChunk(x_start, y_start, chunk);

void ReplaceChunk(x_start, y_start, chunk);

void Draw(ViewPort drawRegion);

}

I don't have a routine for rendering yet, so it could be done using two containers or perhaps while avoiding a for loop. What I am trying to say is that the render routine can be designed as efficiently as possible after committing to how I store the tile map as a whole.

Not quite. The way your store your data directly affects how quickly you can access that data. Storing an fire extinguisher inside a locked closet makes it less accessible during an emergency than mounting it on a wall. You can optimize your "fire emergency procedures" as fast as you like, but until you change where it is stored, your "best time" will be determined purely by the closet and the lock.

Since your data storage determines the minimum access time, designing your routines "as efficiently as possible" *after* "committing" to a slow data storage, means you can only optimize up to your data's already slow layout.

I could have a container for the tile map in its entirety, and yet another for what will be rendered which then could in turn be updated as efficiently as possible.

If you think about this sentence you just said, there's an important insight here.

To highly paraphrase your sentence, you just said: "I could store more data, and do more work, and optimize that extra work as efficiently as possible"

You know what the most "as efficiently as possible" solution is for doing more unnecessary work? Not doing the unnecessary work at all.

Doing nothing is always faster than doing something, so if that 'something' isn't necessary, it's faster to not need to do it in the first place.

This is not premature optimization. This is knowing your needs in advance, and designing your architecture for that. Your needs, which you'll find out eventually, is iteration speed and access speed. std::vectors trump std::maps in both of those areas. What maps win at are searches; and even then, they only win at searches when you got large amounts of data.

Moving onto the second part regarding how you would go about this using chunks of (tiles wide x tiles high). I guess there is one more specification I didn't consider. Everything is sized differently. Even rooms that would share the same visual space can be different sizes. When you leave Room A and enter Room B only half of Room A might be replaced.

So how would you design chunks around that little caveat?

You don't need to.

If your world is a seamlessly scrolling world, your areas don't need to line up to chunks. A room might horizontally use 2 and 7/9ths of a chunk - it doesn't matter; chunks don't know about rooms, rooms don't know about chunks. "Chunks" are just collections of tiles. "Rooms" are just pictures draw using those tiles.

This scene (WIP pic from my game from ~2010), shows two things that could be described as "rooms" (depending on how you want to count the hallways). It's split across more than one chunk. Chunks don't affect gameplay, they just silently existing for streaming data in and out as the player moves around.

I don't remember exactly where the chunks fell - the chunks are supposed to be invisible grouping of tiles, not observable by the player, or even the person designing the maps (though they can see it if they want, it shouldn't affect the map design). It's a behind the scenes optimization to make everything work smoothly and seamlessly.

The chunk divisions could've easily fallen like this, without any difference to the gameplay or visuals:

Here's another shot (from a few days ago), showing how even objects can straddle the chunks. The chunk boundaries are seamless and invisible to entities within the world.

(the chunk lines in this screenshot aren't guesses: the editor is drawing them)

I don't know your gameplay needs, so maybe you have some special gameplay related to the concept of rooms (as opposed to mere visuals and collisions)? If so, chunks still don't need to know about rooms, nor rooms about chunks. Just use rectangles (or collections of rectangles) to define the areas of your rooms on top of, over, and without knowledge of, the chunks.