Jasoco wrote:You need to check:

tile[floor(playerX / tileWidth)][floor(playerY / tileHeight)] == not solid

I'm already doing that in a way.

I think we're talking past each other, so I'm just going to post my collision code in full.

First of all, keep in mind that I'm using a fixed timestep, using a method described

here. So, I don't multiply anything by

*dt*.

My update function looks like this:

Code: Select all

```
local dx, dy = actor.getVelocity(player, currentButtons)
local time = collision.actorVSLevel(currentLevel, player, dx, dy)
actor.move(player, dx, dy, time)
```

First I get the player's velocity. Then I get a

*time* value where I check the player against the map. This value is between zero and one; one if the player is not going to collide with anything, zero if the player is already up against something. So,

*time* represents the moment in the current frame that the player collides with something. Note that the player has not actually moved yet. Movement only happens in the last function, which looks like this:

Code: Select all

```
function actor.move(act, dx, dy, time)
local time = time or 1.0
act.x = act.x + math.floor(dx * time)
act.y = act.y + math.floor(dy * time)
end
```

This is what checking the player against the map looks like. The idea is I find the time, a value between zero and one, that the earliest collision occurs. I return 1 if I don't find any collision.

Code: Select all

```
function collision.actorVSLevel(level, act, dx, dy, time)
local resultTime = time or 1.0
local radius = act.type.radius
local moveRect = collision.circleMoveRect(radius,
act.x, act.y, dx, dy)
local possibleTiles = levels.tilesInRect(level, moveRect)
local moveLine = {xi = act.x, yi = act.y,
xf = act.x + dx, yf = act.y + dy}
for _, tile in ipairs(possibleTiles) do
if levels.isWall(level, tile.x, tile.y) then
if dx < 0 then
-- Going west
local line = levels.lineSegmentEast(level,
tile.x, tile.y)
local normal = {x = 1, y = 0}
local firstCorner = levels.hasNorthEastCorner(level,
tile.x, tile.y)
local secondCorner = levels.hasSouthEastCorner(level,
tile.x, tile.y)
iTime = lineCollision(moveLine, line, radius,
normal, firstCorner, secondCorner)
if iTime and (iTime < resultTime) then
resultTime = iTime
end
elseif dx > 0 then
-- Going east
local line = levels.lineSegmentWest(level,
tile.x, tile.y)
local normal = {x = -1, y = 0}
local firstCorner = levels.hasNorthWestCorner(level,
tile.x, tile.y)
local secondCorner = levels.hasSouthWestCorner(level,
tile.x, tile.y)
iTime = lineCollision(moveLine, line, radius,
normal, firstCorner, secondCorner)
if iTime and (iTime < resultTime) then
resultTime = iTime
end
end
if dy < 0 then
-- Going north
local line = levels.lineSegmentSouth(level,
tile.x, tile.y)
local normal = {x = 0, y = 1}
local firstCorner = levels.hasSouthWestCorner(level,
tile.x, tile.y)
local secondCorner = levels.hasSouthEastCorner(level,
tile.x, tile.y)
iTime = lineCollision(moveLine, line, radius,
normal, firstCorner, secondCorner)
if iTime and (iTime < resultTime) then
resultTime = iTime
end
elseif dy > 0 then
-- Going south
local line = levels.lineSegmentNorth(level,
tile.x, tile.y)
local normal = {x = 0, y = -1}
local firstCorner = levels.hasNorthWestCorner(level,
tile.x, tile.y)
local secondCorner = levels.hasNorthEastCorner(level,
tile.x, tile.y)
iTime = lineCollision(moveLine, line, radius,
normal, firstCorner, secondCorner)
if iTime and (iTime < resultTime) then
resultTime = iTime
end
end
end
end
return resultTime
end
```

First thing I do is get the rectangle that encloses the player's movement, which looks like this:

- move_rect.png (18.01 KiB) Viewed 4694 times

Code: Select all

```
function collision.circleMoveRect(radius, x, y, dx, dy)
local width = (radius * 2) + math.abs(dx)
local height = (radius * 2) + math.abs(dy)
local rx = x - radius
if dx < 0 then
rx = rx + dx
end
local ry = y - radius
if dy < 0 then
ry = ry + dy
end
-- return {x = x or 0, y = y or 0,
-- width = width or 0, height = height or 0}
return utility.rectangle(rx, ry, width, height)
end
```

Then I get the tiles covered by the movement rectangle:

Code: Select all

```
function levels.tilesInRect(level, rect)
local minX = levels.tileX(level, rect.x)
local minY = levels.tileY(level, rect.y)
local maxX = levels.tileX(level, rect.x + rect.width)
local maxY = levels.tileY(level, rect.y + rect.height)
if minX < 0 then
minX = 0
end
if minY < 0 then
minY = 0
end
if maxX >= level.width then
maxX = level.width - 1
end
if maxY >= level.height then
maxY = level.height - 1
end
local result = {}
for x = minX, maxX do
for y = minY, maxY do
table.insert(result, {x = x, y = y})
end
end
return result
end
```

Now that I have all the tiles the player will cross, I loop through them and find any wall tiles. When i find a wall tile, I figure out which sides the play may hit. So, if the player is moving east, I get a line segment representing the wall's west side.

Code: Select all

