Trouble with inter-mob collision

[RyanImperion]

.....Hello! I've been working on a project with the aid of Sockmunkee, and I've run into a bit of a snag. He loaned me some of his collision code that I've been trying to integrate, and I've had the oddest bug. What I'm trying to do is have every mob check with other mobs to see if they're colliding. If they are, then they stop moving in that direction (Hopefully). I've attached both .loves here Hopefully you guys can help me out, since this has been stressing me for the better part of 2 days.

.....Oh, and any recommendations for code structure/organization is much appreciated. I've cobbled this together from all of the internet and the wiki. Again, thanks!

-Ryan

Edit: Forgot to mention that the problem(s) can be found in "zombie.lua". Heh.

[Zilarrezko]

Have you tried the love.physics API? It simplifies a lot of collisions and callbacks once you find your way around the system. I personally haven't messed with it, but it looks like it's a great thing to work with. (I'm not that great with looking through someone else's code and deciphering problems in optimization or little details. Mostly learned from videos and some practice here and there from basically every Lua source out there).

Other than that I can't do much, but everyone else can pretty much make their own operating system here and they're humble about it. For the most part, I'm commenting on this so it'll bump up and the omniscients will take over.

[Roland_Yonaba]

I'm commenting on this so it'll bump up and the omniscients will take over.

It worked indeed.
Well, The Great Robin is the only omniscient here.

What I'm trying to do is have every mob check with other mobs to see if they're colliding.

I took a quick peek at your code, and I can suggest a few things on the overall. But let us focus on the collision issue for now.
For such a problem, you normally won't need to use love.physics. Instead, you can boil down to problem to tinier pieces, as follows.

First of all, you want to detect if two entities (two zombies, here) are colliding. Each zombie is represented with a square. I'll assume that x,y refers to the top-left position of the entity sprite, and w,h refers to its width and height.

That said, you can use a simple utility function which checks if two AABBs (axis-aligned bounding boxes), meaning here "rectangles", are overlapping. It will take as input the two entities tables and perform the check. The following is just a rewrite of this sample on the wiki.

Code: Select all

function collides(entityA, entityB)
  return entityA.x < entityB.x + entityB.w
     and entityB.x < entityA.x + entityA.w
     and entityA.y < entityB.y + entityB.h
     and entityB.y < entityA.h + entityA.h
end

In case you need to deal with some extra space, it remains fairly simple to tweak the previous function to achieve that. You will just have to increase accordingly the with and height of the entities bounding boxes, and maybe shift to the left and to the top the x,y in case you want to "center" the bounding box inside the extra space.

Second, the collision check actually. Since you keep maintained a list of all the entities, you can perform this check very easily :

Code: Select all

for i, entityA in ipairs(listOfEntities) do
  for j, entityB in pairs(listOfEntities) do
    if entityA ~= entityB and collides(entityA, entityB) then
      -- stop moving for both entityA and entityB
      -- optionally, you can calculate their displacement vector and shift them appart so that they do not overlap
    end
  end
end

The above should work, but it has two flaws, mainly: it is not really efficient and not clever at all. Because of one simple thing: collision is commutative. Meaning that the statement "A collides with B" is strictly equivalent to "B collides with A". Therefore, you can notice that with the previous implementation, we are performing two times some checks.
To fix, this, we can proceed as follows:

Code: Select all

for i = 1, #listOfEntities-1 do
  for j = i+1, #listOfEntities do
    local entityA = listOfEntities[i]
    local entityB = listOfEntities[j]
    if collides(entityA, entityB) then
      -- stop moving for both entityA and entityB
      -- optionally, you can calculate their displacement vector and shift them appart so that they do not overlap
    end
  end
end

This reduces fairly well the number of collision checks and should be faster than the previous.

Hope this helps.

[micha]

A different approach would be to use soft constraints instead of hard ones.

A hard constraint means that you check if entities are colliding and if so, you stop their movement.

A soft constraint would mean that you apply a force that moves entities away from each other. Entities are then allowed to touch or even overlap, but if they do, they begin to resolve this by themselves. Such a crowd would be "squeezable". If many entities try to reach a point, then the crowd gets denser.

This approach is also used in pedestrian motion models. It is called "Social forces model". See for example this video. As you can see, the individual entities never touch, because they are aware of the positions of the other entities (besides following their individual target).

For Boids, this behavior is called "Separation".

[Roland_Yonaba]

A different approach would be to use soft constraints instead of hard ones.

I learnt something new. Indeed, I knew these expressions "hard/soft constraints", without knowing their proper meaning. Thanks.

[RyanImperion]

.....Thank you! I know that it seems very belated. but I just got over some really annoying computer-hardware issues. Just got up and running again to check my thread and stuff. Very in-depth answers, and it is very much appreciated!

-Ryan