tilemap vs decimal coordinates

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
touchdown51
Prole
Posts: 9
Joined: Sat May 19, 2018 4:51 am

tilemap vs decimal coordinates

Post by touchdown51 »

Hi there !
I'm trying to wrap my head around tilemap collision detection and response with love2d and I'm hitting a sort of conceptual roadblock. Here is what I mean by that.

Wrinting an 'AABB vs AABB' test when the AABB's have decimal world coordinates test is kind of easy :
function rectOverlap(pRect1X, pRect1Y, pRect1Width, pRect1Height, pRect2X, pRect2Y, pRect2Width, pRect2Height)
return pRect1X + pRect1Width > pRect2X
and pRect1X < pRect2X + pRect2Width
and pRect1Y + pRect1Height > pRect2Y
and pRect1Y < pRect2X + pRect2Height
end

In this model, rectangle have dimension-less edges (they can touch without colliding) so it works with decimal rectangle coordinates!

Tilemap, however, describe a discrete space when a point is inside a tile or another : you can't be on the edge between two tiles, colliding with no one.

So, how can you make a game when you are able to move in sub-pixel distances but detect and resolve collision with a tilemap in a sane manner ? I've tried all kind of hacks but can't seem to find a reasonable solution. I feel like the code is not the problem but the thinking : maybe I'm missing something important about the situation ! What is your understanding of the situation (allow decimal position objects with AABB vs tilemap) and do you know how pro devs usually approach it ? Not so much in code but the frame of mind, the way they see and deal with it, the bird view general intuition / conceptual understanding of what the situation implies.
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

Re: tilemap vs decimal coordinates

Post by ReFreezed »

Heh, I've thought about this many times but never came to any solid conclusion. Sometimes I treat tilemaps the same as AABBs and sometimes I don't. It may simply be something you have to choose depending on what you really need in each particular situation.

Comparing it to the real world... If you have two cubes made of some material, and the left side of one cube is "touching" the right side of the other cube. The two sides are not really sharing the exact same coordinate - there's always some space in-between them, even if we have to zoom in to the atomic level. Actually, the sides wouldn't be completely flat either; the surfaces would be more or less uneven and some atoms from one cube would most likely be slightly inside the very outer theoretical bounds of the other cube. If there was a way to measure the sizes of the cubes with infinite precision and the distance from the outmost atom on one side to the outmost atom on the other side turned out to be exactly 1 unit in each dimension for both cubes - when touching each other the resulting combined bounding box would most likely not be exactly 2 units long because of the space between the atoms and the likely overlap of the individual bounding boxes.

Let's try to mix in the tilemap concept into the soup then... If the exact center of one cube is located exactly on coordinate 0 on one axis and you tried to position the other cube exactly on coordinate 1 then you either a) wouldn't be able to, as the atoms in the cubes would push the other cube away, or b) you would be able to but then the cubes wouldn't touch, because no atoms on the (uneven) surface of one cube aligned and collided with any atoms of the other cube. So, depending on the exact shape of the surfaces, the cubes may or may not be able to be 1 unit away from each other without atoms occupying the exact same space.

Imagine one of the cubes as being part of the tilemap. Doesn't really make any difference physically - it's still collision between two uneven surfaces. Does it truly matter what "tile" the collision between atoms happens in?

Anyway, going back to the digital world, games don't really simulate physics down to the atomic level, right? So somewhere we have to round values to something appropriate for each situation. Because tilemaps don't exist in the real world; they are only an abstract idea, we just have to decide what happens at tile boundaries. Thus, no true answer. :o:

This was a lot of text. Is this making any sense? I may have to lay down for a moment...
Tools: Hot Particles, LuaPreprocess, InputField, (more) Games: Momento Temporis
"If each mistake being made is a new one, then progress is being made."
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: tilemap vs decimal coordinates

Post by ivan »

I have a feeling that you are overthinking the problem.
The simplest way to handle tilemap collisions, is to round the position to tilemap coords:

Code: Select all

tx,ty = math.floor(x/tileWidth), math.floor(y/tileHeight)
So you don't need to use AABB checks at all, just check if the tile coords are not blocked.
In terms of the animations, you can add "smooth" transition where objects would be interpolated between tiles.
So, how can you make a game when you are able to move in sub-pixel distances but detect and resolve collision with a tilemap in a sane manner ?
If you are making an action game, then you need a good collision system (preferably Box2D).
Rolling out your own collision system is possible but it's hard:
https://2dengine.com/?p=collisions
touchdown51
Prole
Posts: 9
Joined: Sat May 19, 2018 4:51 am

Re: tilemap vs decimal coordinates

Post by touchdown51 »

I know it's been a while now (got tor absorbed by my experiments), but thank you both for the time you took to reply! I enjoyed reading your post ReFreezed, so your wall of text was not typed in vain (hope your' laying down' worked and your brain stamina is back and kicking, aha). One thing I must have tell you is the context : action game in tilemap world. What I decided to do (perhaps could be useful for others ?) : let position representation and velocity calculation be decimal but use floored position to compute aabb sides coordinates that I use to test collision against tilemap. I also draw the object at the floored position of the object. Ivan, your website articles are very interesting ! Thanks for sharing, I bookmarked it! PS: looking at Momento Temporis and 8-bit Commando is very inspiring !
touchdown51
Prole
Posts: 9
Joined: Sat May 19, 2018 4:51 am

Re: tilemap vs decimal coordinates

Post by touchdown51 »

And Ivan, you got me intrigued by your "So you don't need to use AABB checks at all, just check if the tile coords are not blocked.
In terms of the animations, you can add "smooth" transition where objects would be interpolated between tiles. " Could you please elaborate on how you would write something like this (high level short pseudocode) ? edit: I mean, the "In terms of the animations, you can add "smooth" transition where objects would be interpolated between tiles"
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: tilemap vs decimal coordinates

Post by ivan »

Thanks, one generic example of this could be a chess game.
You have a 8x8 board and each piece has a position.
Positions on the chessboard are always integers like tilemap coordinates.
If you want to move a piece, you simply overwrite the position.
This would work for RPG games in the style of Ultima or even something similar to Pacman or Bomberman.
To make the movement between tiles smooth, you need a few extra variables:

Code: Select all

-- set target square/tile
function piece.moveTo(x,y)
  -- todo: check if blocked
  if board[x][y] ~= nil then
     return
  end
  -- update target
  piece.targX = x
  piece.targY = y
  piece.lerp = 0
end

-- update interpolation
function piece.update(dt)
  piece.lerp = piece.lerp + dt
  if piece.lerp >= timeToMove then
    -- arrived at new position
    piece.x = piece.targX
    piece.y = piece.targY
    piece.lerp = 0
  end
end

-- interpolate and draw
function piece.draw()
  -- interpolate from current to target position
  local a = piece.lerp/timeToMove
  local x = (piece.targX - piece.x)*a + piece.x
  local y = (piece.targY - piece.y)*a + piece.y
  -- draw piece
  love.graphics.draw(pieceImg, x*board.tileWidth, y*board.tileHeight)
end
Haven't tested this but it should hopefully illustrate my point.
The basic idea is that each piece has an integer positions like on a tilemap.
You only need to interpolate when drawing.
Post Reply

Who is online

Users browsing this forum: No registered users and 56 guests