About the darned grid, collisions and pathfinding

Game Mechanics
#1

Hello!

I’ve known for awhile that it’s better to index everything into a giant grid and then query said grid for entities, than querying the entire world.
I do have a few questions left unanswered, and I hope some of you can shed light on this.

I’ve tried to write this in an understandable way, and I even provide some illustrations.

A perfect situation of querying a grid, would be this:

The circle represents your entity, and it should be clear that the entity is indeed in cell (1, 1).

It’s easy to ask (in code) “Hey! Is anything in the way, over at (1, 1)”, and it’s easy to find out that the circle is there.

Consider this next scenario:

The circle is the same. It still fits within one square, but it’s not entirely inside a single square. This scenario is possible within a ton of games, but how do we handle it?
What cell is it actually inside? If we decide that it’s still (1, 1), then what happens if we need to check if there are no collisions in cell (2, 1)? Obviously the outcome isn’t great, because the game won’t recognize anything in the (2, 1) area.

Here’s an actual question: With the above in mind, do I want duplicate entries in the grid? If yes, I no longer have to worry about -||-
I always thought that I didn’t want duplicate entries, and so I’ve had a few thoughts on how to handle the problem.

Here’s one: I can query multiple cells, based on how big my entities are.
Let’s say that my largest entity, is equal to the size of the blue circle:

Now, if I want to query cell (3, 3), I need to do it like this:

Because my largest entity can leak over 9 cell, I need to query the 8 cell around the starting point to make sure I don’t miss anything (provided that there is only one entry of each entity). That makes performance a lot worse.

Is there any ways around this problem? Is there an easy way to find out what cells an entity is touching, if the entities center vector, and radius is available?

Also, how is pathfinding in an environment like this possible? I would make targets at the center of each cell, and just use the heuristic to get my entity there. That makes it easy to apply A* for instance. However, that way it can easily become difficult to find a valid path.
I don’t want to avoid a cell, just because the edge of an entity is slightly leaking into it. That doesn’t pose an actual obstacle, especially if the mover is a much smaller circle, that can easily maneuver past the edge of the leaking entity, without leaving the cell. I’ve illustrated this below.

Another thing is, how does one query collisions accurately, in this environment? Say, I want to know whether a small circle is intersecting with anything, but it’s radius is a cell’s width 1/20 (like a bullet in a game).

For completely practical reasons: How big should each cell be? Not too small because it’ll be slower, but not too big either. Is there any general rule of thumb, like equal to the size of my smallest entity?

I know a bunch of you have been working with an environment like this, so please enlighten me. :slight_smile:

Thanks a ton.

#2

An entity that spans multiple cells is in all of them. Finding out which cells an entity touches is as simple as making a bounding box around it – this should be pretty trivial for circles. This will result in some false positives on corners, but the idea isn’t for an exact position, it’s just to narrow down the list of entities you do more precise comparisons with.

A cell should be “big enough” to partition your space so that most cells contain only one or two objects, but that you’re not wasting space with empty cells between objects or having to inhabit several cells for every entity. You should consider dynamically adjusting it and benchmarking to see which arrangement fits best.

#3

Big question: What sort of game will this be for? If it’s a platformer, then there will be slightly different rules for how you design the node-set for your game (Pathfinding it is about the same, however). If it’s for something that’s relatively top-down, or where movement occurs unit by unit and only in strict compass directions (N-NE-E-SE-S-SW-W-NW) or something similiar, then your grid can be used for pathfinding.

Either way, a lot deals with how your movement rules work. Here are some things to consider (Which weren’t made too obvious by your post that you should think about. Sorry if I’m just not understanding your intention and mentioning things you felt answered!)

  1. Are movements/positions going to be grid-aligned at all?
  2. How do entities move? Platform: Do jumps have a calculable height/distance that they can typically be expected to attain, are there different ‘rules’ for walking across different spaces, etc. Actual Grid: Is it a single ‘step’ per turn (Think a rogue like) or is do they have a moment range (Think Final Fantasy Tactics) per turn?
  3. Decide whether entities can coexist on a given grid square. If it’s a strict no then this makes things pretty straight forward. If it’s a yes then you need to decide how you’re going to handle overlaps and the like.
  4. Like Sprongie said, your grid should be just the right size. Selecting the smallest entity that you possess and using that to designate your grid side could work, or a grid square that is the smallest possible movement distance per turn. This one depends on question 1, in that you’ll have some sort of trade off. If you select the grid by entity, but you have movement increments smaller than that, you’ll end up having an entity straddling several squares that way. If you select the grid by movement, but your units are all bigger than the smallest unit, then all units will straddle several squares simply due to size.

