Collision Strategies

[ravenger]

Earlier this year i was working on a pacman game (http://www.java-gaming.org/forums/index.php?topic=12086.0) for a course in AI at the university im studying at, roughly based on Kevin Glass his Space Invaders tutorial. I finished it and got an A+ for it of which im quite proud, but since im following a course on Design Patterns now and since i have plans to do an internship at a major gamedeveloper and thus need a nice portfolio, ive decided to implement some of them into my Pacman game to make the code cleaner and the game extendable.

Since i still use the original collision detection methods from the tutorial, something like this;

if(pacman.collidesWith(x)){
	pacman.collidedWith(x);
	x.collidedWith(pacman);
}

It also still uses the instanceof, for example here in my GhostEntity class;

public void collidedWith(Entity other) {
	if(other instanceof PacmanEntity) {
		finalPath.clear();
	}
}

Point is that ive come to the conclusion that using instanceof is a prove of flaud design in this case, and ive decided to replace this collidedWith method by implementing collision strategies somehow on the hand of the Strategy pattern (http://en.wikipedia.org/wiki/Strategy_pattern). What if i could do something like this, and make derived classes for each entity that needs to have a collisionstrategy:

public interface CollisionStrategy {

	public void collidedWith(GhostEntity other);
	public void collidedWith(PacmanEntity other);
	public void collidedWith(WallEntity other);
	public void collidedWith(DotEntity other);
	
}

For instance we have the PacmanCollisionStrategy which looks like this;

public class PacmanCollisionStrategy implements CollisionStrategy {

	private PacmanGame game; 
	
	public PacmanCollisionStrategy(PacmanGame game){
		this.game = game; 
	}
	
	public void collidedWith(GhostEntity other) {
		game.notifyDeath();
	}

	public void collidedWith(PacmanEntity other) {}
	public void collidedWith(WallEntity other) {}
	public void collidedWith(DotEntity other) {}
}

And the constructor of the Entity class of which all entities derive then looks like this, together with the collisioncheck method (which obviously doesnt work in this way);

public Entity(String ref, double x, double y, int size, CollisionStrategy collisionStrategy) {
	this.sprite = SpriteStore.get().getSprite(ref);
	this.x = x;
	this.y = y;
	this.size = size;
	this.collisionStrategy = collisionStrategy;
	this.setSpawnPosition(new Dimension((int)x/20,(int)y/20));
}

/
public void collidedWith(Entity other) {
	collisionStrategy.collidedWith(other);
}

And i can now do this in my game initialization method:

pacman = new PacmanEntity("pacman.gif",this,20,20,size,moveSpeed, new PacmanCollisionStrategy(this));

The only thing is, im still not rid of the point that i have to determine somehow which method to use, similar to why you would use instanceof, because im still stuck with an arraylist of Entity objects, which i traverse inside my collision detection method to check for collisions.

for (int p=0;p<entityList.size();p++) {
	for (int s=p+1;s<entityList.size();s++) {
		Entity me = (Entity) entityList.get(p);
		Entity him = (Entity) entityList.get(s);

		if (me.collidesWith(him)) {
			me.collidedWith(him);
			him.collidedWith(me);
		}
	}
}	

Anyone got any ideas on how i could get to where i want to be?

[Orangy_Tang]

IMHO but collision between a range of primatives like this is well suited to the DoubleDispatch pattern. It looks like you’re almost there yourself.

[Don_Kiddick]

You could,

• Have the entities handle their own collisions which is more OO in a way - tell don’t ask.

class Entity {
  void collidedWith(Entity entity)
}

• Internally you may want to handle collisions differently depending on what you collided, which is your original problem. Use a Map of class, to CollisionStratgey to look up the correct stratgey to use.

class Entity {
  private Map<Class? extends Entity, CollisionStratagy> collisionStrategies;

  void collidedWith(Entity entity) {
    CollisionStratagy cs = collisionStrategies.get(entity.getClass());
    cs.collidedWith(entity);
  }
}

ps. CollisionStrategy should now have one method :

public interface CollisionStrategy {

	public void collidedWith(Entity other);
	
}

D.

[CommanderKeith]

Without meaning to, I use that double-dispatch pattern. Tt works well. It lets both objects have an opprtunity to know that they are being collided with the other object. Its the best OO strategy as far as I can tell.

Keith

[dishmoth]

Interesting discussion! I hadn’t come across it before, but the DoubleDispatch pattern certainly looks to be a neat way of organising collision checks.

Trouble is… Is it only me who squirms at the idea of checking for collisions between all possible pairs of Entities in the game? In the original Pacman example, that means on every update you’re checking for a collision between every pair of dot entities, every pair of wall entities, and every pairing of a dot and a wall. Last time I played Pacman, none of these collisions seemed likely to occur!

Okay, so in practice these null collision checks probably end up taking a negligible amount of time, but it still somehow seems wrong to me to be using an O(N²) approach for checking for what is in practice a small number of potential collisions.

Anyone want to tell me that I’m overreacting?

Simon

[kevglass]

Kinda out of the scope of the question, that’s collision detection, this seems to be about collision response. I’d assume comparing every entitiy against every other is working performance wise for the poster.

However, I was quite surprised that it was approached this way too. This is the second person to do this based of the space invaders stuff too. I would have thought Entities would be ghost and pacman, and the rest would be handled in a tile map with the simple collision that brings.

Kev

[Orangy_Tang]

Personally I’ve got two main gripes with the double dispatch pattern - one is that it’s unweildy to implement, and the other is that you need to know all objects which interact at compile time.

The second issue is the real killer - it’s nice to be able to write a game with semi-generic ‘entities’ and drop in new ones at a later point. Double dispatch makes this pretty tricky - I’ve tried working around this with various catergories of entity, and doing double dispatch for those, but this tends to get hairy and nails you down to a particular division of entities and groupings. Then there’s the obvious performance problem with comparing everything against everything else (realistically not a problem, but somewhat cringeworthy).

IMHO where double dispatch pays off is in the initial collision detection. Typically you’ll only have a few types of collision primitives (circles, boxes, lines, points) but you might want to do collisions between all of these types. Doing a double dispatch with these lets you do something like:

boolean collided = pacman.getBounds().intersects( ghost.getBounds() );

…and you don’t care what the bounds are actually represented as.

When it comes to the actual reaction I think the best way is usually to keep things simple and game specific. In this case I’d just test pacman against all ghosts, and let the pacman class handle a collision if it occurs. Tilemaps and other mostly static environment stuff I think are special enough to handle separately.

[purpleguitar]

Sorry to be a late poster on this thread.

I wanted to point out to the OP: if you’ve studied design patterns at university, it was probably based on the Gang of Four book, and you’ve probably seen the Visitor pattern. In my experience, “Visitor” is the more common name for this pattern, and “double dispatch” is the more common name for the programming technique. The nomenclature varies depending on your source, of course, and nowhere is it written in stone that one name is correct.

Of course, if you believe that the GoF Design Patterns book is the best common reference, and that a fundamental reason for cataloging design patterns is to promote effective communication about software architectures, then you might join us in calling it “Visitor”.

[ravenger]

Sorry i kinda left this topic to it for a while, but i recently found the time to pick it up again a bit and ive started working on implementing the Visitor pattern as a way of handling collisions. As Orangy Tang stated earlier, i was quite close allready, tho i didnt really saw it back then Anyway, ive been thinking about how to implement it properly, and ive stumbled upon a few things that i wanna evaluate before im actually gonna go for the finishline.

First of all, ive looked into what Kevin said about having a tilemap with tiles instead of having all entities. I made the difference between entities and tiles, as in pacman and ghosts being entities and walls and pills being tiles. My first stumble is where i have a pill being a tile. Its basicly the definition of things thats keeping me busy; A tile to me is something that is allways there, an entity is something that generally moves around. (You could say “hey wheres the point in that, its just a minor detail, dont worry about it too much” but to me its really the essence of getting a good model so that if i make a next game, i can use the experience to tackle more complex object related issues). So my first question here is, is it usefull to see pils as a third kind of object (along with cherries and big pills etc)?

Next ive been looking into the visitor pattern (http://en.wikipedia.org/wiki/Visitor_pattern) and how to implement it. I noticed that i actually was really close on this allready. I’ve got different objects, and lets say i make a third kind of object, id make them all inherit the interface visitable because thats their main purpose. Next, Id make pacman inherit Visitor, and to this extend i can see it all working out just fine. Now ofcourse pacman isnt pacman if there werent any ghosts. If id look at the definitions again, this time of the pattern itself, the ghost should be visitable, because if pacman picks up a big pill he’s able to eat ghosts. This is where i stumble upon next. Shouldnt pacman be visitable aswell, and let the ghost be a visitor too? This because if a ghost touches pacman, pacman dies. This would imply that i need two different visitor interfaces; one for pacman and one for the ghost. My question to this is, am i overdoing things here ?

[ravenger]

Allright well, since the forums were down for a couple a days i’ve worked it out by myself.

The first issue i solved, indeed by making a third kind of object which i call a CollectableObject. I guess it was the obvious thing to do anyway because pills and superpills etc all have a couple of things in common anyway; they cant move, and they add score.
The second issue i solved aswell, by making pacman a visitor and by making Ghost and CollectableObject visitable. I’ve got some examplecode here;
The Collectable class:

public class Collectable extends Entity implements Visitable {

	private int score;
	
	public Collectable(String ref, double x, double y, int size, int score) {
		super(ref,x,y,size);
		this.score = score;
	}
	
	public int getScore() {
		return score;
	}

	public void accept(Visitor visitor) {
		visitor.visit(this);
	}
}

Pacman:

public class Pacman extends Movable implements Visitor {

	private PacmanGame game;

	public Pacman(String ref, PacmanGame game, double x, double y, 
						int size, double moveSpeed) {
		super(ref, x, y, size);
		this.game = game;
		this.moveSpeed = moveSpeed;
	}
	
	public void move() {
	        ....
        }

	public String toString() {
		return "Pacman";
	}

	public void visit(Ghost ghost) {
		// TODO check ghost status and if ghost is eatable, send ghost back to start, else, pacman dies
		game.notifyDeath();
	}

	public void visit(Collectable collectable) {
		game.addScore(collectable.getScore());
		game.removeCollectable(collectable);
	}
}

And the collision detection code in the mainloop:

	private void checkForCollisions() {
		// First we check if pacman collides with ghosty
		for(int i = 0; i < movablesList.size(); i++) {
			// Pacman shouldnt meet himself ofcourse
			if(movablesList.get(i).equals(pacman)) {
				continue;
			}
			// We check if the ghost is in the neighbourhood
			if(movablesList.get(i).collidesWith(pacman)) {
				// if so, we let ghosty accept pacman as his visitor and battle it out
				((Ghost)movablesList.get(i)).accept(pacman);
			}
		}
		
		// Next, pacman is hungry
		for(int i = 0; i < collectablesList.size(); i++) {
			if(collectablesList.get(i).collidesWith(pacman)) {
				// if pacman stumbles upon something eatable, the eatable must accept its doom
				collectablesList.get(i).accept(pacman);
			}
		}
	}

As you probably notice, theres one minor thing in there, i have to check the movablesList to see if im not dealing with pacman when checking for collisions. This could ofcourse be solved by moving pacman out of the movablesList, but that brings a lot of extra stuff which i dont want.