Collision management help

[kneeride]

Hi guys,

Just wondering if anyone can offer some advice on designing my framework for testing collisions between objects. btw, I'm not using a physics engine because it would be overkill for my grid based game

This is an example of my (pretty straightforward) object hierarchy:

Object (abstract class)
- Player (inherits from Object)
- Monster (inherits from Object)
- Item (inherits from Object)

Basically I have the following algorithm to detect collisions:

Code: Select all

// test player collisions
for each monster, test and handle player/monster collision
for each item, test and handle player/item collision
// test monster collisions
for each monster, test and handle monster/item collision
// nb: item collisions have already been tested above

Ok this is my new idea. I'm thinking of now making my collision tests when an object moves.

Code: Select all

moveobject(object a)
{
    move the object to the new cell
    test if another object is in the cell
    handle any collisions:
	if (a is Player and b is Monster) then PlayerMonsterCollision(a, b)
	if (b is Player and a is Monster) then PlayerMonsterCollision(b, a)
	if (a is Player and b is Item) then PlayerItemCollision(a, b)
	if (b is Player and a is Item) then PlayerItemCollision(b, a)
	if (a is Monster and b is Item) then MonsterItemCollision(a, b)
	if (b is Monster and a is Item) then MonsterItemCollision(b, a)
}

This reduces my complexity from O(N^2) to O(N). My guess is this will be a huge performance boost, especially since only 20% of objects would be moving at a time.

I however have a few design barriers when implementing this:

I'm now performing collisions at the object level and I will need to cast back up to the Player/Monster/Item level. ie I'll need to grab attributes from the Monster object to deterine how to handle the collision. Also when casting up, I'll loose an type safety because the cast checks will be made at run time.

Another problem I have is ensuring a collision isn't performed twice. ie if the player and monster move in the same loop, then both of these lines will get called on 2 seperate moveobject calls:

if (a is Player and b is Monster) then PlayerMonsterCollision(a, b)
if (b is Player and a is Monster) then PlayerMonsterCollision(b, a)

Any tips on what I can do here?

Also how does physics engines handle this problem? I've very open to standard practise. From my understanding, they perform the collisions checks at the 'object' level and then you guys 'cast back up' to your own objects. Also my guess is they do a O(N^2) sweep after all objects have moved - but i could be wrong.

Is this how physics engines manage their collisions? (nb I understand they probably optimise by testing regions/zone etc however I want to keep this discussion at the higher level thanks)

Code: Select all

for each object
	move object

for each object
	for each object
		test collision

Thanks everyone.

[Valentin Perrelle]

This seems to be a language-related question. There is no algorithmic problem there. In OO languages, one would say that your 6 tests are actually a polymorphism and that you are trying to reimplement object dispatch: the function you need to call is choosen from the (dynamic) types of your objects. Double dispatch is generally implemented using a visitor pattern, and you would have to use it twice. (once for each argument)

Again, from an oriented-object perspective, the code to handle collisions would probably be factorized: the code for each collision is probably not so different. It's not clear you need 3 distinct functions.

For the symmetry problem, the universal way to solve this problem is to sort your objects by type, i.e. consider the set of two objects instead of the list. [a,b] != [b,a] but {a,b} = {b,a}, so you only have to test for {player, monster}, {player, item} and {monster, item}. Again, the way to write that is very language dependent.