Collision detection in several directions (2D game)

[johanbrook]

Hi! I’ve got some issues with collision detection in a game me and a couple of other guys are working on.

It’s a 2D game where you move a player around in a world filled with other collidable objects (enemies, walls, etc.). The entities (subclasses of CollidableObject) should collide with each other. I’m using the Java class Rectangle for the objects’ collision boxes.

Rectangle has two handy methods I’m using below: intersects and outcode. I’m using outcode when checking in which direction another given collidable object is, in order to block that direction.

/**
 * Check whether this object is colliding with another CollidableObject.
 * 
 * The objects are colliding if their collision boxes intersect.
 * 
 * @param obj The specified CollidableObject
 * @return True if the objects are colliding, false otherwise
 */
public boolean isColliding(CollidableObject obj){
	
	return this.collisionBox.intersects(obj.getCollisionBox());
}

public Direction getCollisionDirection(CollidableObject obj) {		
	int code = this.collisionBox.outcode(obj.getCollisionBox().getLocation());		
       Direction d = Direction.ORIGIN;
      
       boolean top = false, bottom = false, right = false, left = false;
      
       if((code & Rectangle.OUT_TOP) == Rectangle.OUT_TOP)
           top = true;
       if((code & Rectangle.OUT_RIGHT) == Rectangle.OUT_RIGHT)
           right = true;
       if((code & Rectangle.OUT_LEFT) == Rectangle.OUT_LEFT)
           left = true;
       if((code & Rectangle.OUT_BOTTOM) == Rectangle.OUT_BOTTOM)
           bottom = true;
      
       if(top && left)
       	d = Direction.NORTH_WEST;
       else if(top && right)
       	d = Direction.NORTH_EAST;
       else if(top)
       	d = Direction.NORTH;
       else if(left && bottom)
       	d = Direction.SOUTH_WEST;
       else if(right && bottom)
       	d = Direction.SOUTH_EAST;
       else if(left)
       	d = Direction.WEST;
       else if(right)
       	d = Direction.EAST;
       else if(bottom)
       	d = Direction.SOUTH;
      
	return d;
}

Below is the relevant code in the main game loop. entities is a List with all the entities in the game.

/**
* Updates the game model.
* @param dt The time since the last update.
*/
public void update(double dt) {

	moveEntities(dt);
}

private void moveEntities(double dt) {
	for(Entity t : this.entities) {
			
		checkCollisions(t);
		t.move(dt);
	}
}


private void checkCollisions(Entity t) {
	
	for(Entity w : this.entities) {
		
		// This baby is in need of a grave refactor :)
		
		boolean stop = false;
		
		if(t != w && t.isColliding(w)) {
			
			Direction currentDirection = t.getDirection();				
			Direction blockedDirection = t.getCollisionDirection(w);

			if(t != w && t instanceof Player){
				System.out.println("-----\nPlayer direction: "+currentDirection);
				System.out.println("Collision direction: "+blockedDirection);
				
				int c = t.getCode(w);
				
				System.out.println("CODE: "+c);
				System.out.println("Top: "+ ((c & Rectangle.OUT_TOP) == Rectangle.OUT_TOP));
				System.out.println("Bottom: "+ ((c & Rectangle.OUT_BOTTOM) == Rectangle.OUT_BOTTOM));
				System.out.println("Left: "+ ((c & Rectangle.OUT_LEFT) == Rectangle.OUT_LEFT));
				System.out.println("Right: "+ ((c & Rectangle.OUT_RIGHT) == Rectangle.OUT_RIGHT));
			}
			
			System.out.println("----------\n"+t);
			System.out.println(w+"\n------------");
								
			if( (blockedDirection == Direction.NORTH_WEST ||
				 blockedDirection == Direction.WEST)
					&& (currentDirection == Direction.WEST || 
						currentDirection == Direction.NORTH_WEST ||
						currentDirection == Direction.NORTH)) {
				
				stop = true;
			}
			
			if( (blockedDirection == Direction.NORTH_EAST ||
				 blockedDirection == Direction.EAST) 
					&& (currentDirection == Direction.EAST || 
						currentDirection == Direction.NORTH_EAST ||
						currentDirection == Direction.NORTH) ){
						
				stop = true;
			}
			
			if( (blockedDirection == Direction.SOUTH_WEST ||
					 blockedDirection == Direction.WEST) 
						&& (currentDirection == Direction.WEST || 
							currentDirection == Direction.SOUTH_WEST ||
							currentDirection == Direction.SOUTH) ){
				
				
				stop = true;
			}
			
			if( (blockedDirection == Direction.SOUTH_EAST ||
					 blockedDirection == Direction.EAST) 
						&& (currentDirection == Direction.EAST || 
							currentDirection == Direction.SOUTH_EAST ||
							currentDirection == Direction.SOUTH)){
							
				stop = true;
			}
			
			if(blockedDirection == currentDirection){
				stop = true;
			}
				
			
			if(stop)
				t.stop();
		}
	}
}

