[library] bump.lua v3.1.4 - Collision Detection

[kikito]

Hi Sarcose,

You are asking several questions, let me try to answer each one.

Hey there, I have a noob question. How would I integrate this with, say, the Fine_Tile_Based_Scrolling tutorial?

The link you supplied seems to be dead, but the approach is always the same: In order to produce collisions with a tile-based map, the simplest way is:

Code: Select all

Assumptions:
* The width and height of your tiles are stored in TILE_WIDTH & TILE_HEIGHT.
* Your map has one (probably small) table per tile.
Steps:
1. Create a new bump world, as big as the map is (in pixels)
2. Go over each tile in the world with a loop, and for each tile:
  2.a If the tile is solid,
    2.a.1 Get the coordinates of the top-left corner of the tile in the world.
    2.a.2 Introduce the tile in the world with something like this:
        world:add(tile, top, left, TILE_WIDTH, TILE_HEIGHT)

3. Introduce the player in the world
4. Copy the player movement code from the simple demo. 

The player should collide with the solid blocks "by default", ignoring the non-solid ones. You can customize this and add more collisions types later.

The trickiest step is 2.a.1. You have to use TILE_WIDTH & TILE_HEIGHT to do this. The drawing code probably knows how to do this already.

I read about using world to query positions. Would it be possible to use world to draw the map directly? And how would that look?

This question has two parts. The first one is about queries. You can "query" a rectangular zone, a line or a dot. That will return a list with the items which collide with the rectangle, line or dot, respectively. The rectangular query can be used to only draw the stuff that is on the screen.

I am going to assume that you are using a camera system which implements scroll by using love.graphics.translate. If you are implementing the scroll in other ways (for example, modifying the coordinates of all the tiles 1 pixel up every time the scroll goes 1 pixel down), I recommend you to stop doing this: it makes things much more difficult to calculate. Your tiles location should not be changed just because you are moving - changing the "origin of coordinates from which we draw" is much simpler. All camera systems in the forums do this, no one modifies the tiles.

In order to query the rectangle like that, you need to give the world a rectangle representing "the screen coordinates": for example, you have moved the scroll 1000 points to the left and 500 points down, and your screen is 640 x 480, to get "everything on the screen" you could do something like this:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)

'items' is a list of game objects which you have inserted into the world: tiles, the player, projectiles, explosions, etc. 'len' is the length of that list (so you can parse it easily with a loop).

Then there is the matter of "how to draw those". That can mean two different things: "properly draw them" (with the images and stuff) or "draw debug information about them". Let's start with the later.

The bump world does not know a lot about the items it holds. It only knows their left-top corner, and their width and height. It knows that about everything you insert on it - the player, or the tiles. So you can draw "a rectangle for each item returned by world:queryRect" like this:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  local x,y,w,h = world:getRect(items[i])
  love.graphics.rectangle('line', x,y,w,h)
end

If you are using some kind of scroll, this code needs to be executed "while the camera is active" - after it does the first love.camera.translate. Otherwise the rectangles will not "move with the scroll".

But this will draw only rectangles. It is useful to "debug that your map is aligned with your world". If you want to "properly draw the map", you need more information which the world does not have. For example, you need to know that the grass tiles use this particular image or quad. Or that the player is on this animation frame. You can't do that with the world alone. This will depend on how your game entities (the tiles, the player) are coded. I usually like to make them objects, and give them a "draw" method, so each object knows how to draw itself. That way I can do just this:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  items[i]:draw()
end

This might be a bit too advanced for you, if you are not familiar with object-oriented programming. A more crude (but easier to understand) method for drawing everything would be this:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  local item = items[i]
  if item.is_grass_tile then
    draw_grass_tile(item)
  elseif item.is_wall_tile then
    draw_wall_tile(item)
  elseif item.is_player then
    draw_player(item)
  ...
  end
end

In this case, all your grass tiles need to have a boolean called is_grass_tile set to true, all your wall tiles need a is_wall_tile, etc. So instead of building each tile like this:

Code: Select all

local tile = {x=..., y=...}

you build it like this:

Code: Select all

local tile = {x=..., y=..., is_grass_tile=true} -- or is_wall_tile or is_player

[Sarcose]

That all actually makes a lot of sense. I guess I just needed someone to lay it out for me like that. Not sure why the link 404's for you (as it works for me, still), but it doesn't matter, because you understood my issue right away.

I'll let you know how this goes when I can work on implementing it. I'm pretty excited to put this together now. Thanks a ton!

[Sarcose]

Alright, I was able to make it work with the debug drawing method, but I can't figure out how you're referencing functions that aren't in the world item (like draw) with items. After adding it to the world, can I add more methods to the item? Pouring over your example code, I'm not sure how you get to methods like items:draw with world:queryRect(). Alternately, if I am trying to use the map table itself (with a draw function), I'm not sure how to reference methods in the map table using the items returned from world:queryRect().

Either way, thanks a bunch for the help. For now, drawing rectangles is all I need to get started on mechanics

[kikito]

I can't figure out how you're referencing functions that aren't in the world item (like draw) with items

We can start with the basics and then move on from there.

As I said before, the only thing bump knows are the rectangles you define for each item - and it also knows the item itself. In consequence, everything else you need to draw the item has to be provided by the item.

For example: if you add a 'color' attribute to all your entities & tiles, then you could draw them in different colors, like this:

Code: Select all

local player = {x=...,y=..., color = {255,0,0}}
...

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  local x,y,w,h = world:getRect(items[i])
  love.graphics.setColor(items[i].color)
  love.graphics.rectangle('line', x,y,w,h)
end

If you add an image to every object in the game, you could use it to draw, too. At this point you will probably not need to use getRect because you only need x and y and they are probably already in your item anyway:

Code: Select all

local playerImage = love.graphics.newImage(...)
local player = {x=...,y=..., image = playerImage}
...

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  local item = items[i]
  love.graphics.draw(item.image, item.x, item.y)
end

(using a quad + an image is very similar - you just add both to the item)

If all the entities in your game have a static image, you can probably stop here. But you could keep complicating this: drawing animations, special effects, sub-entities, particle effects, etc. The problem with that approach is that, the more "special treatment" each entity requires when drawing it, the more "spaggetty code" your "draw all visible items" function will become:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  local item = items[i]
  if item.subEntities then
    ...
  end
  it item.animation then
    ...
  end
  if item.particleEffect then
    ...
  end
end

This gets very difficult very quickly, if you have several ways of drawing stuff. The code for drawing the orks gets mixed up with the code which draws the player, the pickup items, the tiles, and even UI elements.

There are some ways to avoid this. One is simply using functions: instead of setting the image on every grass tile, you create a "drawGrassTile" function like this:

Code: Select all

local function drawGrassTile(item)
  love.graphics.draw(grassTileImage, item.x, item.y)
end

And you create your tiles with a draw function, pointing to their correct "drawing function":

Code: Select all

local tile = {x=...,y=..., draw = drawGrassTile}
...
local player = {x=...,y=..., draw = drawPlayer}

Now you can draw the items like I said at the beginning:

Code: Select all

local items, len = world:queryRect(1000, 500, 640, 480)
for i=1, len do
  items[i]:draw()
end

It is very clear what this function is doing now. The code of drawing ghosts is not mixed up with the code for drawing the tiles, or the player - they can be as complex as needed, with particles and effects and whatnot - but the concerns are not mixed up.

It is worth noting that you will face a similar problem when you have to update your items. It is possible that you want to update only the visible ones (or maybe the ones in a region around the camera). If you define update functions for each item, like this:

Code: Select all

local function updatePlayer(player, dt)
  ... do stuff with the keyboard & dt to change player.x and player.y
end

Then you can define your player like this:

Code: Select all

local player = {x=...,y=..., draw = drawPlayer, update = updatePlayer}

And then your update code will become:

Code: Select all

function love.update(dt)
  local items, len = world:queryRect(1000, 500, 640, 480)
  for i=1, len do
    items[i]:update(dt)
  end
end

There are several other things that you might want to do. If you end up creating bullets in several places (for example, both the player and the enemies fire them), it might make sense to write a createBullet(x,y) function instead of writing this:

Code: Select all

newBullet = {x=..., y=..., draw=drawBullet, update=updateBullet}

That way, if you ever need to add a new value change how bullets are created (for example, an "expiration time"), you can do it in a single place, instead of "hunting for bullet tables" in your code.

This combination of "dynamical dispatch of methods" and "creation functions" is basically what Object Orientation means. You can refine it with nicer syntax and lua metatables, but I don't think that's necessary in your case, at least for now.

[Sarcose]

Chiming in real quick just to say that your long post was super helpful, and I was able to get working what I needed to get working. I haven't dissected your whole post yet, but I realized that I was being very silly in not realizing that, in world:add(item,blah) where item is a table, and given lua's versatility with tables meaning tables can have functions, that would mean that I can declare a method for the table before adding it and then call it after the fact. For some reason, that was not clicking for me -- I was laboring under the assumption that I would have to world:add(item,x,y,w,h) and then somehow add methods to the item-already-passed, like world[x][y]:method().

Thanks a ton, kikito. Either this comes really easy to you or you decided to pour a ton of effort into helping me, and in either case I feel unworthy. I honestly am at a point where I am finally starting to get all of this, and bump.lua is probably the biggest reason.

[kikito]

I was laboring under the assumption that I would have to world:add(item,x,y,w,h) and then somehow add methods to the item-already-passed, like world[x][y]:method()

Heh. I am glad we cleared that one out. Once you get the hang of the basics, and you are capable of, say, iterating over a 2-dimensional table without breaking a sweat, consider giving a look at Lua's metatables.

Either this comes really easy to you or you decided to pour a ton of effort into helping me, and in either case I feel unworthy.

It is very easy for me to ignore a question when it seems that its author has not invested their own effort in answering it before asking it ("your lib doesn't work, here is my code, fix it for me"). Conversely, when it is clear that the person asking the question has made some effort, I am compelled to answer. Your case was the latter, so it was easy for me to find the time. Even slightly pleasant

[Sarcose]

Okay, I have another question. When I'm using filters and, say, I return 'bounce,' around where do I access col.bounce?

For instance:

Code: Select all

	
function player:updatePosition(dt)
	local px, py = self:resolveXInput(), self:resolveYInput()
	local ox, oy = self:resolveXOutside(), self:resolveYOutside()
	local goalX, goalY = self:resolveVelocities(dt,px,py,ox,oy)
	local actualX, actualY, cols, len = world:move(self, goalX, goalY, self.filter)
	self.x, self.y = actualX, actualY
end

Am I looking at something like:

Code: Select all

(inside updatePosition, after world:move)
	for i = 1, len do
		self:resolveCollisionType(cols[i])
	end

function player:resolveCollisionType(col)
	if col.type == 'bounce' then 
		self.response.xv = col.bounce.xv
		self.response.yv = col.bounce.yv
		self.response.updatestobounce = blah
	end
end

Then the "outside applied velocity" state system is in resolveXOutside(), resolveYOutside with things like bouncespeed * bouncevector as shown above, and these are evaluated against the input amounts in resolveVelocities.

At least, that's my general idea about how I need to do this.

I can see in how you write filter code that the collided-with thing is passed to the filter, then 'return 'bounce'' is what seems to give it col.bounce. Okay, so my confusion (as you can probably see) is where exactly I can access the vector after passing the collision response -- going from 'reflect the velocity to reach a bounced actualX, actualY' to 'use the reflected velocity to add more velocity-updates in a response state engine'.

edited a bit to fix some errors

[s-ol]

"col" refers to an entry in the "cols" table:

Code: Select all

ODE: SELECT ALL
(inside updatePosition, after world:move)
   for i = 1, len do
      -- use cols[i].bounce in calculations
      self:resolveCollisionType(cols[i])
   end

-- or use it in resolveCollisionType
function whatever:resolveCollisionType(col)
  -- use col.bounce
end

[Imaculata]

I'm interested in using this for my random dungeon game. I have however a simple question. In my game the player can sometimes move very fast. I have for example a dodge roll, where the player quickly covers a large distance of the screen (about 3 tiles in a split second). With my current collision detection, this can occasionally cause some problems, because the collision detection cannot keep up. So the player skips over a tile that he should collide with, and ends up stuck in a wall.

Does your library already take such issues into account? Does it scan ahead if objects are moving really fast?

[Nixola]

If I recall correctly, it doesn't; you should either do it yourself or check for collisions "in pieces", something like this:

Code: Select all

local d = math.abs(player.x -  player.newX)
while d > player.width do
  local  newX = player.x + player.width -- beware  of the sign
  d = d - player.width -- again, beware
  if collides then
    resolve() 
    break
  end
end
resolve -- again, because "d" might still be something, just one last time