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?

Basically yes -- but by selecting chunk size as a power-of-two, you can do that translation simply by using the low-order bits. Say you have 16x16 tile chunks, then the lowest 4 bits of whole-world tile coordinates select the right tile in the chunk. In essence, the low-order bits are the chunk-local coordinate system.

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?

Its like your original idea of forming a unique key into the set out of the x/y coordinates of the tile, only now I propose that you have a unique_set of chunks, rather than tiles. Following on from the previous question, since the low-order bits form the chunk-local coordinate system, its the high-order bits that are left to form the whole-world coordinate system, the whole-world contains chunks rather than tiles.

I think I am starting to understand. To help speed that understanding along:

1) Would placing chunks in the world in a bizarre way screw up this functionality?

- Let's say I decided to place the first chunk's (0,0) at (1,1) in the world. Would that throw off the ability to use the low-order bits as local coordinates?

2) What if I chose to use 4096x4096 as my chunk resolution? Presumably I would then need to use the lower 12 bits? Thus leaving 20 bits left over to use as the world coordinates?

3) Why couldn't I use whatever bits I want for the world coordinate system? Is it merely to provide symmetry of design, or is there something that would break?

- (As far as I can understand the chunk's would know nothing of the world. Whereas the world would have a top down perspective, and be able to differentiate quite easily what coordinate system to prepare for assuming the translation wouldn't be performed inside the chunks themselves)

As a side note, I hope I am not performing a faux-pas by continuing to post to this topic. Like beating a dead horse or something. If it is, I am just trying to understand the anatomy of the horse, I apologize! Please don't lynch me

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.

Firstly thanks for your help, I've been able to understand this concept a lot better with your posts. There are however situations and algorithms that require "unnecessary work" so that they can function more efficiently. I've been able to make A* work faster by doing just that, doing unnecessary work. The algorithm functions just fine without the additions however, thus making it unnecessary. The point stands for anything, so I can't accept your statement as true. I do understand the point however and agree with you, and I think this situation is one where no gains will be gotten from such work.

Certainly. It's well known you can often trade time for speed, for example. I don't consider optimizations to get something to run at the required speeds to be unnecessary work.

I consider what benefits you're gaining from a second container to be unnecessary.

If I'm understanding you correctly, you're saying a map (which is optimized for searching, and bad at iteration and direct indexing) is a better choice than an array (which is optimized for iteration and indexing, but bad at searching) in a situation where you aren't going to be doing much searching, but will be doing heavy iteration and heavy indexing.

Your solution to that is to use two containers: One for storing the tile map for gameplay logic, and one for storing the tile map for rendering logic. Using two containers is sometimes don to great effects. But in this situation, it is unnecessary work because, unless I'm really misunderstanding what you are saying, both your gameplay logic and rendering logic benefit from arrays and suffer from maps, so two containers aren't needed. Modifying the terrain and expanding the terrain both are better suited to arrays. But you know your own code better than I do; maybe there's some key gameplay necessity that I'm just not catching? Perhaps involving the 'rooms' you mentioned?

Going back to your very first post, you said:

`std::map<int64, Tile>` the int64 representing both x and y.

That's likely slower than:

std::vector<Tile> tiles(Width * Height);
tiles[(y * width) + x] = '...'

And for re-sizing, as long as you're wiling to grow in chunks at a time, you basically have an array of chunks (or a map of chunks), and index into it in the same way:

struct Chunk
{
    std::vector<Tile> tilesInChunk(ChunkWidthInTiles * ChunkHeightInTiles); //Psuedo-code
};

std::vector<Chunk*> chunksInWorld(WorldWidthInChunks * WorldHeightInChunks); //Resize and reshuffle this as desired, just shuffling around pointers to the chunks.

Tile &GetTileInWorld(unsigned tileX, unsigned tileY)
{
    //As Ravyne mentoned, if the chunk sizes are powers-of-twos, you can avoid the divides and mods.
    unsigned chunkX = (tileX / ChunkWidthInTiles);
    unsigned tileX  = (tileX % ChunkWidthInTiles);
    unsigned chunkY = (tileY / ChunkHeightInTiles);
    unsigned tileY  = (tileX % ChunkWidthInTiles);

    Chunk *chunk = chunksInWorld[(chunkY * WorldWidthInChunks) + x]
    return chunk->tilesInChunk[(tileY * ChunkWidthInTiles ) + x];
}
// ^^^^ Illustrating the concept, but ignoring fine details of optimizations and bounds-checking.

But you don't want your tile container itself to be a map (unless I'm really missing something here).

As a side note, I hope I am not performing a faux-pas by continuing to post to this topic. Like beating a dead horse or something. If it is, I am just trying to understand the anatomy of the horse, I apologize! Please don't lynch me

Not at all. Either you're learning from our insights, or we're learning from your insights, or (ideally) both. It's a faux-pas to revive the horse months after it died (unless you start a new thread), but as it stands, this horse is scarcely bruised and can tolerate much more abuse.

>>> No horses were harmed in the making of this thread <<<

I wasn't really talking about two containers for gameplay logic and rendering logic, sorta because those need to be there. The two containers I was originally talking about would have been: history, and current. The history could have been hashed and the current could have been a vector. The idea was that I'd rather add data to a map than a vector, so the vector could have been a simple array even. I was originally talking about working with the tiles directly though.

Now, with the chunks I still need to replace data in the tilemap so a container optimized for searching is still ideal for part of the work. The pseudo-code below can probably tell you more than I can with words, or at least faster.

The relationship between the world and the tile map is not detailed in the code. The relation is that World uses TileMap, it gives it the data to render.

class Terrain //Visual Space
{
unsigned short width;
unsigned short height;
std::vector<unsigned short> m_TileValues;
};
 
class TileChunk //Visual Space that actually gets rendered
{
enum { width = 32, height = 32 };
enum { size = width * height };
Tile m_Region[size] = {0};
};
 
class World
{
PhysicalSpace* m_World;
std::map<Room*, Terrain*> m_TerrainStorage; //Terrain is created as m_World is explored
void Move( direction d );
};
 
class TileMap
{
std::vector<TileChunk*> m_RenderList;
std::map<coord_key, TileChunk*> m_Explored;
void Scroll( direction d );
};