Direction is an enum with the eight directions (N, S, E, W, NE, NW, SE, SW).

The problem: it’s only working in some directions. If the player moves to another object from north or west, collisions aren’t working. I’ve debugged the code, and it indeed does run through the code above. The printouts are showing legit results, but still the if blocks aren’t catching the correct direction.

I can’t for my life figure out why it’s only north and west. My unit tests are (supposedly) testing this (green).

I’d deeply appreciate any assistance. The project code is located in a repo at GitHub: https://github.com/johanbrook/medioqre/

Thanks!

[philfrei]

Looks like a fun debugging project.

Just a nutty idea, but North and West kind of suggest it might have something to do with the iteration order, if it proceeds in a direction like reading a book. Does checking against something that has already been collision-tested different in any way different from something yet to be tested?

For example, this might be the case if you only touch each possible combination of two objects once instead of twice, or if the second collision test between two objects somehow overwrites what happened in the first test, or doesn’t register because of something that happened during the first test.

I’m assuming the direction constants are all correct. That would be an embarrassing place for a typo (something I’ve certainly done before).

Wish I had time to download the code. This is kind of neat. (I’m working on some code with many colliding objects, but am using a representation of the screen as the place where I update and test locations rather than testing each object against every other object.)

[65K]

Just from a quick glance: you never check for blockedDirections NORTH and SOUTH, if that does mean anything.

[johanbrook]

[quote]Just from a quick glance: you never check for blockedDirections NORTH and SOUTH, if that does mean anything.
[/quote]
You’re correct, I am not, those checks are done with the block

if(blockedDirection == currentDirection){
	stop = true;
}

[quote]Just a nutty idea, but North and West kind of suggest it might have something to do with the iteration order, if it proceeds in a direction like reading a book. Does checking against something that has already been collision-tested different in any way different from something yet to be tested?

For example, this might be the case if you only touch each possible combination of two objects once instead of twice, or if the second collision test between two objects somehow overwrites what happened in the first test, or doesn’t register because of something that happened during the first test.
[/quote]
I’m suspecting something like this, but can’t isolate the cases (except for the main problem that collisions don’t work when the enemy is south or east of the player). I’d appreciate some advice on this.

Here’s the printouts of the two objects (t and w) from line 45-46 in the code posted:

[x:-9:y:1] [w:20:h:20] [speed:30] [moving:false] [dir:EAST] [hp:100]
[x:0:y:0] [w:20:h:20] [speed:0] [moving:true] [dir:SOUTH_WEST] [hp:100]
------------
----------
[x:0:y:0] [w:20:h:20] [speed:0] [moving:true] [dir:SOUTH_WEST] [hp:100]
[x:-9:y:1] [w:20:h:20] [speed:30] [moving:false] [dir:EAST] [hp:100]

