Skip to content
AABBs tree native extension for Defold Engine
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
daabbcc
input
lib-src
tests
.gitignore
README.md
game.project
html-build-sizes.txt
log.txt
release-nophysic.appmanifest
releasephysic.appmanifest

README.md

header.png

DAABBCC

DAABBCC is a terrible name of the AABB Tree + Experimental Collision Detection native extension for Defold Engine

Caution: This library is not battle tested (yet). It may contain memory leaks, performance drops...

About

DAABBCC is a C++ wrapper of AABB.cc and cute_c2 libs for Defold Engine.

AABB.cc is developed by Lester Hedges and released under the Zlib license. The code in AABB.cc library was adapted from parts of the Box2D physics engine.

tinyc2 is developed by Randy Gaul and released under the Zlib license.

DAABBCC is a C++ implementation of a dynamic bounding volume hierarchy (BVH) using axis-aligned bounding boxes (AABBs). The data structure provides an efficient way of detecting potential overlap between objects of arbitrary shape and size and is commonly used in computer games engines for collision detection and ray tracing.

Installation

You can use DAABBCC in your own project by adding this project as a Defold library dependency. Open your game.project file and in the dependencies field under project add:

https://github.com/selimanac/DAABBCC/archive/master.zip

Platforms

Supported platforms: Web, Windows, MacOS and Linux (64bit). It is also available for mobile but I couldn't test it yet.

What is this for?

First of all, this is not a complete collision library/solution. Basically it is a Broad Phase collision for fast overlap checking. You have to handle precise collision yoursef. This library contains experimental narrow phase collision detection functionalty.

Usage in Defold

You can use this native extension by simply calling 'daabbcc'.

Default "World" tree will be created on init with 0.0 tickness and 100 count.

Caution: Scaling may break your collision. You should recalculate the size manually.

Creating a new AABB Tree

- createTree

local tree_name = "World" -- Name of your tree
local dimension = 2 -- 2D. Original library works with 2D and 3D. Only 2D is implemented   
local thickness = 0.1 -- Thickness of bounding boxes.
local number = 4 -- Number of aabbs/bounding boxes. Optional but recommended.  

daabbcc.createTree(tree_name, dimension, thickness, [number])

You can create as many as trees according to your needs. Pseudo example for a platformer:

daabbcc.createTree("walls", 2, 0.1, 4)
daabbcc.createTree("enemies", 2, 0.1, 50)
daabbcc.createTree("collectables", 2, 0.1, 150)

Inserting AABBs

- insertCircle

Insert a AABB into the created tree. Works with radius. This method is not going to create a circular shape. It creates a square AABB from given radius. (radius = 10 mean 20x20 square)

insertCircle, returns the ID of the inserted AABB. You should probably keep track of those IDs in a lua table.

Caution: IDs starts with '0'

local tree_name = "World" -- Name of your tree
local radius = 10 -- radius of the circle. It is basically:  width/2 
local position = vmath.vector3(x,y,z) -- Position of your game object / go.get_position()

local _id = daabbcc.insertCircle(tree_name, radius, position.x, position.y)

- insertRect

Same as insertCircle but using size.

insertRect, returns the ID of the inserted AABB. You should probably keep track of those IDs in a lua table.

Caution: IDs starts with '0'

local tree_name = "World" -- Name of your tree
local position = vmath.vector3(x,y,z) -- Position of your game object / go.get_position()
local size = vmath.vector3(x,y,z) -- Size of your game object or sprite / go.get("#sprite", "size")

local _id = daabbcc.insertRect(tree_name, position.x, position.y, size.x, size.y)

Updating AABBs

If your game object(s) are not static, you should update their position and size when they move or resize.

- updateCircle

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object
local radius = 10 -- radius of the circle. It is basically:  width/2
local position = vmath.vector3(x,y,z) -- Position of your game object / go.get_position()

daabbcc.updateCircle(tree_name, id, radius, position.x, position.y)

- updateRect

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object
local position = vmath.vector3(x,y,z) -- Position of your game object / go.get_position()
local size = vmath.vector3(x,y,z) -- Size of your game object or sprite / go.get("#sprite", "size")

daabbcc.updateRect(tree_name, id, position.x, position.y, size.x, size.y)

Removing AABBs from Tree

- removeAABB

Remove AABB using ID

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object

daabbcc.removeAABB(tree_name,id)

- removeAll

Remove all AABBs from a tree

local tree_name = "World" -- Name of your tree

daabbcc.removeAll(tree_name)

Queries

You can query a tree by id or with AABB for possible overlaps. Query returns a lua table of object IDs.

Caution: You can't cross query between different trees.

- queryID

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object

local _result = daabbcc.queryID(tree_name, id)

- queryAABB

local tree_name = "World" -- Name of your tree
local position = go.get_position() -- Position of your object
local size = go.get("#sprite", "size")

local _result = daabbcc.queryAABB(tree_name,position.x,position.y,size.x,size.y)

Helpers

- validateTree

Validate the tree. (Not documented)

local tree_name = "World" -- Name of your tree

daabbcc.validateTree(tree_name)

- rebuildTree

Rebuild an optimal tree. (Not documented)

local tree_name = "World" -- Name of your tree

