LoginLogin
Nintendo shutting down 3DS + Wii U online services, see our post

Methods for dealing with varied types of collision?

Root / Programming Questions / [.]

MZ952Created:
This is not so much a question as it is a request to hear other's methods for the collision engines they used for their games or programs. I am designing (and desperately rounding) a collision engine designed for floating-point collision between a point and square tiles. I've got all the bugs worked out except for one where the point is able to pass through the contact of two adjacent tiles' vertices. I'm looking to redesign the engine to use integer type because I suspect the certain type of collision I want to use may work just as well, and work around this bug. Having said that, I've looked around at code written by others, and I've done a little research into collision, and I think it would be helpful for me, and newcomers alike who are attempting to build collision in their games and programs for the first time, if we (SBS) had a focused, a coherent (for those without programming vernacular), and a detailed forum post which could be referenced, and which details those various methods other programmers have utilized for managing collision, and perhaps the physics engines and those other relating aspects.

A common way I've used is to store two variables for each of the position components (X, & Y). One old, the other, new. So that one of the X variables stores the old X position, and the other variable stores the current position, and likewise for the Y coordinates. If a collision on the tile at the current X & Y coordinates is detected, then it will restore the current X & Y coordinates to the old ones, and either negate or reverse the X & Y velocities, to either stop the movement or to simulate a deflection effect. That method I used is rather rudimentary. I currently employ better version of it, where if the distance between the old position and the new position is greater than the tile size, it performs a linear check of all the tiles in between by finding the slope of the player's path and recursively checking each of the tiles along that slope.
'Where S is the tile size (each tile is square)
'Where X0 is the old coordinate, and X1 the new ... Likewise for Y0 & Y1.
'// If the distance travelled was greater across the X-axis ...
XD = (X0 DIV S) - (X1 DIV S)
YD = (Y0 DIV S) - (Y1 DIV S)
FOR I = 0 TO XD STEP SGN(XD)
 IF COLCHK( I , (I DIV ABS(XD))*SGN(YD) ) THEN 'Enact collision
NEXT I
'// If the distance was greater on the Y-axis, do the same except using Y-coordinates instead 
DEF COLCHK( X , Y )
 'Define collision
END
It is worth noting that you ought to check the collision at the points along the slope PLUS the displacement of the player, since XD & YD are simply distance, not coordinates, and do not account for the offset of the player within your game world. Since the code will not store the old X & Y coordinate values if they belong inside a colliding tile, it shouldn't be possible for both variables to be at fault, and cause the player to be stuck within a tile.

The best way I know of is to do multiple checks. For example, if the player's velocity is 17, you'd check for collision at their position +1, +2, +3, etc. until +17. If you find collision at any time, exit the loop and move the player to the last position where there was no collision. That way, you won't stop before you hit a wall if you are moving fast, or go through a wall if you're moving REALLY fast. For example:
ANGLE=ATAN(VY,VX)
SPEED=SQR(VX*VX+VY*VY)
FOR I=0 TO SPEED STEP 1/QUALITY
 IF CHKCOL(X+VX*(I/SPEED),Y+VY*(I/SPEED)) THEN BREAK
NEXT
INC X,VX*(I/SPEED)
INC Y,VY*(I/SPEED)
QUALITY should be higher than the number of pixels per whatever unit you use for location (for example, if adding 1 to X or Y makes the player move 16 pixels, QUALITY should be 16 or more)