This is a little different than simply checking if a tile is occupied on a grid map. Using a fixed grid size, that is one in which every tile is of equal size with equal spacing, we check for collision with the tiles by checking the horizontal and vertical lines of the grid.
Create a line segment to represent movement from point A to B. Line CD represents the vertical and horizontal lines. By knowing the size of the grid tiles which are evenly spaced, we can narrow down the number of line intersections that need checked. For instance, a line moving downwards which starts at y-coord 150px, there's no need to check horizontal lines below the 150px mark.
Next step, check for intersection between AB and CD. For vertical lines, we're checking for collision along the X-axis. When we hit a line, find the intersection point then extrapolate which tile that is. Similarly, do the same for horizontal lines along the Y-axis.
Why not simply divide the destination point by the tile size of the map to determine the collision tile? For several reasons.
1. In a fast-paced game, it would be possible to skip over tiles that you should have collided with if your velocity is greater than the size of a tile.
2. This method allows you to determine what side of a tile you hit.
3. Paves the way for more advanced collision response.
4. Consider an RTS game moving a unit from A to B. This can quickly tell you if the path is clear or not without the need for A*
Granted this method may not be as fast check for the current tile underneath a specific point, but it's much more powerful in terms of flexibility.
What does this demo do? Aside from the steps I discussed above, move the mouse around which will form the AB line segment. It will then color any box on the map that is occupied with green. A yellow box will mark the earliest collision.
REM ========================================================
REM Project: Grid-based collision using sweep intersection
REM Created: Tuesday, February 12, 2013
REM Author: Phaelax
REM ========================================================
set display mode 1024, 768, 32
Type Vector2D
x as float
y as float
EndType
dim map(16, 20)
rem make a random map
for x = 0 to 15
for y = 0 to 19
if rnd(1) = 1 then map(x, y) = 1
next y
next x
A as Vector2D
B as Vector2D
C as Vector2D
D as Vector2D
sync on
sync rate 60
do
cls
rem draw map data
ink rgb(192,192,192),0
for x = 0 to 15
for y = 0 to 19
if map(x, y) = 1 then box x*64+1, y*32+1, x*64+64, y*32+32
next y
next x
rem draw grid
ink rgb(255,255,255),0
for x = 1 to 16
line x*64, 1, x*64, 640
next x
for y = 1 to 20
line 1, y*32, 1024, y*32
next y
rem Line representing a velocity, line of sight, or whatever.
rem I'll refer to line [A,B] as the view line.
A.x = 500
A.y = 200
B.x = mousex()
B.y = mousey()
rem Limit number of line checks.
rem Only check the horizontal/vertical
rem lines that are within range.
sX = A.x / 64
fX = B.x / 64
sY = A.y / 32
fY = B.y / 32
rem order the limits
tX = min(sX, fX)
fX = max(sX, fX)
sX = tX
tY = min(sY, fY)
fY = max(sY, fY)
sY = tY
rem So we don't check outside the map area
rem No need to constrain X values because
rem the map extends the width of the screen
rem and the mouse can't go beyond it.
if fY > 19 then fY = 19
if sY > 19 then sY = 19
nearestX = -1
nearestY = -1
nearestT# = 2
rem collision boxes shown in green
ink rgb(0,255,0),0
rem check vertical lines
for x = sX to fX
rem define vertical line [C,D]
C.x = x*64 : C.y = 1
D.x = x*64 : D.y = 640
rem Get intersection time of view line to the vertical
tb# = timeIntersection(A, B, C, D)
rem When dealing with line segments, make sure intersection time is between 0 and 1.
if inRange(tb#, 0, 1)
rem Get intersection time of vertical line to the view line
tl# = timeIntersection(C, D, A, B)
rem Check intersection is within segment endpoints
if inRange(tl#, 0, 1)
rem Calculate intersection point.
rem The reason for using INT then CEIL in this manner is
rem to sort out a floating point precision issue with DB.
rem When '6' is assigned to a float, it could appear as '5.99'
rem which can cause the wrong tile to show up as being intersected
x# = int(A.x + (B.x - A.x)*tb#)
y# = A.y + (B.y - A.y)*tb#
tx = ceil(x# / 64)
ty = y# / 32
rem if ball is travelling from the right
rem we can't hit the left side of a brick.
rem So if there's a vertical line intersection
rem it must be the right side. This ensures
rem proper translation for the map indices.
rem Each box in the grid shares a border with another.
rem To determine if we're hitting the left side of a box
rem or the right side of a box next to it, we check which
rem direction the collision point is in relation to the
rem start of the view line.
if x# < A.x then dec tx
rem A final range check so we don't accidently go out of array bounds
if inRange(tx, 0, 15) and inRange(ty, 0, 19)
rem draw a box to show collision if map tile contains a block
if map(tx, ty) = 1
box tx*64+1, ty*32+1, tx*64+64, ty*32+32
rem For determining the closest collision
if tb# < nearestT#
nearestT# = tb#
nearestX = tx
nearestY = ty
endif
endif
endif
endif
endif
next x
rem check horizontal lines
for y = sY to fY
rem define horizontal line [C,D]
C.x = 1 : C.y = y*32
D.x = 1024 : D.y = y*32
rem Get intersection time of view line to the horizontal
tb# = timeIntersection(A, B, C, D)
rem When dealing with line segments, make sure intersection time is between 0 and 1.
if inRange(tb#, 0, 1)
rem Get intersection time of horizontal line to the view line
rem For this demo, you could ignore this check since the horizontal lines
rem reach both ends of the screen and therefore appear infinite anyway.
tl# = timeIntersection(C, D, A, B)
rem Check intersection is within segment endpoints
if inRange(tl#, 0, 1)
rem Calculate intersection point
x# = A.x + (B.x - A.x)*tb#
y# = int(A.y + (B.y - A.y)*tb#)
tx = x# / 64
ty = ceil(y# / 32)
rem Each box in the grid shares a border with another.
rem To determine if we're hitting the top of a box
rem or the bottom of a box, we check which direction
rem the collision point is in relation to the start
rem of the view line.
if y# < A.y then dec ty
rem A final range check so we don't accidently go out of array bounds
if inRange(tx, 0, 15) and inRange(ty, 0, 19)
rem draw a box to show collision if map tile contains a block
if map(tx, ty) = 1
box tx*64+1, ty*32+1, (tx+1)*64, (ty+1)*32
rem For determining the closest collision
if tb# < nearestT#
nearestT# = tb#
nearestX = tx
nearestY = ty
endif
endif
endif
endif
endif
next y
ink rgb(255,255,0),0
if nearestX > -1 and nearestY > -1
box nearestX*64, nearestY*32, nearestX*64+64, nearestY*32+32
endif
rem show view line
ink rgb(0,0,255),0
line A.x, A.y, B.x, B.y
sync
loop
rem verifies a number is within the specified range
function inRange(n as float, low as float, high as float)
if n >= low and n <= high then exitfunction 1
endfunction 0
rem Returns time value along line AB for intersection with line CD
function timeIntersection(A as vector2D, B as vector2D, C as vector2D, D as vector2D)
n# = ((D.x-C.x) * (A.y-C.y)) - ((D.y-C.y) * (A.x-C.x))
d# = ((D.y-C.y) * (B.x-A.x)) - ((D.x-C.x) * (B.y-A.y))
t# = n# / d#
endfunction t#
After typing this entire page, I accidently closed the tab! I clicked on recently closed to bring this page back up (after yelling much profanity) and to my amazement, Chrome still had everything I typed in it! Chrome just redeemed itself in my eyes!
"You're not going crazy. You're going sane in a crazy world!" ~Tick