# How to store ever-expanding maps with top-bottom, left-right hierarchy?

I'm writing a game that will largely take place on only a screen-worth of hexagons, but which will require map to expand in every direction. Also the way I want to display those hexagons requires that I have to be able to iterate over them in order from top to bottom, left to right.

I have already written coordinate system, which can represent coords as 2d (axial) or 3d (cube). The system regards (0, 0) as the center hex, so it means I need to store negative coords as well.

What I don't have is data structure that fufills my needs.

I'm thinking about writing a data structure myself, which will consist of 4 two-dimensional vectors (each for one quadrant of the map in regards to positive/negative) that would be able to get hexes in order I want, but this solution (using 4 vectors) seems unintuitive and long to write.

So is there a simpler, possibly already implemented, way?

• Do you need to iterate the entire world in this order, or just the part shown on-screen (eg. for depth ordering)? – DMGregory Aug 19 at 11:36
• And is that use case the only use case? – Vaillancourt Aug 19 at 11:46
• Only the part show on screen needs to be in order, but I imagine this isn't going to be a huge map, so I'd prefer it all to be aligned from the start. – Trotom Aug 19 at 19:25

There are several options. For example:

• An std::map which maps coordinate pairs to tiles
• An adjacency graph (each tile has pointers to its neighbors - pretty useful for pathfinding or other applications where you need to navigate from tile to tile)
• A two-dimensional tree (allows you to quickly obtain a rectangular area of your map - useful for rendering or obtaining the local surrounding of an entity)

But all these methods have a drawback: While they grow, they allocate memory for new tiles as they need. That means that your tile data will be spread wildly across your RAM. This is bad for CPU caching, which might result in bad performance. (not as bad, though as using growing std::vectors, which will from time to time copy the whole content to a different memory location when they grow)

When your game world is very large, then it might be useful to divide it into fixed-size chunks. Fixed size means that each chunk can be easily represented as a fixed length array, which is great for memory locality. The chunks can then be connected through one of the options above.

Another option could be to allocate tile data in bulk and then put that data into the data structures described above as needed.

Start with a 2d array of tile. If they are all displayed on screen, there should not be too many tiles.

Each of your tile hold lot of data? Split data by concern and create one 2d array per concern. For example with a sim city like game path finding array will hold data about terrain surface, electricity availability could be another array... It all depends on how your algorithm access the data. If you just need one kind of data for one process, then give it his own view. This will even allow for efficient multithreading.

You have a hell lot of data? Split in squares. Maybe octree could help.

Need to apply same function on each tile? Just process as a 1d array.

But clearly if your tiles are on screen you should not have more than thousand, then any data design will work.