# How do I efficiently deal with entities moving between chunks?

I am working on a game in which entities need to be stored in chunks.

This is the basic chunk format:

public static Entity [row][column][entities] chunkEntities;


However, some of my entities move. How do I handle an entity switching chunks as a result of moving, and what is the most efficient way of doing so?

• Why are they stored in chunks? What are you trying to accomplish? Feb 18, 2015 at 18:33
• @mklingen Well, there are a few thousand entities. With that many, it slows down frame rate a ton by updated every entity every tick. To counter this, I can store entities in chunks and then just loop through the entities in chunks near the player. Feb 18, 2015 at 18:36
• @mklingen basically optimization. Feb 18, 2015 at 18:39
• I see. You have a fundamental problem. What you've done now is just made a 3D array of entities. What you actually want to do is store a dynamic list of entities inside each chunk. I see @jzx has already provided the answer. Note that the problem you're trying to solve is called Space Partitioning: en.wikipedia.org/wiki/Space_partitioning ; and it has many (potentially better) solutions than chunks. Feb 18, 2015 at 18:53

If you need to store entities in chunks it's probably better to actually store them in the chunks rather than a separate array.

public class Chunk {
public int SizeX;
public int SizeY;
public Entity[] Entities;
public Chunk[] Neighbors;
}

public class Entity {
// ...
public Chunk CurrentChunk;
// ...
}


You can still maintain the Chunks in row/column format elsewhere, but this way each chunk will be aware of its neighbors as well. When an entity leaves its CurrentChunk's Size bounds, remove it from CurrentChunk, add it to the corresponding neighbor, and change its CurrentChunk.

You'll have to repeat that, of course, if an entity somehow moves an entire chunk's size in a single frame.

• Thanks for this answer. I'll try to implement this. Also, an entity should never cross more than one border in one tick. Feb 18, 2015 at 22:41