```
function levels.lineSegmentNorth(level, x, y)
-- Goes west to east
local xi = x * TILE_SIZE
local yi = y * TILE_SIZE
local xf = xi + TILE_SIZE
local yf = yi
return {xi = xi, yi = yi, xf = xf, yf = yf}
end
function levels.lineSegmentSouth(level, x, y)
-- Goes west to east
local xi = x * TILE_SIZE
local yi = (y * TILE_SIZE) + TILE_SIZE
local xf = xi + TILE_SIZE
local yf = yi
return {xi = xi, yi = yi, xf = xf, yf = yf}
end
function levels.lineSegmentEast(level, x, y)
-- Goes north to south
local xi = (x * TILE_SIZE) + TILE_SIZE
local yi = y * TILE_SIZE
local xf = xi
local yf = yi + TILE_SIZE
return {xi = xi, yi = yi, xf = xf, yf = yf}
end
function levels.lineSegmentWest(level, x, y)
-- Goes north to south
local xi = x * TILE_SIZE
local yi = y * TILE_SIZE
local xf = xi
local yf = yi + TILE_SIZE
return {xi = xi, yi = yi, xf = xf, yf = yf}
end
```

I also check whether or not the wall tile has any corners facing the player. That is, I don't check the player against the wall tile's corners if the wall tile is part of a larger wall.

Code: Select all

```
function levels.hasNorthEastCorner(level, x, y)
return not ( levels.isWall(level, x, y - 1)
or levels.isWall(level, x + 1, y) )
end
function levels.hasSouthEastCorner(level, x, y)
return not ( levels.isWall(level, x, y + 1)
or levels.isWall(level, x + 1, y) )
end
function levels.hasNorthWestCorner(level, x, y)
return not ( levels.isWall(level, x, y - 1)
or levels.isWall(level, x - 1, y) )
end
function levels.hasSouthWestCorner(level, x, y)
return not ( levels.isWall(level, x, y + 1)
or levels.isWall(level, x - 1, y) )
end
```

I finally check the player against a line segment representing a wall side.

Code: Select all

```
local function lineCollision(a, b, radius, bNormal, bHasFirstPoint,
bHasSecondPoint)
local result = nil
local aDX = a.xf - a.xi
local aDY = a.yf - a.yi
local bDX = b.xf - b.xi
local bDY = b.yf - b.yi
local denom = (bDY * aDX) - (bDX * aDY)
-- Shift wall towards circle
local rx = radius * bNormal.x
local ry = radius * bNormal.y
local crossX = a.xi - b.xi - rx
local crossY = a.yi - b.yi - ry
local intersectA = ((bDX * crossY) - (bDY * crossX)) / denom
local intersectB = ((aDX * crossY) - (aDY * crossX)) / denom
if (intersectA >= 0) then
-- Circle will cross plane of wall
if (intersectA <= 1)
and (intersectB >= 0) and (intersectB <= 1) then
-- Circle hitting wall itself
result = intersectA
else
-- Test against wall's end points
if bHasFirstPoint and (intersectB < 0) then
-- Test against first point
result = pointCollision(a, b.xi, b.yi, radius)
elseif bHasSecondPoint and (intersectB > 1) then
-- Test against second point
result = pointCollision(a, b.xf, b.yf,
radius)
end
end
end
return result
end
```

The first part is a standard line intersection test, based on

this geometry article. Since the wall line is always horizontal or vertical, I just have to shift it towards the player by the player's radius.

*intersectA* corresponds to when the (infinitely extended) movement line will intersect the (infinitely extended) wall line. If it's between 0 and 1, the intersection will happen during this frame. If it's less than 0, the wall only intersects with the movement line extended

*backwards* from the movement line segment, corresponding to sometime in the past. If

*intersectA* is greater than 1, the two lines will intersect but only in the future.

*intersectA* is treated like a time value.

When the two lines are not intersecting is when I try to test against the corners, and this is the part I'm struggling with. I'll post my function for testing against a corner point again.

Code: Select all

```
local function pointCollision(line, px, py, radius)
local result
local dx = line.xf - line.xi
local dy = line.yf - line.yi
local moveLenSq = (dx * dx) + (dy * dy)
-- Center of circle to point
-- I'm just going to call this vector "v"
local vx = px - line.xi
local vy = py - line.yi
local moveLen = math.sqrt(moveLenSq)
local ndx = dx / moveLen
local ndy = dy / moveLen
-- Dot product between v and normal of movement vector.
-- This is equal to the length of the projection vector of
-- v onto the movement vector
local dotprod = (vx * ndx) + (vy * ndy)
assert(dotprod > 0) -- Circle should already be moving towards
-- corner, since it's moving towards the
-- corner's line
-- Closest distance circle will ever get to point
local vLenSq = (vx * vx) + (vy * vy)
local closestDistSq = vLenSq - (dotprod * dotprod)
if closestDistSq < (radius * radius) then
local moveOffsetSq = (radius * radius) - closestDistSq
local realMoveLen = dotprod - math.sqrt(moveOffsetSq)
if realMoveLen < moveLen then
result = realMoveLen / moveLen
end
end
return result
end
```

And the article I got my algorithm from:

http://www.gamasutra.com/view/feature/3 ... php?page=2
I am ambitious about my collision detection you can tell.