How to handle collision detection when an entity movement speed is high?

Game Mechanics
#1

Hello.

So, basically, my collision detection code is something like this:


public Boolean canMove() {
  Position pos = positionEntityWannaMoveTo;

  for (WorldObject : All Objects In Map) {
    if (WorldObject.intersects(pos)) {
      return false;
    }
  }

  return true;
}

Ok, obviously, my code isn’t like this because it would use too much CPU considering the map has a high number of entities/tiles, but the “base” of the detection is something like that.

Suppose, my player is at Y 126.0, and his height is 32.0. So, his feet Y is 158.0, and there is a solid block at Y 159.0. So, if my player movement speed is 1.0, it will move correctly. But, what if the movement speed is 2.0, then the final move feet Y would be 160.0, being blocked by the block.

Then I tried to divide the movement speed in parts, so it would detect and move each 1.0 of movement speed. But, what if the movement speed is partial, like, 3.5? Then I should move each 0.5 of movement speed? And if it is 3.85?

So, there is a proper way to handle the movements with partial movement speed?

#2

Every movement update, you could make an imaginary line between the previous position and the new position. If it intersects with anything, then you are teleported back to the previous position.

Theoretical, of course.

#3

Be prepared to handle a collision before it happens, not when it just happened. Or you will end up with things colliding inside or weird teleporting effects

This as as simple as taking the current position + the speed of the character to get a new position, then check if that collides with anything.

If that makes sense.

#4

I think that is what he is doing, but the issue is, what if your speed is higher than the width of an object? Then that method of collision won’t work.

#5

The short answer is you do a collision check instead of a intersection test.

#6

I think I’ve explained it bad, so here I go again.

I AM checking for collision and not intersection. It’s something like:

  • player wants to move from 126,126 to 126,127
  • creates a new Box for that position { x = 126, y = 127, width = 32, height = 32 } (width and height are playerWidth and playerHeight, respectively).
  • check if this box collides with any object (entity/block/etc) on the map. if yes, the movement does not happen. if no, the movement goes normally.

BUT, the problem is: in the example above, the player moved +1 y (his movement speed is 1). but, what if his movement speed is 2?

So, here we go again:

  • player wants to move from 126,126 to 126,128
  • creates a new Box for that position { x = 126, y = 128, width = 32, height = 32 }
  • the new Box endX and endY are 158 and 160, respectively.
  • there is a block located at y = 160.
  • so, the player can’t move, since it would collide with the block. BUT, the player could have moved to y = 127 (endY = 159), with 1 movement speed.

So, moving the player with 1 movement speed is alright. The problem is when moving with higher and/or fractional movement speeds (like 2.5, 3.25, etc).

#7

You could do a line intersection test to see if the movement is possible

  1. Create a line from old coordinates to new coordinates
  2. Use a line intersection test with surrounding objects to see if they intersect
  3. If nothing intersects, move to new position
  4. If something intersects, then figure out the closest collision to the player and move the player there.
#8

Hey BloodShura,

this is a very classic problem of simulations, physics engine and the sort.
As an object moves at very high speeds doing collision checks gets more problematic, since in frame 1 it can be before and in frame 2 its behind an object.
Actually talked to my professor about this once; there should be documentation of how this problem is universally solved.

It all comes down to precision of collision detection. So if you wanna check those cases you have to basically, as the velocity increases do more collision checks each frame. Even though you are only rendering one frame you might have to check for a middle step or even quarter steps and so on

so traditionally you do:

for(each frame){
   object A has a speed
   check if when object A is moved one step, a collision will occur, if so react, if not proceed moving
}

(moving one step drawing it and so on…

but now you wanna have a loop, for lets say 4 time: speed / 4


for(each frame){
   for (4 times){
      check for impending collisions
      object.position+=speed/4
   }
}

4 is an arbitrary number here and it should be an higher number as your speed get higher, whatever makes sense

#9

To understand those suggestions better, I’d like to clarify that there are 2 common ways to do collision detection:

  • check IF a collision occured and then discard the movement; use a small interval as small as performance allows it (what Cero suggested)
  • check WHEN there was a collision in the previous timestep and adjust the position according to that exact moment (somewhat what Longarmx suggested)

The latter is called continuous or swept collision detection and gives more precise results without requiring that many iterations per tick. Here is an interesting article about swept collsion detection on AABBs.
That solves both your problem of not being able to entirely “touch” the wall at a high velocity and also the problem of clipping through thin obstacles.