5
\$\begingroup\$

I am working on a video game. Everything (terrain, entities, particles) is stored in 100 by 100 chunks. Here is the array structure for the chunks:

public static final int chunkSize = 100;
public static Chunk [][][] chunks;

The world is 20,000 by 20,000.

Given a random coordinate (such as (-1244, 1353)), how can I quickly and efficiently determine what chunk the coordinate is in?

Once I know what chunk a coordinate is in, I can determine which chunks to load around a player.

\$\endgroup\$
6
  • \$\begingroup\$ Close to duplicate, at least covers the same information: gamedev.stackexchange.com/questions/65800/… \$\endgroup\$
    – House
    Commented Feb 13, 2015 at 19:15
  • 3
    \$\begingroup\$ Just divide the coordinate by 100? That solution seems so blatantly obvious to me that I am pretty sure that I must be missing something in your question. \$\endgroup\$
    – Philipp
    Commented Feb 13, 2015 at 19:45
  • \$\begingroup\$ To avoid a lot of headaches make your chunk size a power of two. For example 128 instead of 100. It will help a lot regarding rounding errors and you can then safely get rid of expensive divisions by using multiplications by the inverse instead (about 20x faster on current FPUs, 2015). It might not be critical for your project but it's a good habit. \$\endgroup\$ Commented Feb 14, 2015 at 1:33
  • \$\begingroup\$ @StephaneHockenhull This is true. At the moment, the game is still in early development stages. Before it is released, chunk size and world sizes will be in more binary friendly formats. \$\endgroup\$
    – Progo
    Commented Feb 14, 2015 at 3:47
  • \$\begingroup\$ @Byte56 As always, I google my issue before asking on StackExchange. Before asking, I hadn't seen anything helpful on Game Dev or StackOverflow. \$\endgroup\$
    – Progo
    Commented Feb 14, 2015 at 3:49

3 Answers 3

4
\$\begingroup\$

If a chunk is C world units along an axis, you can convert a world unit W along that axis to a chunk index along that axis by floor(W/C) (or simply rely on integer division to drop the fractional part of the result).

Now, you have to be careful since you can't actually have "negative" indices into the chunk array, which is what you'd get if you have a negative world coordinate.

Thus, you will first want to offset your coordinate system so that there aren't any negative values. If your lowest value on your world axis is -10,000 for example, adding 10,000 to the input will appropriately translate the coordinate system. In general if your world is WorldWidth wide, evenly distributed around the origin, then you'd add 0.5 * WorldWidth.

Overall you'd end up with something like this to get a chunk from a world position:

Chunk GetChunkForWorldPosition(Vector3 position) {
  float offset = WorldWidth * 0.5;
  int x = (int)Math.Floor((position.x + offset) / ChunkSizeX);
  int y = (int)Math.Floor((position.y + offset) / ChunkSizeY);
  int z = (int)Math.Floor((position.z + offset) / ChunkSizeZ);

  return chunks[x][y][z];
}
\$\endgroup\$
4
  • \$\begingroup\$ You can also use the modulo operator (%) with a 0-based indexing to make sure you're always inside the coordinate system no matter what value you get passed by calculating x = x % WorldWidth. Advantage is that with a WorldWidth=10000, a value of -500000 would still be acceptable (and translate to the origin, with many wrap-arounds). \$\endgroup\$
    – Mephy
    Commented Feb 14, 2015 at 4:40
  • 1
    \$\begingroup\$ @Mephy: The modulo operator produces negative outputs, e.g., (-125) % 100 = -25, not 75 like you want. This is one of the reasons why powers of two are nice: because the x & 0x7f is always positive or zero. \$\endgroup\$ Commented Feb 14, 2015 at 6:10
  • \$\begingroup\$ @DietrichEpp My bad, I was thinking about Python, where (-125) % 100 = 75. stackoverflow.com/questions/3883004/… \$\endgroup\$
    – Mephy
    Commented Feb 14, 2015 at 14:08
  • \$\begingroup\$ Just out of curiosity, do you find an advantage to float over double? \$\endgroup\$
    – Progo
    Commented Feb 14, 2015 at 15:32
1
\$\begingroup\$

You can use this simple calculation:

int chunkX = playerX / chunkSize + coordinateOriginX;

Where:

playerX is the X-coordinate of the player.
chunkSize is the size of the chunk.
coordinateOriginX is the in-world horizontal origin of the coordinate system.

The same can also be used for the Y-index, but you just have to replace the playerX value with the Y-coordinate of the player, and the worldOriginX with the vertical coordinate origin.

You can then create a method which finds the chunk at a specified coordinate based on the above calculation, pretending that you have a class to hold the chunk data (In this example called Level. Also, note that I use a two-dimensional array here, because I can't really understand the purpose of a three-dimensional array when using two-dimensional coordinates):

public class Level {

    // The array of chunks
    private Chunk[][] chunks;
    // The chunk size, as you mentioned
    private int chunkSize = 100;

    // The world width
    private int worldWidth = 20000;
    // The world height
    private int worldHeight = 20000;

    // The in-world horizontal coordinate origin (the 0, 0 point)
    private int coordinateOriginX = 10000;
    // The in-world vertical coordinate origin (the 0, 0 point)
    private int coordinateOriginY = 10000;

    public Level() {
        // Create the chunk array
        chunks = new Chunk[(int)(worldWidth / chunkSize)][(int)(worldHeight / chunkSize)];
        // TODO POPULATE THE CHUNK ARRAY
    }

    public Chunk getChunkAt(int x, int y) {
        // If the horizontal coordinate is valid and in the world
        if(x >= coordinateOriginX - worldWidth && x <= worldWidth - coordinateOrigin) {
            // If the vertical coordinate is valid and in the world
            if(y >= coordinateOriginY - worldHeight && y <= worldHeight - coordinateOrigin) {
                // Determine the indexes to the chunk
                int xIndex = (int)(x / chunkSize) + coordinateOriginX;
                int yIndex = (int)(y / chunkSize) + coordinateOriginY;

                // Return the chunk at the indexes
                return chunks[x][y];
            }
        }
    }
}

This is a very easy-to-use system for getting the chunk at a specific coordinate. It is also very flexible, and easy to extend.

There is one thing I don't understand though, why do you use a three-dimensional array for the chunk array, when you just use a two-dimensional coordinate system for the coordinates?
Just tell me if/what purpose this is for, and I'll update my answer to work with it.

Good luck!

\$\endgroup\$
2
  • \$\begingroup\$ Also note that this does not work with negative coordinates, as it rounds towards 0. \$\endgroup\$ Commented Feb 14, 2015 at 5:38
  • \$\begingroup\$ @immibis That's why I included the "coordinate origin". Then, if you set the horizontal origin to 10000, as in the example, you can give an input of -10000, and it will turn out as index 0. The OP specified the world width, 20000 by 20000, so just include a simple if-statement to check if the values are valid. I'll update my example. \$\endgroup\$ Commented Feb 14, 2015 at 6:27
1
\$\begingroup\$

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)) == -1);
assert(CalcChunk(-(CHUNK_W * TILE_W + 1)) == -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)) == 0);
assert(CalcChunkTile(-(CHUNK_W * TILE_W + 1)) == CHUNK_W - 1);

P.S. I know assert is C, not C++. Take the free code and leave me alone. :D

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .