[Solved] - Beginner - Collision detection with tiles

[Ximici]

Hi,

I want to make a RPG kind of game but I have no idea how I can make my player Not go through walls... I also want to know how I can make enemies that I can attack, but that is maybe something for later... For now I want to know the collision thing, please help.

Thanks in advance,

Ximici


PS: I don't want to use AdvTiledLoader or HardonCollider or something like that. I also attached code that I already made.
(yes, some parts of the code are from tutorials)

[vitaminx]

Hi,

Here you go, added collision detection between player and wooden boxes:

Code: Select all

function box_update(dt)

	if love.keyboard.isDown("a") then
        local _x=box.x - box.speed * dt
        if not box_checkCollision(_x,box.y) then box.x = _x end
	end 
	if love.keyboard.isDown("d") then
        local _x=box.x + box.speed * dt
        if not box_checkCollision(_x,box.y) then box.x = _x end
 	end 
 	if love.keyboard.isDown("w") then
        local _y=box.y - box.speed * dt
        if not box_checkCollision(box.x,_y) then box.y = _y end
 	end 
 	if love.keyboard.isDown("s") then
        local _y=box.y + box.speed * dt
        if not box_checkCollision(box.x,_y) then box.y = _y end
 	end
end

function box_checkCollision(x,y)
    local col=false

    for grid_y,v in ipairs(tiletable) do
        for grid_x,tile in ipairs(v) do
            if tile==3 and x+tileW>(grid_x-1)*tileW and y+tileH>(grid_y-1)*tileH and x<(grid_x-1)*tileW+tileW and y<(grid_y-1)*tileH+tileH then col=true end
        end
    end

    return col
end

The formula for the collision detection would translate to english more or less like that:

- search through the tiles in tiletable
- if we found the right tile (number 3) then check:
- if player x position plus his width is bigger than the tile's x position
- and if player x position is smaller than tile's x position plus it's width
- and if player y position plus his height is bigger than the tile's y position
- and if player y position is smaller than the tile's y position plus it's height
- then we have a collision and don't move there!


Greets,
vitaminx

[ivan]

This is a very common question on the forums.
Ok, so you wanna program your own collision system.
The classic way to handle collisions for action games (action RPGs in your case) is 2 steps.
I'll use (simplified) code examples from a lib that I worked on called FizzX.

1.Detection
detect if the moving sprite (player) is colliding with another object
- this is usually done by checking the moving sprite against every other object

Code: Select all

  for i = 1, #dynamics do
    local d = dynamics[i]
    moveShape(d, d.xv*dt, d.yv*dt)

    for j, s in ipairs(statics) do
      checkCollision(d, s)
    end
    for j = i + 1, #dynamics do
      checkCollision(d, dynamics[j])
    end

- the easiest approach is to use AABBs or axis aligned bounding boxes

Code: Select all

function testRectRect(a, b)
  -- distance between the shapes
  local dx, dy = a.x - b.x, a.y - b.y
  local adx = abs(dx)
  local ady = abs(dy)
  -- sum of the half-widths
  local shw, shh = a.hw + b.hw, a.hh + b.hh
  if adx > shw or ady > shh then
    return -- no collision
  end
  -- collision!

2.Response
translate the moving sprite so that it's no longer colliding with the other object
- if you find that a moving AABB is overlapping another AABB, you need to find the "separation vector" or how much you need to displace the moving AABB

Code: Select all

  -- continuation from "testRectRect"
  -- shortest separation
  local sx, sy = shw - adx, shh - ady
  if sx < sy then
    sy = 0
  else
    sx = 0
  end
  if dx < 0 then
    sx = -sx
  end
  if dy < 0 then
    sy = -sy
  end
  
  -- penertation depth
  local pen = sqrt(sx*sx + sy*sy)
  if pen > 0 then
    -- return penetration vector & depth
    return sx/pen, sy/pen, pen
  end
end

- after separating the two AABBs that you've checked you need to adjust their velocities. There's two variables that play a role here: friction (loss of velocity when 1 object slides over the edge of another) and bounce (elasticity).

Code: Select all

-- resolves collisions
function solveCollision(a, b, nx, ny, pen)
  -- object a is always dynamic and is always moving
  local vx, vy = a.xv - (b.xv or 0), a.yv - (b.yv or 0)
  local dp = vx*nx + vy*ny
  -- objects moving towards each other?
  if dp < 0 then
    -- project velocity onto collision normal
    local pnx, pny = nx*dp, ny*dp
    -- find tangent velocity
    local tx, ty = vx - pnx, vy - pny
    -- respond to the collision
    local r = 1 + a.bounce
    local f = a.friction
    local dvx = pnx*r + tx*f
    local dvy = pny*r + ty*f
    a.xv = a.xv - dvx
    a.yv = a.yv - dvy

    -- transfer force to the second object if it's dynamic
    if b.list == dynamics then
      local ar = atan2(vx, vy) - atan2(nx, ny)
      local force = cos(ar)
      b.xv = b.xv - dvx*force
      b.yv = b.yv - dvy*force
    end
  end
  -- separate
  if abs(nx) > 0 or abs(ny) > 0 then
    moveShape(a, nx*pen, ny*pen)
  end
end

[vitaminx]

Couldn't resist to add normalization for diagonal player movement to the game too

Code: Select all

[...]

box.speed = 100
box.speed_norm = 100/math.sqrt(2)

[...]

function box_update(dt)
    box.left=love.keyboard.isDown("a")
    box.right=love.keyboard.isDown("d")
    box.up=love.keyboard.isDown("w")
    box.down=love.keyboard.isDown("s")

    -- normalize diagonal movement
    if (box.left and box.up) or (box.left and box.down) or (box.right and box.up) or (box.right and box.down) then speed=box.speed_norm
    else speed=box.speed end

[...]

greets,
vitaminx

[Ximici]

Hi,

Thanks, vitaminx! You helped me a lot and most important of all, I understand your code! (It's a big thing for me that I understand a generic loop)
Also thank you, Ivan but your code seems a bit too complicated for me on the moment but I will sure look at it and try to understand, for now I will keep the more simple system from vitaminx. Now I understand how one can create something like that because I just couldn't figure it out!

Greets,

Ximici

[vitaminx]

The code I've posted may be easier to understand than ivan's solution.
But his is definitely better and it would be worth to try to understand it (I also have to dig a bit more into it .

Just consider a major drawback of my simple code:

If you have fast player movement or low FPS (or a combination of both) which result in a player movement of more than one pixels per update() then you might notice something strange:

The player seems to stop some pixels *before* the obstacle leaving a gap of some pixels between player and obstacle.

Consider this example:
Your frame rate is slow and the player moves quite fast, so it moves, lets say, 6 pixels per update().
The routine checks and sees, that the player moves towards an object which is in reality lets say 4 pixels away. Even though there should be no collision yet, the collision routine returns "true", thus preventing the player to move this 6 pixels.
This will result in a gap of 4 pixels between the player and the obstacle.

If your framerate is going up and down for some reason, you might also notice some unstable movement just before the obstacle, sometimes the player seems to advance a pixel more, sometimes a pixel less.

I could think of 2 solutions here: 1th the one ivan presented or 2nd this one which came to my mind:
Once a collision is detected you start a "repeat ... until" loop, which advances the player pixel per pixel towards the direction the player intented to go.
You test for a collision at each step and stop when the collision *really* happens.



There's a second drawback:
If the framerate is *really* low, let's say around 1 fps, then the routine could miss a collision and traverse an obstacle although it shouldn't.
I'm not sure if ivan's routine considers that, but I think in general this can only be prevented, if you use fixed time intervals between updates, not the plain dt delta time provided by the love.update() routine.

But you also might think that if your framerate is really *that* low, you wouldn't be able to play the game anyway



I've added some code to your program to implement the "repeat ... until" solution, there's a line in main.lua in love.update() which you can comment out to test it with low framerates:

Code: Select all

function box_update(dt)
    box.left=love.keyboard.isDown("a")
    box.right=love.keyboard.isDown("d")
    box.up=love.keyboard.isDown("w")
    box.down=love.keyboard.isDown("s")
 
    -- normalize diagonal movement
    if (box.left and box.up) or (box.left and box.down) or (box.right and box.up) or (box.right and box.down) then speed=box.speed_norm
    else speed=box.speed end
   
    if box.left then
        local _x=box.x - speed * dt
        while _x<box.x do
            if not box_checkCollision(box.x-1,box.y) then box.x = box.x-1
            else break end
        end
    end
    if box.right then
        local _x=box.x + speed * dt
        while _x>box.x do
            if not box_checkCollision(box.x+1,box.y) then box.x = box.x+1
            else break end
        end
    end
    if box.up then
        local _y=box.y - speed * dt
        while _y<box.y do
            if not box_checkCollision(box.x,box.y-1) then box.y = box.y-1
            else break end
        end
    end
    if box.down then
        local _y=box.y + speed * dt
        while _y>box.y do
            if not box_checkCollision(box.x,box.y+1) then box.y = box.y+1
            else break end
        end
    end
end

Greets,
vitaminx

[Ximici]

Yes, I noticed that bug. I find that problem a bit complicated but if I understand it right, you added a piece of code that keeps checking if that bug is occuring and if so, you fix it? I can't really get it, I' m new to programming, I try my best to understand.
The collision system of Ivan looks good, but still a little to complicated. If I look at his lib, I just can't follow ...
Thanks for the info, I' m learning a lot!

Greets,

Ximici