Dynamic AABB Tree native extension with Branch and Bound Algorithm for Defold Engine
This is a Dynamic AABB Tree native extension with Branch and Bound Algorithm for Defold Engine.
DAABBCC build by using Box2D’s Dynamic Tree.
Branch and Bound implementation by Randy Gaul
Radix sort by Mathias Westerdahl
Box2D Copyright (c) 2009 Erin Catto http://www.box2d.org
What is DAABBCC?
A Dynamic AABB Tree is a binary search algorithm for fast overlap testing. Dynamic AABB trees are good for general purpose use, and can handle moving objects very well. The data structure provides an efficient way of detecting potential overlap between objects. DAABBCC does not contain narrow-phase collision detection.
You can use it whenever precise collision manifold(narrow-phase) is not required.
You can use the 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/refs/tags/v2.1.2.zip
2.1.2
aabb.update_frequency()
.2.1.1
2.1
raycast_sort
, query_id_sort
, query_sort
according to your needs #5.#count
anymore.2.0
This is a complete rewritten version by using Box2D’s Dynamic Tree.
Final 1.x release.
1.0
Initial release.
New empty group for AABBs.
RETURN
group_id
(int) - New group ID.EXAMPLE
local group_id = aabb.new_group()
group_id
, x
, y
, width
, height
)Insert AABB into the group.
PARAMETERS
group_id
(int) - Group ID.x
(number) - X position of AABB.y
(number) - Y position of AABB.width
(int) - Width of AABB.height
(int) - Height of AABB.RETURN
aabb_id
(int) - New AABB ID.EXAMPLE
local x = 0
local y = 0
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert(group_id, x, y, width, height)
-- OR --
self.pos = go.get_position(".")
self.size = go.get("#sprite", "size")
self.group_id = aabb.new_group()
self.aabb_id = aabb.insert(self.group_id, self.pos.x , self.pos.y, self.size.x, self.size.y)
group_id
, url
, width
, height
)Insert Gameobject and the associated AABB into a group.
Most suitable for moving gameobjects. If your gameobject is static then use aabb.insert
instead.
PARAMETERS
group_id
(int) - Group ID.url
(msg.url) - URL of Gameobject.width
(int) - Width of AABB.height
(int) - Height of AABB.RETURN
aabb_id
(int) - New AABB ID.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
group_id
, aabb_id
, x
, y
, width
, height
)Updates the AABB position and size when you change its position or size.
Gameobject AABB positions will be overwritten.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.x
(number) - X position of AABB.y
(number) - Y position of AABB.width
(int) - Width of AABB.height
(int) - Height of AABB.EXAMPLE
local x = 0
local y = 0
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert(group_id, x, y, width, height)
local new_x = 10
local new_y = 10
local new_w = 60
local new_h = 60
aabb.update(group_id, aabb_id, new_x, new_y, new_w, new_h)
group_id
, aabb_id
, w
, h
)Updates the AABB size related to the Gameobject.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.width
(int) - Width of AABB.height
(int) - Height of AABB.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
local new_w = 60
local new_h = 60
aabb.update_gameobject(group_id, aabb_id, new_w, new_h)
group_id
, aabb_id
)Query the possible overlaps using AABB ID.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.RETURN
result
(table) - Table of possible overlapping AABBs.count
(int) - Count of result
table.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
local result, count = aabb.query_id(group_id, aabb_id)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
, x
, y
, width
, height
)Query the possible overlaps without AABB ID.
PARAMETERS
group_id
(int) - Group ID.x
(number) - X position.y
(number) - Y position.width
(int) - Width.height
(int) - Height.RETURN
result
(table) - Table of possible overlapping AABBs.count
(int) - Count of result
table.EXAMPLE
local x = 0
local y = 0
local width = 50
local height = 50
local group_id = aabb.new_group()
local result, count = aabb.query(group_id, x, y, width, height)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
, aabb_id
)Query the possible overlaps using AABB ID.
Returns result table with ids and distance, ordered by closest first.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.RETURN
result
(table) - Table of possible overlapping AABBs. Result table contains aabb_id
and distance
.count
(int) - Count of result
table.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
local result, count = aabb.query_id_sort(group_id, aabb_id)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
, x
, y
, width
, height
)Query the possible overlaps without AABB ID.
Returns result table with ids and distance, ordered by closest first.
PARAMETERS
group_id
(int) - Group ID.x
(number) - X position.y
(number) - Y position.width
(int) - Width.height
(int) - Height.RETURN
result
(table) - Table of possible overlapping AABBs. Result table contains aabb_id
and distance
.count
(int) - Count of result
table.EXAMPLE
local x = 0
local y = 0
local width = 50
local height = 50
local group_id = aabb.new_group()
local result, count = aabb.query_sort(group_id, x, y, width, height)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
, start_x
, start_y
, end_x
, end_y
)Query the possible overlaps using RAYCAST.
PARAMETERS
group_id
(int) - Group ID.start_x
(number) - Ray start position X.start_y
(number) - Ray start position Y.end_x
(number) - Ray end position X.end_y
(number) - Ray end position Y.RETURN
result
(table) - Table of possible overlapping AABBs.count
(int) - Count of result
table.EXAMPLE
local group_id = aabb.new_group()
local ray_start = vmath.vector3(0, 0, 0)
local ray_end = vmath.vector3(365, 370, 0)
local result, count = aabb.raycast(group_id, ray_start.x, ray_start.y, ray_end.x, ray_end.y)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
, start_x
, start_y
, end_x
, end_y
)Query the possible overlaps using RAYCAST.
Returns result table with ids and distance, ordered by closest first.
PARAMETERS
group_id
(int) - Group ID.start_x
(number) - Ray start position X.start_y
(number) - Ray start position Y.end_x
(number) - Ray end position X.end_y
(number) - Ray end position Y.RETURN
result
(table) - Table of possible overlapping AABBs. Result table contains aabb_id
and distance
.count
(int) - Count of result
table.EXAMPLE
local group_id = aabb.new_group()
local ray_start = vmath.vector3(0, 0, 0)
local ray_end = vmath.vector3(365, 370, 0)
local result, count = aabb.raycast_sort(group_id, ray_start.x, ray_start.y, ray_end.x, ray_end.y)
if result then
for i = 1, count do
print(result[i])
end
end
group_id
)Removes the group and all associated AABBs and Gameobjects.
PARAMETERS
group_id
(int) - Group ID.EXAMPLE
local group_id = aabb.new_group()
aabb.remove_group(group_id)
group_id
, aabb_id
)Removes the AABB and Gameobject from group.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
aabb.remove(group_id, aabb_id)
group_id
, aabb_id
)Removes gameobject and the associated AABB.
You don't need to call aabb.remove
again for removing AABB.
PARAMETERS
group_id
(int) - Group ID.aabb_id
(int) - AABB ID.EXAMPLE
local go_url = msg.url("/go")
local width = 50
local height = 50
local group_id = aabb.new_group()
local aabb_id = aabb.insert_gameobject(group_id, go_url, width, height)
aabb.remove_gameobject(group_id, aabb_id)
state
)Stop/resume Gameobject position update iteration.
It is true
by default, but does not iterate when when there are no Gameobjects registered.
PARAMETERS
state
(boolean) - True/FalseEXAMPLE
aabb.run(true)
Clear everything (AABBs,groups, gameobjects) and reset to initial state.
EXAMPLE
aabb.clear()
update_frequency
)It is possible to set a independent update frequency for gameobject loop. Default value is set from game.project file(display.frequency).
PARAMETERS
update_frequency
(int) - Update Frequency.EXAMPLE
aabb.update_frequency(5)
Developer: 8BitSkull
Publisher: 8BitSkull
Release Date: 21 Oct, 2022
Steam: https://store.steampowered.com/app/2005210/Void_Scrappers/
Switch: https://www.nintendo.co.uk/Games/Nintendo-Switch-download-software/Void-Scrappers-2344179.html.
Developer: 8BitSkull
Publisher: 8BitSkull
Release Date: 8 Mar, 2024
Steam: https://store.steampowered.com/app/2398170/BORE_BLASTERS/
Switch: TBA