As you can see, the order och t and w is switched. Haven’t analyzed this yet.

Below is a screenshot of what’s happening.

(Larger: http://f.cl.ly/items/3g0A0U3T0B0p2Z0Z0L16/Skärmavbild%202012-04-19%20kl.%2009.29.27.png)

The player is the leftmost guy (haven’t made sprites for enemies yet). Check the console: the player’s direction is EAST and the enemy is situated NORTH EAST of the player. The top: true, right: true printouts also verify this.

So why aren’t they colliding? It’s something with my if blocks that aren’t correct. I’ve worked with this for so long now I’m going crazy: seems I can’t think straight any longer

[quote]That would be an embarrassing place for a typo (something I’ve certainly done before).
[/quote]
It would indeed, but I certainly hope people here can help me find it

[johanbrook]

Worth noting is that switching order of the if blocks isn’t changing anything (I thought stuff were overwriting other stuff).

[philfrei]

Just trying to think this through a bit:

In the code which checks for collisions, you iterate through each object, and test it against every other object, yes?

So, you check T, and find it is colliding with W, and T is set “stop = true”. Anything else changed for the state of T at this time? Do you do anything to compensate the motion so that the collision state no longer occurs?

Later in the same collision iteration, you get to object W, and test it against every object, including T. However, T is now “stopped” or has had some other state changes, meaning the results could potentially be different this time the collision is tested. Does that “stop=true” value affect the result of this second test, from W’s perspective?

I am assuming that the order of the tests is such that the first test will always be (or will tend to be) from the point of view of the object that is higher and to the left. (Y value is lower, X value is lower) And the second test (when the enemy POV was tested first) is the problem.

Only other thing I can think of is to limit the screen to two objects and set them no more than a turn or two away from collision and set a breakpoint at the top of the if blocks. Stepping through and examining state of both objects should reveal something!

[philfrei]

private void moveEntities(double dt) {
   for(Entity t : this.entities) {
         
      checkCollisions(t);
      t.move(dt);
   }
}

So, if the enemy is (t) and a collision is detected with the player, I notice that you move t in the very next line, before you have a chance to check the collision from the POV of the player. Does this move() method change the state of (t) such that it causes the collision check to fail when the player becomes (t) and the enemy becomes (w)?

(I’m also wondering about t.stop() at the end of the collision check. Will this affect the second test?

When I did a brute force collision test like this in the past, I used two passes. In the first I marked every object in collision, and in the second iteration I resolved the collisions for all the marked objects. That kind of change to the logic might help.

private void moveEntities(double dt) {
   for(Entity t : this.entities) {         
      checkCollisions(t);
   }

   for(Entity t : this.entities) {
      t.move(dt);
   }

}

[johanbrook]

Thanks for the great replies.

Some more info: in the class Entity (inherits from CollidableObject) I have these instance variables below. In conjunction with them, here are relevant methods:

private int movementSpeed;
private boolean isMoving;
private Direction direction;

/**
 * Move in a the set direction.
 * 
 * @param dt Delta time
 * @pre isMoving() == true
 * @see setDirection()
 */
public void move(double dt) {
	// Upper left corner is origin
	
	if(this.isMoving){
		Point currPos = getPosition();
		
		int x = (int) (this.direction.getXRatio() * (double) this.movementSpeed * dt);		
		int y = (int) (this.direction.getYRatio() * (double) this.movementSpeed * dt);
					
		this.setPosition(currPos.x + x, currPos.y + y);
		EventBus.INSTANCE.publish(new Event(Property.DID_MOVE, this));
	}
}

/**
 * Let the entity stop.
 * 
 */
public void stop() {
	this.isMoving = false;
	
	EventBus.INSTANCE.publish(new Event(Property.DID_STOP, this));
}


/**
 * Let the entity start moving.
 * 
 */
public void start() {
	this.isMoving = true;		
}

/**
 * Set a direction of the entity.
 * 
 * Note: Will only set a new direction if <code>dir</code>
 * differs from the current direction.
 * 
 * @param dir The new direction
 * @pre getDirection() != dir
 */
public void setDirection(Direction dir) {
	
	if (this.direction != dir) {
		this.direction = dir;
		EventBus.INSTANCE.publish(new Event(Property.CHANGED_DIRECTION, this));
	}
}

As you can see, move() ONLY actually moves an object IF the isMoving boolean is true, which is handled with start() and stop(). Apart from that, no other methods actually change the state of the object.

I get your reasoning about the iterations, and it’s indeed something in there. It wouldn’t surprise me if I’ve got some of the iteration logic wrong. Your suggestion regarding separating the collision checks and the actual movement method is clever, will investigate.

In my head, I’ve seen the t variable as the player, and w as the opponent. But even if we think the other way around (= t is enemy, w is player) issues shouldn’t arise, since I’m not changing anything related to the OTHER object in each iteration. I.e., I’m only manipulating t in each iteration, and not its opponent (may it be a player or an enemy).

I’ve reduced the test case to only check for collisions with the isColliding() method, and that indeed works as intended.

What bugs me is the special cases: why no collisions when the player is approaching an enemy from west and north?

Have a look at this scenario:

(Large: http://f.cl.ly/items/0P182k3W3n2e1g1z1F3w/Skärmavbild%202012-04-19%20kl.%2011.37.06.png).

The player is REALLY close to the (only) enemy, and the “Collision direction” is set to NORTH, which would cause all my direction checks to fail, and stop would be set to false.

[philfrei]

I see your point about the result of a collision being a “stop”, and thus the two checks (player as t, enemy as t) should match state. But, just to double check, does the collision test use the current position or the “next” position of the entities? Entity state includes location, speed, direction, not just the boolean isMoving. If “next” positions are used for the check, and one of the entities is stopped (and the future move not made) then the second test will be using different state info from the first.

How well do the rectangles and the graphics for the object line up? For example, if the graphic is printed evenly around a center point, and the rectangle extends east and south from the center point? Or, if the player is centered and the enemies are drawn from the corner position? (Just a double check for a common overlook.)

Another ideas for troubleshooting:

• reverse the order of occurrence in the entities array, and see if this changes anything.

But I still think setting a breakpoint for the start of the collision testing would be best, and step debugging. For a breakpoint, you can sometimes write a conditional that will only execute when conditions are optimal, and break on that. I think you want to verify that the results of intersects() and outcode() are what you think they are.

Duh! You can do this (and easily step debug): make a unit test of checkCollisions(), and feed it isolated cases that test various locations.

e.g.,

    Entity enemy = new Entity(); // then set the location
    Entity[] entities = { enemy };  // or whatever is needed to load entities with the single enemy object 
    Player p = new Player(); //  then set the location
    checkCollisions(p);

    p.setLocation(); // or whatever is needed to put in a new location
    checkCollisions(p); 

    // and repeat for all the test cases 

[johanbrook]

Hi again, my sincerest thanks for your suggestions. I’ve actually solved the problem now!

It was Rectangle’s outcode which used “incorrect” comparisons in order to return an integer constant for the position. I wrote an almost exact implementation in my super object class, which corrected the issues described. “Never trust other’s code”, eh?

It took days of debugging Thanks!

The code:

public int getLocationOfPoint(int x, int y) {
	int out = 0;
	if (this.collisionBox.width <= 0) {
	    out = LEFT | RIGHT;
	} else if (x < this.collisionBox.x) {
	    out |= LEFT;
	} else if (x > this.collisionBox.x) {
	    out |= RIGHT;
	}
	if (this.collisionBox.height <= 0) {
	    out |= TOP | BOTTOM;
	} else if (y < this.collisionBox.y) {
	    out |= TOP;
	} else if (y > this.collisionBox.y) {
	    out |= BOTTOM;
	}
	return out;
}