Scalable Approaches to Collision Resolution.

[Azzla]

In the evolution of my project, more and more objects are interacting and colliding with each other. This is presenting an interesting "philosophical" (architectural?) problem regarding collisions which I can't quite figure out a clean solution to. Not so much a technical "how-to" question, which is why I've chosen to post this in General. Just for the record, I'm using HardonCollider for detection.

A basic description of the problem. Lets say I have four classes/entity types which are all capable of colliding with each other.

1. Player
2. Enemies
3. Projectiles
4. Environment (boundaries, walls, obstacles etc)

In the simplest case of just player and enemies, I might use a simple class method like the following for resolution:

Code: Select all

function Player:collide(enemy)  
  self.health = self.health - enemy.damage
end

However, the player can collide with multiple objects, so now we need some kind of generic method with validation. (e.g. the player shouldn't be hit by their own projectiles)

Code: Select all

function Player:collidesWith(object)
  --defensive programming can help somewhat
  if object.isProjectile then return end --at some point we may also have to distinguish between player/enemy projectiles
  
  --resolve
  if object.isEnemy then
  	object.dead = true --flag the enemy as despawnable for an entity manager
  	self.health = self.health - object.damage
  elseif object.isObstacle then
  	--perform whatever logic on the player's velocity, position, etc
  end
end

This is all fine and well, but not only will this resolution code get increasingly complex, but we run into another, more fundamental problem of how to handle collisions from other instantiated objects. If every object has its own collision resolution method, how do we determine whose takes precedence? It makes sense to handle collisions with a Player object from the Player object's perspective, but sometimes other objects may need their own logic.

Code: Select all

function Enemy:collidesWith(object)
  if object.isEnemy then return end
  if object.isProjectile then
    self.health = self.health - object.damage
  end
  if object.isObstacle then
    --vector/velocity/position transforms
  end
  
  if object.isPlayer then
    --let the player handle this? Since its just an inversion of the same scenario from the player's collide method?
  end

It seems like either way, the collide methods necessarily contain side effects. Either player:collidesWith() receives the enemy object and mutates its state, or enemy:collidesWith() receives the player object and mutates its state. If this is unavoidable, how do decide whose resolution function is more "important"?

I just want to quickly note that I am not dogmatic about paradigms; I generally find OOP helpful in game development, but if another approach is better suited I will take it. In prior versions of my game where my code was more procedural/functional the same problem occurs.

Code: Select all

function playerCollidesWith(something)

versus

Code: Select all

function enemyCollidesWith(something)

or even

Code: Select all

function collide(object1, object2)

are just varying abstractions with the same basic problem. Collision stuff just generally becomes painful with increasing entity types and interactions.

When I started out long ago, I used the bump library, and the author's approach to validation is the idea of "filters", where a collider defines predetermined responses to other colliders (almost the same thing as my class method approach). As for the precedence problem, it still isn't clear:

We can have a playerFilter and an enemyFilter and a projectileFilter but we still have to decide who handles various scenarios. Does playerFilter handle player collisions with enemies, or vice versa? Does projectileFilter handle projectile collisions with enemies and obstacles? Does obstacleFilter handle obstacle collisions with projectiles and enemies and the player?

I figured I'd throw this on the forum to see if anyone has good ideas, because maybe I'm simply thinking about this the wrong way. It's not a major hurdle; usually I just "decide" who handles what arbitrarily and move on. The only issue is, with rising project complexity, sometimes I have to hunt down who is handling which collision scenarios to alter them. I may forget that projectiles are handling collisions with enemies, or the other way around. I'd like to avoid playing "find the collision handler" as much as possible.

[dusoft]

This sounds like overthinking to me. I understand you would like your code to be clean and abstract enough, but just go with whatever works for you.

As for the precedence this is again up to you to decide. In the end damage is done and since it should be simple subtraction, order doesn't really matter, does it?

I would prefer having universal collision callback to resolve any and all collisions, but you might prefer something else.

[Azzla]

In the end damage is done and since it should be simple subtraction, order doesn't really matter, does it?

The subtraction was just an example for demonstration's sake, my actual game's callbacks are much more involved.

By "universal" callback do you mean something like this approach?

Code: Select all

function collide(object, other)

The upside is every collision scenario in one location, and we avoid the precedence issue by delegating the entire responsibility to an external manager, not the entities themselves. I think a downside is that this function will grow enormous and be difficult to modify pretty quickly.

I don't really buy that I'm overthinking this problem - I feel certain there is a better way that I haven't thought of. Keeping code clean and maintainable has real consequences for projects of much larger scope, if this was just a week-long gamejam entry of course I wouldn't bother at all.

[dusoft]

The subtraction was just an example for demonstration's sake, my actual game's callbacks are much more involved.

Indeed, but the order of applying damages is really up to you and your model.

By "universal" callback do you mean something like this approach?

Code: Select all

function collide(object, other)

The upside is every collision scenario in one location, and we avoid the precedence issue by delegating the entire responsibility to an external manager, not the entities themselves. I think a downside is that this function will grow enormous and be difficult to modify pretty quickly.

Yes, this one. E.g. a manager for collisions. You can structure it into multiple functions instead of all conditions inside this callback/manager.

But really I think you should just keep moving and decide once you think it's getting bloated. Execution is better than planning in identifying hurdles and solutions.

[togFox]

I only recently discovered this collision detection library: https://github.com/Aweptimum/Strike

It does

Code: Select all

local hasCollided = collision(object1, object2)

(^- not exact code)

It's super simple and the advise is you make a table of all the colliding objects and then iterate through that table looking for key events (e.g. person colliding with bullet). The coder has full control.

I'm mostly familiar with the box2d BeginContact(object1, object2) callback method that does a lot of heavy lifting.

[BulbaMander]

Do you have any time today to chat about our lord and savior entity component system?

In short I'm also a fan of this approach:

Code: Select all

function collide(object1, object2)

However, the way I do it is a little bit different. Basically I abstract out collision, but I also abstract out the effects of that collision. It's all handled by a "manager" of sorts.

I keep a list of all objects that can collide, but I also have tables whose membership is predicated on how it's members would respond to a collision. In other words I have a "damageable" table, a "damaging" table, a table for objects that affect physics (walls), and a table of objects that would have it's physics affected by such an object (player, enemy).

I have a single function that checks for collisions among all collisional objects, and saves which object collided with which others. Then I loop over all the damageable objects, check if they collided with an object, and whether or not that object is in the damaging hash. I do the same for the physics affecting tables.

I /believe/ all this seemingly extra looping isn't actually a performance impact, because doing two things in one loop is the same as doing one thing in two loops.

[Azzla]

I keep a list of all objects that can collide, but I also have tables whose membership is predicated on how it's members would respond to a collision. In other words I have a "damageable" table, a "damaging" table, a table for objects that affect physics (walls), and a table of objects that would have it's physics affected by such an object (player, enemy).

That seems really interesting! I might be doing something similar already, for a different project. I have an entity manager that holds all the entities in a table. The manager includes a sort of "filtering" function that returns a new table of references to just the existing entities that meet a criteria (like your "damageable" example). Basically just JS's array.map but for more generic stuff like "isEnemy" or "canAttack". I iterate through those filtered tables for various pathfinding/targeting systems, but for some reason hadn't thought to use the same idea for collision resolution. I'll give it a try and run a profiler on it to see if the 'looping twice' thing has notable performance costs.

Do you have any time today to chat about our lord and savior entity component system?

Haha. Bit of a tangent but... OOP has been letting me down a lot lately so I've been meaning to give ECS a serious try. I'm in university for CS and OOP is still taught as the fundamental, de-facto standard. The more I try to work with it however, the less I'm convinced it's actually helping me accomplish anything tangible besides the occasional "modular code good" feeling. OOP has you writing lots of boilerplate interfaces with good intentions of "protecting" state but also the consequences of bloated runtimes and difficult-to-traverse inheritance hierarchies.

The most insidious problem for games might be that it encourages premature implementation/abstraction, when you aren't fully cognizant of what your algorithmic requirements are. It can lock you into naïve early decisions, or paralyze you into spending all your time designing the codebase instead of the game itself.