Introduction

Efficiently mapping game entities to positions is a core performance problem in Java game development. A simple list of entities works for tiny worlds, but once you need collision detection, proximity checks, or region-based updates, you usually want a spatial structure that limits how much of the world each query has to scan.

Start With a Clear Position Model

At minimum, each entity needs an identifier and position data. A small immutable position record keeps the code easy to reason about.

1public record Position(int x, int y) {}
2
3public final class Entity {
4    private final int id;
5    private Position position;
6
7    public Entity(int id, Position position) {
8        this.id = id;
9        this.position = position;
10    }
11
12    public int getId() {
13        return id;
14    }
15
16    public Position getPosition() {
17        return position;
18    }
19
20    public void setPosition(Position position) {
21        this.position = position;
22    }
23}

If you only keep entities in a List<Entity>, every lookup like "which entities are near this point" becomes a full scan. That is often too slow once entity count grows.

Use a Spatial Hash Grid for Fast Local Queries

A practical solution for many 2D games is a spatial hash or fixed grid. Divide the world into cells, then map each cell to the entities currently inside it. Queries only inspect nearby cells instead of the whole entity list.

1import java.util.*;
2
3public final class SpatialGrid {
4    private final int cellSize;
5    private final Map<Cell, List<Entity>> cells = new HashMap<>();
6
7    public SpatialGrid(int cellSize) {
8        this.cellSize = cellSize;
9    }
10
11    public void add(Entity entity) {
12        Cell cell = cellFor(entity.getPosition());
13        cells.computeIfAbsent(cell, key -> new ArrayList<>()).add(entity);
14    }
15
16    public void move(Entity entity, Position oldPosition, Position newPosition) {
17        Cell oldCell = cellFor(oldPosition);
18        Cell newCell = cellFor(newPosition);
19
20        if (!oldCell.equals(newCell)) {
21            List<Entity> oldList = cells.get(oldCell);
22            if (oldList != null) {
23                oldList.remove(entity);
24                if (oldList.isEmpty()) {
25                    cells.remove(oldCell);
26                }
27            }
28            cells.computeIfAbsent(newCell, key -> new ArrayList<>()).add(entity);
29        }
30
31        entity.setPosition(newPosition);
32    }
33
34    public List<Entity> getNearby(Position position) {
35        Cell center = cellFor(position);
36        List<Entity> result = new ArrayList<>();
37
38        for (int dx = -1; dx <= 1; dx++) {
39            for (int dy = -1; dy <= 1; dy++) {
40                Cell neighbor = new Cell(center.x() + dx, center.y() + dy);
41                List<Entity> bucket = cells.get(neighbor);
42                if (bucket != null) {
43                    result.addAll(bucket);
44                }
45            }
46        }
47
48        return result;
49    }
50
51    private Cell cellFor(Position position) {
52        return new Cell(position.x() / cellSize, position.y() / cellSize);
53    }
54
55    private record Cell(int x, int y) {}
56}

This pattern is effective because insertion and lookup are usually close to constant time on average, and the query cost depends more on local density than total world size.

Keep Movement Updates Cheap

Position mapping becomes expensive when moving entities require too much bookkeeping. The grid approach above updates only when an entity crosses a cell boundary. If an entity moves within the same cell, you can skip all map modifications and just update its position.

That small optimization matters because most game loops update entity positions every frame. Removing and re-adding every entity every frame creates unnecessary object churn and hash map traffic.

A useful rule is this:

• update the position field every frame
• update the spatial index only when cell membership changes

That keeps the hot path simpler.

Choose the Structure That Matches the Game

A fixed grid is not the only option. Different world shapes favor different structures.

• Dense, tile-based worlds often work well with arrays or fixed grids.
• Sparse open worlds often benefit from hash-based spatial indexing.
• Highly uneven distributions may justify quadtrees or other hierarchical structures.

For many Java games, a hash grid is the best starting point because it is much easier to implement and debug than a quadtree. Only move to a more complex structure if profiling shows the grid is the bottleneck.

Avoid Premature Complexity

It is tempting to build a fully generic spatial engine immediately, but that usually makes iteration slower. Start with the smallest structure that supports your real queries. If the game only needs nearby collision checks in a 2D world, a grid backed by HashMap<Cell, List<Entity>> is often enough.

You should also profile object allocation. If garbage collection becomes visible in frame times, consider reusing lists, storing entity ids instead of full objects, or using primitive-friendly collections. Those are second-stage optimizations, not first-stage design requirements.

Common Pitfalls

• Storing all entities in one list and scanning it for every proximity check does not scale once entity counts increase.
• Rebuilding the entire spatial map every frame creates avoidable overhead. Update only when entities cross cell boundaries.
• Choosing a cell size without relation to gameplay leads to poor performance. Cells that are too small increase bookkeeping, while cells that are too large weaken query filtering.
• Using mutable keys in hash-based structures can corrupt lookups. Cell keys should be immutable.
• Implementing a quadtree before measuring the actual bottleneck often adds complexity without improving frame time.

Summary

• Model entity positions clearly, then choose a spatial index that matches your query patterns.
• A spatial hash grid is a strong default for many Java 2D games.
• Update the index only when an entity changes cells, not on every minor movement.
• Match cell size to the interaction radius and density of your world.
• Profile first, then decide whether you need more complex structures such as quadtrees.