daabbcc.rebuildTree(tree_name)

- getHeight

Get the height of the tree.

local tree_name = "World" -- Name of your tree

daabbcc.getHeight(tree_name)

- getNodeCount

Get the number of nodes in the tree.

local tree_name = "World" -- Name of your tree

daabbcc.getNodeCount(tree_name)

- getAABB

Returns postion and size of bounding box.

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object

local x,y,w,h = daabbcc.getAABB(tree_name, id)

Experimental Narrow Phase Collision Detection

Swept AABB Collision Detection

Collision detection for a moving object against static object. Returns impact time and collision normal.

local tree_name = "World" -- Name of your tree
local moving_bb_id = 0 -- ID of your moving object
local static_bb_id = 1 -- ID of your static object
local target_velocity = vmath.vector3(25, 25, 0) -- target velocity of your moving object
local normal = vmath.vector3(1, 0, 0) -- Direction of your moving object

local collisionTime, c_normal_x,  c_normal_y = daabbcc.checkSweptCollision(tree_name, moving_bb_id, static_bb_id, target_velocity.x,target_velocity.y, normal.x, normal.y)

cute_c2 lib

- checkHit

Simple aabb to aabb collision check. Returns integer.

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object
local other_id = 1 -- ID of your other object

local hit =   daabbcc.checkHit(tree_name,id,  other_id)

- checkManifold

Manifold generation for colliding objects. Returns count, depth, normal and contact points.

local tree_name = "World" -- Name of your tree
local id = 0 -- ID of your object
local other_id = 1 -- ID of your other object

local count, depth, normal, contact_points = daabbcc.checkManifold(tree_name,id, other_id)

- createRay

Creates a ray and returns it is ID. You should probably keep track of those IDs in a lua table.

local position = vmath.vector3(0, 0, 0) -- ray start position
local direction = vmath.vector3(1, 0, 0) -- ray direction
local distance = 20 -- ray distance

local ray_id = daabbcc.createRay(position.x,position.y, direction.x, direction.y, distance)

- updateRay

Updates current Ray.

local id = 0 -- ID of your ray
local position = vmath.vector3(0, 0, 0) -- ray start position
local direction = vmath.vector3(1, 0, 0) -- ray direction
local distance = 20 -- ray distance

daabbcc.updateRay(id, position.x,position.y, direction.x, direction.y, distance)

- removeRay

Removes a Ray.

local id = 0 -- ID of your ray

daabbcc.removeRay(ray_id)

- rayCastToAABB

Cast a ray to AABB. Returns hit, impact and end poin.

local ray_id = 0 -- ID of your ray
local other_id = 1 -- ID of you object
local tree_name = "World" -- Name of your tree

local hit,ray_end, impact, ray_normal = daabbcc.rayCastToAABB(tree_name, id, other_id)
-- hit: 0-1
-- ray_end: End point of the ray
-- impact: If there is a hit, returns impact point of the ray
-- ray_normal: If there is a hit returns normal

Examples

Since I am a lazy developer, you can find my terrible test files in the source. Also I am working on a simple platformer for testing this library: https://github.com/selimanac/DAABBCC-Platformer

Size Comparison

Default project html build js size comparison. (Defold v1.2.123)

Default Sizes
Without manifest 5.092.579 bytes
Exclude: Physics, Record, Profiler, Facebook 4.183.078 bytes
Exclude: Record, Profiler, Facebook 5.048.428 bytes
DAABBCC included Sizes
Without manifest 6.130.055 bytes
Exclude: Physics, Record, Profiler, Facebook 4.533.029 bytes
Exclude: Record, Profiler, Facebook 5.396.846 bytes
DAABBCC without swept Sizes
Without manifest 6.125.678 bytes
Exclude: Physics, Record, Profiler, Facebook 4.528.604 bytes
Exclude: Record, Profiler, Facebook 5.392.367 bytes
DAABBCC without swept + tinyc2 Sizes
Without manifest 6.113.874 bytes
Exclude: Physics, Record, Profiler, Facebook 4.516.716 bytes
Exclude: Record, Profiler, Facebook 5.380.689 bytes

Performance and Notes

If you know what you are doing, lib is very performant. But that doesn't mean it is a competitor to build-in collision with physics. It is not. First of all; you should handle all collision responses by yourself. Which means you need loops and logics. Maybe lots of them.This approach is very CPU intensive and results may differ according to CPU performance. Also, resolution may affect the performance.

I made some stress tests just for fun. Those number are not acceptable in real game. Maybe(just maybe) you can use less than half of the numbers. Dt is fixed to 60, not variable. I drop down the item numbers and their speed. Because of the screen video recording cause a memory leap. I believe the code can be more optimised.

Keep in mind: This lib is not battle tested.

My test platform is:

  • macOS 10.13.2
  • 2GHz Intel Core i7
  • 8GB 1600 MHz DDR3
  • Intel HD Graphics 4000

Youtube videos:

600 sprites in the box

Crazy 700 sprites goes into the black hole

600 sprites in the box with Defold Engine

Crazy 700 sprites goes into the black hole with Defold Engine

AABB.cc Docs

Doxygen Docs: https://codedocs.xyz/selimanac/aabbcc/

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.