Why are these important?
Number of Paths Needed: Depending on how your movement system works, your entities are likely going to have to use the pathfinder quite a few times, perhaps as often as once per turn. For ‘Step’ method this is mainly to do with passable squares becoming impassable (See question 2) and can result in a form of thrashing (Think when you’re walking towards someone and you both step to the side to let the other pass). For the ‘range’ you’ll typically still end up needing to find paths as often, however the chance of the thrash mentioned above is less likely.
Path accuracy: Depending on how you’re handling overlap, you can end up with lots of sub-optimal paths (Which typically aren’t too much of an issue). This can get better/worse if you only find a new path when there’s an interruption on the current one or when you change targets.

#4

Shouldn’t this be accomplished with the exact method you linked to in an earlier collision problem?

If an object overlaps grids, check its collision against all the objects in those grids.

[EDIT]:
Here’s another more articulate and concise link for the same thing: http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

#5

Indeed, but there are still a few things left unanswered, like the pathfinding. I’ve come to the realization that entities that are in multiple cells, are added to each cells list.

You nailed it, and I admit I left out on quite a few things. I’m going to let you imagine how movement works for “TLOZ: A Link To The Past”, and assume you know your classics :wink:
Each entity is not blocking (In Zelda it was only imaginary because Link jumps back), and they are not aligned to the grid. They move completely independently of the grid, and eachother (in theory - I can still do a BB-overlap test, within the cell).
I thought I could make pathfinding work with the cells though (imagine the cell size as big as the tiles in Zelda), and just use trig to guide an entity towards the middle of each tile/node, until the node is reached. Then proceed to the next node. This should work great, but it doesn’t take into account other entities. It’ll just check whether or not a tile is occupied, and it could be occupied by just the nosetip of some skeleton, which is inaccurate if the entity is small enough. Else, I can disregard entities, but then I can’t have any collidable entities. I’d like to have that, since I might have boulders and other things to interract with.

#6

Here’s the collision manager I use. Notice how collisions are processed - each pair is notified an an arbitrary order of the collision. Make sure you understand that bit.


/*
 * Copyright (c) 2003-onwards Shaven Puppy Ltd
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of 'Shaven Puppy' nor the names of its contributors
 *   may be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package puppytron;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.lwjgl.util.ReadableRectangle;
import org.lwjgl.util.Rectangle;

/**
 * Grid-based collision manager.
 */
class GridCollisionManager implements CollisionManager {

	private static final int INITIAL_ENTITIES = 512;
	private static final int BORDER_TILES = 4;

	private static class Cell {
		final ArrayList<Entity> contents = new ArrayList<Entity>(4);
		boolean inUsed;
	}

	private static class Pair {

		Entity a, b;

		Pair(Entity a, Entity b) {
	        this.a = a;
	        this.b = b;
        }

		@Override
		public int hashCode() {
		    return a.hashCode() + b.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			Pair p = (Pair) obj;
			return ((p.a == a && p.b == b) || (p.a == b && p.b == a));
		}
	}

	/** Temp pair */
	private final Pair tempPair = new Pair(null, null);

	/** Temp rects */
	private final Rectangle temp = new Rectangle(), cells = new Rectangle();

	/** Collision pairs */
	private final List<Pair> collisions = new ArrayList<Pair>();

	/** Cell size */
	private final int cellSize;

	/** Bounds, in a rectangle */
	private final ReadableRectangle mapBounds;

	/** The sparse grid */
	private Cell[] grid;

	/** All cells which actually contain at least 1 entity */
	private ArrayList<Cell> used = new ArrayList<Cell>(INITIAL_ENTITIES), used0 = new ArrayList<Cell>(INITIAL_ENTITIES);

	/** Origin (grid) */
	private int ox, oy;

	/** Size (grid) */
	private int w, h;

	/** Map of Entities to ReadableRectangles; this maps Entities to the cells in which they have been placed */
	private Map<Entity, ReadableRectangle> entityMap = new HashMap<Entity, ReadableRectangle>(INITIAL_ENTITIES);

	private static int fastFloor(float x) {
		int i = (int) x;
		return x >= 0.0f ? i : i == x ? i : i - 1;
	}

