Home

Awesome

bump-3dpd

Build Status Coverage Status Lua Versions

bump-3dpd is a Lua three-dimensional collision-detection library for axis-aligned cubes. It is based off of kikito's bump.lua library. Its main features are:

The demos are LÖVE based, but this library can be used in any Lua-compatible environment.

bump-3dpd is ideal for:

bump-3dpd is not a good match for:

Example


local bump = require 'bump-3dpd'

-- The grid cell size can be specified via the initialize method
-- By default, the cell size is 64
local world = bump.newWorld(50)

-- create two cubes
local A = {name="A"}
local B = {name="B"}

-- insert both cubes into bump
world:add(A, 0,    0, 0, 64, 256, 64) -- x, y, z, width, height, depth
world:add(B, 0, -100, 0, 32,  32, 32)

-- Try to move B to 0,64,0. If it collides with A, "slide over it"
local actualX, actualY, cols, len = world:move(B, 0, 64, 0)

-- prints "Attempted to move to 0,64,0 but ended up in 0,-32,0 due to 1 collisions"
if len > 0 then
  print(("Attempted to move to 0,64,0 but ended up in %d,%d,%d due to %d collisions"):format(actualX, actualY, actualZ, len))
else
  print("Moved B to 0, 64, 0 without collisions")
end

-- prints the new coordinates of B: 0, -32, 0, 32, 32, 32
print(world:getCube(B))

-- prints "Collision with A"
for i = 1, len do -- If more than one simultaneous collision, they are sorted out by proximity
  local col = cols[i]
  print(("Collision with %s."):format(col.other.name))
end

-- remove A and B from the world
world:remove(A)
world:remove(B)

Demo

There is a demo showing movement, collision detection, basic slide-based resolution, and z-sorting in main.lua. You will need LÖVE in order to try it.

demo

Basic API - Adding, removing and moving items

Requiring the library

local bump = require 'bump-3dpd'

The following methods (bump.newWorld, world:add, world:remove, world:update, world:move & world:check) are basic for working with bump-3dpd, as well as the 4 collision responses. If you want to use bump-3dpd effectively, you will need to understand at least these.

Creating a world

local world = bump.newWorld(cellSize)

The first thing to do with bump-3dpd is creating a world. That is done with bump.newWorld.

Don't worry too much about cellSize at the beginning, you can tweak it later on to see if bigger/smaller numbers give you better results (you can't change the value of cellSize in runtime, but you can create as many worlds as you want, each one with a different cellsize, if the need arises.)

The rest of the methods we have are for the worlds that we create.

Adding items to the world

world:add(item, x, y, z, w, h, d)

world:add is what you need to insert a new item in a world. "Items" are "anything that matters to your collision". It can be the player character, a tile, a missile etc. In fact, you can insert items that don't participate in the collision at all - like puffs of smoke or background tiles. This can be handy if you want to use the bump-3dpd world as a spatial database in addition to a collision detector (see the "queries section" below for mode details).

Each item will have an associated "cube" in the world.

world:add returns no values. It generates no collisions - you can call world:check(item) if you want to get the collisions it creates right after it's added.

If you try to add an item to a world that already contains it, you will get an error.

Removing items from the world

world:remove(item)

bump-3dpd stores hard references to any items that you add (with world:add). If you decide that a item is no longer necessary, in addition to removing it from your "entity list", you must also remove it from the world using world:remove. Otherwise it will still be there, and other objects might still collide with it.

Once removed from the world, the item will stop existing in that world. It won't trigger any collisions with other objects any more. Attempting to move it with world:move or checking collisions with world:check will raise an error.

It is ok to remove an object from the world and later add it again. In fact, some bump-3dpd methods do this internally.

This method returns nothing.

Changing the position and dimensions of items in the world

world:update(item, x, y, z, <w>, <h>, <d>)

Even if your "player" has attributes like player.x, player.y, and player.z, changing those will not automatically change them inside world. update is one of the ways to do so: it changes the cube representing item inside world.

This method always changes the cube associated to item, ignoring all collisions (use world:move for that). It returns nothing.

