https://gamedev.stackexchange.com/a/199172/24266
I just spent a while writing some code for my 2D game to do this that should work correctly with negative coordinates. I informally checked it against Minecraft's F3 debug menu's chunk offsets, as well as wrote a few simple unit tests that I've provided below.
If anyone knows of a way to simplify or optimize this algorithm, do please comment and let me know!
// Copyright 2022 by Dan Bechard
// Your choice of any the following licenses:
// - Public domain
// - Unlicense license
// - MIT
#include <cstdint>
#include <cmath>
#define CLAMP(x, min, max) (MAX((min), MIN((x), (max))))
// Returns chunk index for a given world coord along a single axis
const int16_t Tilemap::CalcChunk(float world) const
{
float chunk = floorf(world / CHUNK_W / TILE_W);
return (int16_t)chunk;
}
// Returns a chunk-relative tile index for a given world coord along a single axis
//
// NOTE(dlb): The 0th tile in a chunk is always the "negative most" tile,
// not the tile closest to zero. In 2D, with +x right and +y down, the 0th
// tile along the x and y axes would be the left-most or top-most tile in a
// chunk, respectively.
//
const int16_t Tilemap::CalcChunkTile(float world) const
{
const float chunk = CalcChunk(world);
const float chunkStart = chunk * CHUNK_W * TILE_W;
const float chunkOffset = world - chunkStart;
const float tile = CLAMP(floorf(chunkOffset / TILE_W), 0, CHUNK_W - 1);
return (int16_t)tile;
}
// Returns the tile at a given world coordinate
const Tile *Tilemap::TileAtWorld(float x, float y) const
{
const int chunkX = CalcChunk(x);
const int chunkY = CalcChunk(y);
const int tileX = CalcChunkTile(x);
const int tileY = CalcChunkTile(y);
assert(tileX >= 0);
assert(tileY >= 0);
assert(tileX < CHUNK_W);
assert(tileY < CHUNK_W);
// NOTE(dlb): I'm using an std::unordered_map to look up chunks by
// their x,y offsets in the world. This allows negative chunk
// offsets. The hash map returns an index into an std::vector which
// acts as a pool of loaded chunks. This is particularly useful
// for "infinite" worlds where you may want to generate chunks on
// the fly, page chunks to disk on the server, or maintain an LRU
// cache of nearby chunks on the client.
//
// NOTE(dlb): Chunk::Hash(x, y) simply packs the two 16-bit ints
// into a single 32-bit int. You may want to choose a different hash.
//
auto iter = chunksIndex.find(Chunk::Hash(chunkX, chunkY));
if (iter != chunksIndex.end()) {
size_t chunkIdx = iter->second;
assert(chunkIdx < chunks.size());
const Chunk &chunk = chunks[chunkIdx];
size_t tileIdx = tileY * CHUNK_W + tileX;
assert(tileIdx < ARRAY_SIZE(chunk.tiles));
return &chunk.tiles[tileY * CHUNK_W + tileX];
}
return 0;
}
If you have 16x16 tiles and 16x16 chunks:
CalcChunk(1)
CalcChunkTile(1)
will return Chunk 0, Tile 0
CalcChunk(TILE_W)
CalcChunkTile(TILE_W)
will return Chunk 0, Tile 1
CalcChunk(CHUNK_W * TILE_W)
CalcChunkTile(CHUNK_W * TILE_W)
will return Chunk 1, Tile 0
Negative coordinates are similar, but tile 0 is the "leftmost" tile in a chunk. So:
CalcChunk(-1)
CalcChunkTile(-1)
i.e. Chunk -1, Tile 15
CalcChunk(-CHUNK_W * TILE_W)
CalcChunkTile(-CHUNK_W * TILE_W)
i.e. Chunk -1, Tile 0
Some tests:
#define CHUNK_W 16
#define TILE_W 16
assert(CalcChunk(0) == 0);
assert(CalcChunk(1) == 0);
assert(CalcChunk(CHUNK_W * TILE_W - 1) == 0);
assert(CalcChunk(CHUNK_W * TILE_W) == 1);
assert(CalcChunk(-1) == -1);
assert(CalcChunk(-(CHUNK_W * TILE_W - 1)) == -1);
assert(CalcChunk(-CHUNK_W * TILE_W) == -2);
assert(CalcChunkTile(0) == 0);
assert(CalcChunkTile(1) == 0);
assert(CalcChunkTile(TILE_W - 1) == 0);
assert(CalcChunkTile(TILE_W) == 1);
assert(CalcChunkTile(-1) == CHUNK_W - 1);
assert(CalcChunkTile(-(CHUNK_W * TILE_W - 1)) == 0);
assert(CalcChunkTile(-CHUNK_W * TILE_W) == CHUNK_W - 1);
P.S. I know assert
is C, not C++. Take the free code and leave me alone. :D