    GridCollisionManager(int cellSize) {
		this.cellSize = cellSize;
		ox = -BORDER_TILES;
		oy = -BORDER_TILES;
		w = GameMap.SIZE + BORDER_TILES * 2;
		h = GameMap.SIZE + BORDER_TILES * 2;
		grid = new Cell[w * h];

		mapBounds = new Rectangle(0, 0, w, h);
	}

	@Override
	public void clear() {
		Arrays.fill(grid, null);
		used.clear();
		entityMap.clear();
	}

//	public Rectangle test(Entity entity) {
//		calcBounds(entity);
//		return calcCells(temp, new Rectangle());
//	}

	@Override
	public void store(Entity entity) {
		// See which cells we should be in and maybe resize the grid
		calcBounds(entity);
		Rectangle r = calcCells(temp, new Rectangle());

		if (entityMap.put(entity, r) != null) {
			assert false : "Entity "+entity+" is already in the entityMap!";
		}

		// Add this entity to each cell
//		assert r.getX() >= 0 : r+" "+temp+" "+entity;
//		assert r.getY() >= 0 : r+" "+temp+" "+entity;
//		assert r.getX() < w : r+" "+temp+" "+entity;
//		assert r.getY() < h : r+" "+temp+" "+entity;
//		assert r.getX() + r.getWidth() <= w : r+" "+temp+" "+entity;
//		assert r.getY() + r.getHeight() <= h : r+" "+temp+" "+entity;
		int cell = r.getX() + r.getY() * w;
		for (int y = r.getHeight(); -- y >= 0; ) {
			for (int x = r.getWidth(); -- x >= 0; ) {
				try {
					Cell c = grid[cell];
					if (c == null) {
						c = new Cell();
						grid[cell] = c;
					}
					c.contents.add(entity);
					if (!c.inUsed) {
						c.inUsed = true;
						used.add(c);
					}
				} catch (ArrayIndexOutOfBoundsException e) {
					System.err.println(r+" "+cell);
					e.printStackTrace();

				}

				cell ++;
			}
			cell += w - r.getWidth();
		}
	}

	private void calcBounds(Entity entity) {
		float radius = entity.getRadius();
		assert radius >= 0.0f : entity+" has radius "+radius;

		// it's a round entity - we'll expand its bounds a bit to account for freaky rounding
		int size = (int)(radius * 2.0f) + 2;
		temp.setBounds((int)(entity.getCollisionX() - radius) - 1, (int)(entity.getCollisionY() - radius) - 1, size, size);
	}

	public Rectangle calcCells(ReadableRectangle src, Rectangle dest) {
		int x0 = fastFloor(src.getX() / (float) cellSize);
		int y0 = fastFloor(src.getY() / (float) cellSize);
		int x1 = fastFloor((src.getX() + src.getWidth() - 1) / (float) cellSize);
		int y1 = fastFloor((src.getY() + src.getHeight() - 1) / (float) cellSize);
		dest.setBounds
			(
				x0 - ox,
				y0 - oy,
				(x1 - x0) + 1,
				(y1 - y0) + 1
			);
		Rectangle clipped = dest.intersection(mapBounds, dest);
		dest.setBounds(clipped);
		return clipped;
	}

	@Override
	public CollisionManager add(Entity entity) {
		store(entity);
		return this;
	}

	@Override
	public CollisionManager submit(ReadableRectangle rect) {
		return this;
	}

	@Override
	public boolean remove(Entity entity) {

		// Shortcut: look in entity map first
		ReadableRectangle existingCells = entityMap.remove(entity);
		if (existingCells != null) {
			int cell = existingCells.getX() + existingCells.getY() * w;
			for (int yy = existingCells.getHeight(); -- yy >= 0; ) {
				for (int xx = existingCells.getWidth(); -- xx >= 0; ) {
					Cell test = grid[cell];
					if (test == null) {
						assert false : "Entity "+entity+" was supposed to be at "+existingCells+" but isn't at "+(cell % w)+","+(cell / w);
						return false;
					}
					if (!test.contents.remove(entity)) {
						assert false : "Entity "+entity+" not found where it was expected!";
					}
					cell ++;
				}

				cell += w - existingCells.getWidth();
			}
			return true;

		} else {
			assert false : "Entity "+entity+" not found!";
			return false;
		}
	}