You may use world:update if you want to "teleport" your items around. A lot of time, however, you want to move them taking collisions into account. In order to do that, you have world:move.

Moving an item in the world, with collision resolution

local actualX, actualY, actualZ, cols, len = world:move(item, goalX, goalY, goalZ, <filter>)

This is probably the most useful method of bump-3dpd. It moves the item inside the world towards a desired position, but taking collisions into account.

The usual way you would use move is: calculate a "desirable" goalX, goalY, goalZ point for an item (maybe using its velocity), pass it to move, and then use actualX, actualY, actualZ as the real "updates" - . For example, here's how a player would move:

function player:move(dt)
  local goalX = self.x + self.xVelocity * dt
  local goalY = self.y + self.yVelocity * dt
  local goalZ = self.z + self.zVelocity * dt
  local actualX, actualY, actualZ, cols, len = world:move(self, goalX, goalY, goalZ)
  self.x, self.y, self.z = actualX, actualY, actualZ
  -- deal with the collisions
  for i = 1, len do
    print('collided with ' .. tostring(cols[i].other))
  end
end

Notice that if filter returns nil or false, it is guaranteed that other will not produce a collision. But the opposite is not true: it is possible that filter returns "slide", and yet no collision is produced. This is because filter is applied to all the neighbors of item, that is, all the items that "touch" the same cells as item. Some of them might be on the same cells, but still not collide with item..

Collision Resolution

For each of the collisions returned by world:move, the most interesting attribute is cols[i].other. Often it's enough with it - for example if item is one of those bullets that disappear when impacting the player you must make the bullet disappear (and decrease the player's health).

world:move() returns a list (instead of a single collision element) because in some cases you might want to "skip" some collisions, or react to several of them in a single frame.

For example, imagine a player which collides on the same frame with a coin first, an enemy fireball, and the floor.

The first two can be handled just by using col.other, but "aligning the player with the ground" requires collision resolution.

bump-3dpd comes with 4 built-in ways to handle collisions: touch, cross, slide & bounce. You can select which one is used on each collision by returning their name in the filter param of world:move or world:check. You can also choose to ignore a collision by returning nil or false.

touch

This is the type of collision for things like arrows or bullets; things that "gets stuck" on their targets.

Collisions of this type have their type attribute set to "touch" and don't have any additional information apart from the the default one, shared by all collisions (see below).

cross

This type of collision is for cases where you want to detect a collision but you don't want any response. It is useful for things like: detecting that the player has entered a new area, or consumables (i.e. coins) which usually don't affect the player's trajectory, but it's still useful to know then they are collided with.

Collisions of this type have their type attribute set to "cross" and don't have any additional information apart from the the default one, shared by all collisions (see below).

slide

This is the default collision type used in bump-3dpd. It's what you want to use for solid objects which "slide over other objects", like Super Mario does over a platform or the ground.

Collisions of this type have their type attribute set to "slide". They also have a special attribute called col.slide, which is a 3d vector with three components: col.slide.x, col.slide.y, & col.slide.z. It represents the x, y, and z coordinates to which the item "attempted to slide to". They are different from actualX, actualY, & actualZ since other collisions later on can modify them.

bounce

A good example of this behavior is Arkanoid's ball; you can use this type of collision for things that "move away" after touching others.

Collisions of this type have their type attribute set to "bounce". They also have a special attributes called col.bounce. It is a 3d vector which represents the x, y, and z coordinates to which the item "attempted to bounce".

Here's an example of a filter displaying all these behaviors:

local playerFilter = function(item, other)
  if     other.isCoin   then return 'cross'
  elseif other.isWall   then return 'slide'
  elseif other.isExit   then return 'touch'
  elseif other.isSpring then return 'bounce'
  end
  -- else return nil
end

The code above will make a character work more or less like super-mario, collision-wise. It'll go though coins, collide with walls, bounce over springs, etc, ignoring things it should not collide with like clouds in the background.

You could then use the collisions returned like so:

function player:move(dt)
  local goalX = self.x + self.xVelocity * dt
  local goalY = self.y + self.yVelocity * dt
  local goalZ = self.z + self.zVelocity * dt
  local actualX, actualY, actualZ, cols, len = world:move(self, goalX, goalY, goalZ, playerFilter)
  self.x, self.y, self.z = actualX, actualY, actualZ
  for i = 1, len do
    local other = cols[i].other
    if other.isCoin then
      takeCoin(other)
    elseif other.isExit then
      changeLevel()
    elseif other.isSpring then
      self:highJump()
    end
  end
end

Checking for collisions without moving

local actualX, actualY, actualZ, cols, len = world:check(item, goalX, goalY, goalZ, <filter>)

It returns the position where item would end up, and the collisions it would encounter, should it attempt to move to goalX, goalY, goalZ with the specified filter.

Notice that check has the same parameters and return values as move. The difference is that the former does not update the position of item in the world - you would have to call world:update in order to do that. In fact, world:move is implemented by calling world:check first, and then world:update immediately after.

The equivalent code to the previous example using check would be:

function player:move(dt)
  local goalX = self.x + self.xVelocity * dt
  local goalY = self.y + self.yVelocity * dt
  local goalZ = self.z + self.zVelocity * dt
  local actualX, actualY, actualZ, cols, len = world:check(self, goalX, goalY, goalZ, playerFilter)
  world:update(self, actualX, actualY, actualZ) -- update the player's cube in the world
  self.x, self.y, self.z = actualX, actualY, actualZ
  -- ... <deal with the collisions as before>
end

world:check is useful for things like "planing in advance" or "studying alternatives", when moving is still not fully decided.

Collision info

Here's the info contained on every collision item contained in the cols variables mentioned above:

cols[i] = {
  item  = the item being moved / checked
  other = an item colliding with the item being moved
  type  = the result of `filter(other)`. It's usually "touch", "cross", "slide" or "bounce"
  overlaps  = boolean. True if item "was overlapping" other when the collision started.
              False if it didn't but "tunneled" through other
  ti        = Number between 0 and 1. How far along the movement to the goal did the collision occur
  move      = Vector({x=number,y=number,z=number}). The difference between the original
              coordinates and the actual ones.
  normal    = Vector({x=number,y=number,z=number}). The collision normal; usually -1, 0, or 1
              in x, y, and z.
  touch     = Vector({x=number,y=number,z=number}). The coordinates where item started touching other
  itemCube  = The cube item occupied when the touch happened({x=N, y=N, z=N, w=N, h=N, d=N})
  otherCube = The cube other occupied when the touch happened({x=N, y=N, z=N, w=N, h=N, d=N})
}

Note that collisions of type slide and bounce have some additional fields. They are described on each response's section above.

Most of this info is useful only if you are doing semi-advanced stuff with collisions, but they could have some uses.

For example, cols[i].normal could be used to "detect if a player is on ground or not". cols[i].touch could be used to "spawn a puff of dust when a player touches ground after a fall", and so on.

Intermediate API - Querying the world

The following methods are required for basic usage of bump-3dpd, but are quite handy, and you would be missing out some nice features of this lib if you were not using it.

Sometimes it is desirable to know "which items are in a certain area". This is called "querying the world".

Bump-3dpd allows querying the world via a point, a cubic zone, and a straight line segment.

This makes it useful not only as a collision detection library, but also as a lightweight spatial dictionary. In particular, you can use bump-3dpd to "only draw the things that are needed" on the screen. In order to do this, you would have to add all your "visible" objects into bump-3dpd, even if they don't collide with anything (this is usually ok, just ignore them with your filters when you do the collisions).

Querying with a point

local items, len = world:queryPoint(x, y, z, filter)

Returns the items that touch a given point.

It is useful for things like clicking with the mouse and getting the items affected.

Querying with a cube

local items, len = world:queryCube(x, y, z, w, h, d, filter)

Returns the items that touch a given cube.

Useful for things like selecting what to display on the screen, as mentioned above, or selecting a group of units with the mouse in a strategy game.

Querying with a segment

local items, len = world:querySegment(x1, y1, z1, x2, y2, z2, filter)

Returns the items that touch a segment.

It's useful for things like line-of-sight or modelling bullets or lasers.

Querying with a segment (with more detailed info)

local itemInfo, len = world:querySegmentWithCoords(x1, y1, z1, x2, y2, z2, filter)

An extended version of world:querySegment which returns the collision points of the segment with the items, in addition to the items.

It is useful if you need to actually show the lasers/bullets or if you need to show some impact effects (i.e. spawning some particles where a bullet hits a wall). If you don't need the actual points of contact between the segment and the bounding cubes, use world:querySegment, since it's faster.

Most people will only need info.item, info.x1, info.y1, info.y1, and info.z2. However, info.x2, info.y2, and info.z2 are useful if you also need to show "the exit point of a bullet", for example. info.ti1 and info.ti2 give an idea about the distance to the origin, so they can be used for things like calculating the intensity of a shooting that becomes weaker with distance.

Advanced API

The following methods are advanced and/or used internally by the library; most people will not need them.

local result = world:hasItem(item)

Returns wether the world contains the given item or not. This function does not throw an error if item is not included in world; it just returns false.

local count = world:countItems()

Returns the number of items inserted in the world. Useful for debugging

local items, len = world:getItems()

Builds and returns an array containing all the items in the world (as well as its length). This can be useful if you want to draw or update all the items in the world, without doing any queries. Notice that in which the items will be returned is non-deterministic.

local x, y, z, w, h, d = world:getCube(item)

Given an item, obtain the coordinates of its bounding cube. Useful for debugging/testing things.

local cell_count = world:countCells()

Returns the number of cells being used. Useful for testing/debugging.

local cx, cy, cz = world:toCell(x, y, z)

Given a point, return the coordinates of the cell that containg it using the world's cellSize. Useful mostly for debugging bump-3dpd, or drawing debug info.

local x, y, z = world:toWorld(cx, cy, cz)

The inverse of world:toCell. Given the coordinates of a cell, return the coordinates of its main corner in the game world.

local cols, len = world:project(item, x, y, z, w, h, d, goalX, goalY, goalZ, filter)

Moves a the given imaginary cube towards goalX, goalY, and goalZ, providing a list of collisions as they happen in that straight path.

This method might be useful when implementing your own new collision responses, although it could be also used as a query method.

local actualX,actualY,actualZ, cols, len = world:projectMove(item, x,y,z,w,h,d, goalX,goalY,goalZ, filter)

Similar to world:project(), except that it simulates collision responses as the cube tries to move along it's path. This is probably most useful for optimization, since it allows you to have items which move appropriately through your world without actually adding them to the world itself.

bump.responses.touch
bump.responses.cross
bump.responses.slide
bump.responses.bounce

These are the functions bump-3dpd uses to resolve collisions by default. You can use these functions' source as a base to build your own response function, if you feel adventurous.

world:addResponse(name, response)

This is how you register a new type of response in the world. All worlds come with the 4 pre-defined responses already installed, but you can add your own: if you register the response 'foo', if your filter returns 'foo' in a collision your world will handle it with response. This, however, is advanced stuff, and you will have to read the source code of the default responses in order to know how to do that.

bump.cube.getNearestCorner
bump.cube.getSegmentIntersectionIndices
bump.cube.getDiff
bump.cube.containsPoint
bump.cube.isIntersecting
bump.cube.getCubeDistance
bump.cube.detectCollision

bump-3dpd comes with some cube-related functions in the bump.cube namespace. These are not part of the official API and can change at any moment. However, feel free to use them if you are implementing your own collision responses.

Installation

Just copy the bump-3dpd.lua file wherever you want it. Then require it where you need it:

local bump = require 'bump-3dpd'

If you copied bump-3dpd.lua to a file not accesible from the root folder (for example a lib folder), change the code accordingly:

local bump = require 'lib.bump-3dpd'

License

bump-3dpd is licensed under the MIT license.

Specs

Specs for this project can be run using busted.

Changelog

See CHANGELOG.md for details

Todo