	@Override
	public List<Entity> checkCollisions(Entity entity, List<Entity> dest) {
		if (dest == null) {
			dest = new ArrayList<Entity>();
		}

		dest.clear();

		if (!entity.isActive() || !entity.canCollide()) {
			// Shortcut: src entity can't collide
			return dest;
		}

		calcBounds(entity);
		calcCells(temp, cells);

		int cell = cells.getX() + cells.getY() * w;
		for (int y = cells.getHeight(); -- y >= 0; ) {
			for (int x = cells.getWidth(); -- x >= 0; ) {
				Cell c = grid[cell];
				if (c != null) {
					List<Entity> contents = c.contents;
					final int n = contents.size();
					for (int i = n; --i >= 0; ) {
						Entity test = contents.get(i);
						if (entity != test && test.isActive() && test.canCollide() && test.isTouching(entity) && !dest.contains(test)) {
							dest.add(test);
						}
					}
				}
				cell ++;
			}
			cell += w - cells.getWidth();
		}

		collisions.clear();

		return dest;
	}

	@Override
	public List<Entity> checkCollisions(ReadableRectangle rect, List<Entity> dest) {
		if (dest == null) {
			dest = new ArrayList<Entity>();
		}

		dest.clear();

		calcCells(rect, cells);

		int cell = cells.getX() + cells.getY() * w;
		for (int y = cells.getHeight(); -- y >= 0; ) {
			for (int x = cells.getWidth(); --x >= 0; ) {
				Cell c = grid[cell];
				if (c != null) {
					List<Entity> contents = c.contents;
					final int n = contents.size();
					for (int i = n; --i >= 0; ) {
						Entity entity = contents.get(i);
						if (entity.isActive() && entity.canCollide() && entity.isTouching(rect) && !dest.contains(entity)) {
							dest.add(entity);
						}
					}
				}
				cell ++;
			}
			cell += w - cells.getWidth();
		}

		collisions.clear();

		return dest;
	}

	@Override
	public void checkCollisions() {

		// For each cell with something in it...
		for (int i = used.size(); --i >= 0; ) {
			Cell cell = used.get(i);
			if (cell.contents.size() > 0) {
				used0.add(cell);
			}
		}

		for (int cell = used0.size(); --cell >= 0; ) {
			// Process all combinations within that cell
			List<Entity> contents = used0.get(cell).contents;
			for (int i = 0; i < contents.size(); i ++) {
				Entity src = contents.get(i);
				if (src.isActive() && src.canCollide()) {
					for (int j = i + 1; j < contents.size(); j ++) {
						Entity dest = contents.get(j);
						if (dest.isActive() && src.isActive() && src.canCollide() && dest.canCollide() && src.isTouching(dest)) {
							// Inform both entities of the collision, in no particular order, unless already done
							tempPair.a = src;
							tempPair.b = dest;
							if (collisions.contains(tempPair)) {
								continue;
							}
							collisions.add(new Pair(src, dest));
							src.onCollision(dest);
							dest.onCollision(src);
						}
					}
				}
			}
		}

		// Compact used list
		used0.clear();
		for (int i = used.size(); --i >= 0; ) {
			Cell cell = used.get(i);
			if (cell.contents.size() > 0) {
				used0.add(cell);
			} else {
				cell.inUsed = false;
			}
		}
		ArrayList<Cell> temp = used;
		used = used0;
		used0 = temp;
		used0.clear();

		// Clear away collisions now they're all processed
		collisions.clear();
	}
}

Cas :slight_smile:

#7

Thank you so much Cas, that will definitely come in handy. I do find that quite hard to look at, and it doesn’t seem apparent which segments executes when.
I’m not sure I get the “pair” sentiment, and I’m definitely not going to resize my grid over any period of time just yet (I have little idea when to, and what sizes are desirable).

I want to understand your code, but I think a lot of understandability (In lack of a better word) went down the drain as performance improved (That’s usually how it goes :P).

#8

It’s not exactly intended for public consumption but it might give you the gist of how you might implement it yourself :slight_smile: That particular implementation assumes all entities are circular, and every time an entity is moved or its radius changes, you must remove() the entity and then store() it again. You call checkCollisions() once per tick to process all collisions, after all movement has taken place. There are a couple of other checkCollisions() methods to query the grid and return results as well.

Here’s a bit of a blast from the past: Collision detection in Alien Flux

Cas :slight_smile: