Skip to content

Commit 528908a

Browse files
numberZeronerzhul
numberZero
authored and
nerzhul
committedApr 3, 2018
Optimize entity-entity collision (#6587)
* Add IrrLicht type aliases * Add hash for IrrLicht vector * Add object map
·
5.11.05.0.0
1 parent 2481ea2 commit 528908a

13 files changed

+613
-80
lines changed
 

‎build/android/jni/Android.mk

+1
Original file line numberDiff line numberDiff line change
@@ -221,6 +221,7 @@ LOCAL_SRC_FILES := \
221221
jni/src/rollback_interface.cpp \
222222
jni/src/serialization.cpp \
223223
jni/src/server/mods.cpp \
224+
jni/src/server/serveractiveobjectmap.cpp \
224225
jni/src/server.cpp \
225226
jni/src/serverenvironment.cpp \
226227
jni/src/serverlist.cpp \

‎src/content_sao.cpp

+4
Original file line numberDiff line numberDiff line change
@@ -224,6 +224,7 @@ ObjectProperties* UnitSAO::accessObjectProperties()
224224

225225
void UnitSAO::notifyObjectPropertiesModified()
226226
{
227+
m_env->updateActiveObject(this);
227228
m_properties_sent = false;
228229
}
229230

@@ -607,6 +608,7 @@ void LuaEntitySAO::setPos(const v3f &pos)
607608
if(isAttached())
608609
return;
609610
m_base_position = pos;
611+
m_env->updateActiveObject(this);
610612
sendPosition(false, true);
611613
}
612614

@@ -615,6 +617,7 @@ void LuaEntitySAO::moveTo(v3f pos, bool continuous)
615617
if(isAttached())
616618
return;
617619
m_base_position = pos;
620+
m_env->updateActiveObject(this);
618621
if(!continuous)
619622
sendPosition(true, true);
620623
}
@@ -1102,6 +1105,7 @@ void PlayerSAO::setBasePosition(const v3f &position)
11021105

11031106
// This needs to be ran for attachments too
11041107
ServerActiveObject::setBasePosition(position);
1108+
m_env->updateActiveObject(this);
11051109
m_position_not_sent = true;
11061110
}
11071111

‎src/irr_aabb3d.h

+2
Original file line numberDiff line numberDiff line change
@@ -24,3 +24,5 @@ with this program; if not, write to the Free Software Foundation, Inc.,
2424
#include <aabbox3d.h>
2525

2626
typedef core::aabbox3d<f32> aabb3f;
27+
typedef core::aabbox3d<s16> aabb3s16;
28+
typedef core::aabbox3d<s32> aabb3s32;

‎src/irr_v3d.h

+18-2
Original file line numberDiff line numberDiff line change
@@ -18,13 +18,29 @@ with this program; if not, write to the Free Software Foundation, Inc.,
1818
*/
1919

2020
#pragma once
21-
2221
#include "irrlichttypes.h"
23-
2422
#include <vector3d.h>
23+
#include <functional>
2524

2625
typedef core::vector3df v3f;
2726
typedef core::vector3d<double> v3d;
2827
typedef core::vector3d<s16> v3s16;
2928
typedef core::vector3d<u16> v3u16;
3029
typedef core::vector3d<s32> v3s32;
30+
31+
namespace std
32+
{
33+
template <> struct hash<v3s16>
34+
{
35+
typedef v3s16 argument_type;
36+
typedef std::size_t result_type;
37+
result_type operator()(const argument_type &s) const noexcept
38+
{
39+
// clang-format off
40+
return static_cast<size_t>((static_cast<u64>(s.X) << 20) ^
41+
(static_cast<u64>(s.Y) << 10) ^
42+
(static_cast<u64>(s.Z)));
43+
// clang-format on
44+
}
45+
};
46+
}

‎src/server/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
11
set(server_SRCS
22
${CMAKE_CURRENT_SOURCE_DIR}/mods.cpp
3+
${CMAKE_CURRENT_SOURCE_DIR}/serveractiveobjectmap.cpp
34
PARENT_SCOPE)

‎src/server/serveractiveobjectmap.cpp

+196
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,196 @@
1+
/*
2+
Minetest
3+
Copyright (C) 2018 numZero, Lobachevsky Vitaly <numzer0@yandex.com>
4+
5+
This program is free software; you can redistribute it and/or modify
6+
it under the terms of the GNU Lesser General Public License as published by
7+
the Free Software Foundation; either version 2.1 of the License, or
8+
(at your option) any later version.
9+
10+
This program is distributed in the hope that it will be useful,
11+
but WITHOUT ANY WARRANTY; without even the implied warranty of
12+
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13+
GNU Lesser General Public License for more details.
14+
15+
You should have received a copy of the GNU Lesser General Public License along
16+
with this program; if not, write to the Free Software Foundation, Inc.,
17+
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18+
*/
19+
20+
#include "serveractiveobjectmap.h"
21+
#include "constants.h"
22+
#include "log.h"
23+
#include "serverobject.h"
24+
25+
static constexpr float granularity = 16.0 * BS;
26+
27+
static aabb3s16 calcBox(const aabb3f &cb)
28+
{
29+
return aabb3s16(
30+
floor(cb.MinEdge.X / granularity),
31+
floor(cb.MinEdge.Y / granularity),
32+
floor(cb.MinEdge.Z / granularity),
33+
ceil(cb.MaxEdge.X / granularity),
34+
ceil(cb.MaxEdge.Y / granularity),
35+
ceil(cb.MaxEdge.Z / granularity));
36+
}
37+
38+
void ServerActiveObjectMap::addObject(ServerActiveObject *object)
39+
{
40+
aabb3f cb;
41+
Wrapper w;
42+
u16 id = object->getId();
43+
if (!isFreeId(id))
44+
throw std::logic_error("ServerActiveObjectMap::addObject: "
45+
"object ID in use: " + std::to_string(id));
46+
w.object = object;
47+
w.has_box = w.object->getCollisionBox(&cb);
48+
if (w.has_box) {
49+
w.box = calcBox(cb);
50+
addObjectRefs(id, w.box);
51+
}
52+
objects.emplace(id, w);
53+
}
54+
55+
ServerActiveObject *ServerActiveObjectMap::removeObject(u16 id)
56+
{
57+
auto pw = objects.find(id);
58+
if (pw == objects.end())
59+
return nullptr; // silently ignore non-existent object
60+
Wrapper w = pw->second;
61+
if (w.has_box)
62+
removeObjectRefs(id, w.box);
63+
objects.erase(pw);
64+
return w.object;
65+
}
66+
67+
void ServerActiveObjectMap::removeObject(ServerActiveObject *object)
68+
{
69+
removeObject(object->getId());
70+
}
71+
72+
void ServerActiveObjectMap::updateObject(u16 id)
73+
{
74+
auto pw = objects.find(id);
75+
if (pw == objects.end()) {
76+
warningstream << "Trying to update non-existent object: " << id
77+
<< std::endl;
78+
return;
79+
}
80+
Wrapper &w = pw->second;
81+
aabb3f cb;
82+
aabb3s16 box;
83+
bool has_box = w.object->getCollisionBox(&cb);
84+
if (has_box)
85+
box = calcBox(cb);
86+
if (w.has_box && has_box && w.box == box)
87+
return;
88+
if (w.has_box)
89+
removeObjectRefs(id, w.box);
90+
w.box = box;
91+
w.has_box = has_box;
92+
if (w.has_box)
93+
addObjectRefs(id, w.box);
94+
}
95+
96+
void ServerActiveObjectMap::updateObject(ServerActiveObject *object)
97+
{
98+
updateObject(object->getId());
99+
}
100+
101+
ServerActiveObject *ServerActiveObjectMap::getObject(u16 id) const
102+
{
103+
auto pw = objects.find(id);
104+
if (pw == objects.end())
105+
return nullptr;
106+
return pw->second.object;
107+
}
108+
109+
std::vector<u16> ServerActiveObjectMap::getObjectsInsideRadius(v3f pos, float radius)
110+
{
111+
std::vector<u16> result;
112+
auto nearby = getObjectsNearBox(calcBox({pos - radius, pos + radius}));
113+
for (auto &id : nearby) {
114+
ServerActiveObject *obj = getObject(id);
115+
v3f objectpos = obj->getBasePosition();
116+
if (objectpos.getDistanceFrom(pos) > radius)
117+
continue;
118+
result.push_back(id);
119+
}
120+
return result;
121+
}
122+
123+
std::vector<u16> ServerActiveObjectMap::getObjectsTouchingBox(const aabb3f &box)
124+
{
125+
std::vector<u16> result;
126+
auto nearby = getObjectsNearBox(calcBox(box));
127+
for (auto &id : nearby) {
128+
ServerActiveObject *obj = getObject(id);
129+
aabb3f cb;
130+
if (!obj->getCollisionBox(&cb))
131+
continue;
132+
if (!box.intersectsWithBox(cb))
133+
continue;
134+
result.push_back(id);
135+
}
136+
return result;
137+
}
138+
139+
std::unordered_set<u16> ServerActiveObjectMap::getObjectsNearBox(const aabb3s16 &box)
140+
{
141+
std::unordered_set<u16> result;
142+
v3s16 p;
143+
for (p.Z = box.MinEdge.Z; p.Z <= box.MaxEdge.Z; p.Z++)
144+
for (p.Y = box.MinEdge.Y; p.Y <= box.MaxEdge.Y; p.Y++)
145+
for (p.X = box.MinEdge.X; p.X <= box.MaxEdge.X; p.X++) {
146+
auto bounds = refmap.equal_range(p);
147+
for (auto iter = bounds.first; iter != bounds.second; ++iter)
148+
result.insert(iter->second);
149+
}
150+
return result;
151+
}
152+
153+
void ServerActiveObjectMap::addObjectRefs(u16 id, const aabb3s16 &box)
154+
{
155+
v3s16 p;
156+
for (p.Z = box.MinEdge.Z; p.Z <= box.MaxEdge.Z; p.Z++)
157+
for (p.Y = box.MinEdge.Y; p.Y <= box.MaxEdge.Y; p.Y++)
158+
for (p.X = box.MinEdge.X; p.X <= box.MaxEdge.X; p.X++)
159+
refmap.emplace(p, id);
160+
}
161+
162+
void ServerActiveObjectMap::removeObjectRefs(u16 id, const aabb3s16 &box)
163+
{
164+
v3s16 p;
165+
for (p.Z = box.MinEdge.Z; p.Z <= box.MaxEdge.Z; p.Z++)
166+
for (p.Y = box.MinEdge.Y; p.Y <= box.MaxEdge.Y; p.Y++)
167+
for (p.X = box.MinEdge.X; p.X <= box.MaxEdge.X; p.X++) {
168+
auto bounds = refmap.equal_range(p);
169+
for (auto iter = bounds.first; iter != bounds.second;)
170+
if (iter->second == id)
171+
refmap.erase(iter++);
172+
else
173+
++iter;
174+
}
175+
}
176+
177+
bool ServerActiveObjectMap::isFreeId(u16 id)
178+
{
179+
if (id == 0)
180+
return false;
181+
return objects.find(id) == objects.end();
182+
}
183+
184+
u16 ServerActiveObjectMap::getFreeId()
185+
{
186+
// try to reuse id's as late as possible
187+
static u16 last_used_id = 0;
188+
u16 startid = last_used_id;
189+
for (;;) {
190+
last_used_id++;
191+
if (isFreeId(last_used_id))
192+
return last_used_id;
193+
if (last_used_id == startid) // wrapped around
194+
return 0;
195+
}
196+
}

‎src/server/serveractiveobjectmap.h

+143
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
/*
2+
Minetest
3+
Copyright (C) 2018 numZero, Lobachevsky Vitaly <numzer0@yandex.com>
4+
5+
This program is free software; you can redistribute it and/or modify
6+
it under the terms of the GNU Lesser General Public License as published by
7+
the Free Software Foundation; either version 2.1 of the License, or
8+
(at your option) any later version.
9+
10+
This program is distributed in the hope that it will be useful,
11+
but WITHOUT ANY WARRANTY; without even the implied warranty of
12+
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13+
GNU Lesser General Public License for more details.
14+
15+
You should have received a copy of the GNU Lesser General Public License along
16+
with this program; if not, write to the Free Software Foundation, Inc.,
17+
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18+
*/
19+
20+
#pragma once
21+
#include <unordered_set>
22+
#include <unordered_map>
23+
#include <vector>
24+
#include "irr_v3d.h"
25+
#include "irr_aabb3d.h"
26+
27+
class ServerActiveObject;
28+
29+
/*!
30+
* The class to speed up collision tests.
31+
*
32+
* @note It stores any objects but only those that has valid collision box
33+
* (`physical` Lua entities) are actually processed.
34+
* @note It uses world coordinate units, i.e. node size is always BS.
35+
*/
36+
struct ServerActiveObjectMap
37+
{
38+
struct Wrapper
39+
{
40+
ServerActiveObject *object;
41+
aabb3s16 box;
42+
bool has_box;
43+
};
44+
45+
/*!
46+
* Adds object to the map. It must have valid ID.
47+
*
48+
* If an object with the same ID already exists in the map,
49+
* std::logic_error is thrown.
50+
*/
51+
void addObject(ServerActiveObject *object);
52+
53+
/*!
54+
* Removes object from the map. The pointer must be valid.
55+
* See `removeObject(u16)` for details.
56+
*/
57+
void removeObject(ServerActiveObject *object);
58+
59+
/*!
60+
* Removes object from the map.
61+
*
62+
* If the object is not found, the call is ignored.
63+
* The function never throws, unless the underlying container throws.
64+
*/
65+
ServerActiveObject *removeObject(u16 id);
66+
67+
/*!
68+
* Updates object metadata stored in the map.
69+
* See `updateObject(u16)` for details.
70+
*/
71+
void updateObject(ServerActiveObject *object);
72+
73+
/*!
74+
* Updates object metadata stored in the map.
75+
*
76+
* The metadata includes (approximate) absolute collision box and
77+
* its existence (`physical` property for Lua entities).
78+
* This function must be called after each change of these properties,
79+
* including each object movement.
80+
*/
81+
void updateObject(u16 id);
82+
83+
/*!
84+
* Returns the object with given ID, if any.
85+
* Returns NULL otherwise.
86+
*/
87+
ServerActiveObject *getObject(u16 id) const;
88+
89+
/*!
90+
* Checks if the given ID is free and valid (i.e. non-zero).
91+
*/
92+
bool isFreeId(u16 id);
93+
94+
/*!
95+
* Returns a free ID, if any. Returns 0 in the case of failure.
96+
*
97+
* @note This function doesn't reserve the ID; it remains free until
98+
* an object with that ID is added.
99+
* @note This function tries to reclaim freed IDs as late as possible.
100+
* However, there is no guarantee.
101+
*/
102+
u16 getFreeId();
103+
104+
/*!
105+
* Returns a list of objects whose base position is at distance less
106+
* than @p radius from @p pos.
107+
*
108+
* @note Due to inexact nature of floating-point computations, it is
109+
* undefined whether an object lying exactly at the boundary is included
110+
* in the list or not.
111+
* @note Objects with base position outside of the collision box may not
112+
* be returned.
113+
* @note Objects without valid collision box are not returned.
114+
*/
115+
std::vector<u16> getObjectsInsideRadius(v3f pos, float radius);
116+
117+
/*!
118+
* Returns a list of objects whose collision box intersects with @p box
119+
*
120+
* @note Due to inexact nature of floating-point computations, it is
121+
* undefined whether an object lying exactly at the boundary is included
122+
* in the list or not.
123+
*/
124+
std::vector<u16> getObjectsTouchingBox(const aabb3f &box);
125+
126+
/*!
127+
* Returns count of objects in the map.
128+
*/
129+
std::size_t size() const { return objects.size(); }
130+
131+
/*!
132+
* Returns reference to the underlying container.
133+
*/
134+
const std::unordered_map<u16, Wrapper> &getObjects() const { return objects; }
135+
136+
private:
137+
void addObjectRefs(u16 id, const aabb3s16 &box);
138+
void removeObjectRefs(u16 id, const aabb3s16 &box);
139+
std::unordered_set<u16> getObjectsNearBox(const aabb3s16 &box);
140+
141+
std::unordered_map<u16, Wrapper> objects;
142+
std::unordered_multimap<v3s16, u16> refmap;
143+
};

‎src/serverenvironment.cpp

+26-62
Original file line numberDiff line numberDiff line change
@@ -996,24 +996,17 @@ bool ServerEnvironment::swapNode(v3s16 p, const MapNode &n)
996996
void ServerEnvironment::getObjectsInsideRadius(std::vector<u16> &objects, v3f pos,
997997
float radius)
998998
{
999-
for (auto &activeObject : m_active_objects) {
1000-
ServerActiveObject* obj = activeObject.second;
1001-
u16 id = activeObject.first;
1002-
v3f objectpos = obj->getBasePosition();
1003-
if (objectpos.getDistanceFrom(pos) > radius)
1004-
continue;
1005-
objects.push_back(id);
1006-
}
999+
objects = m_active_objects.getObjectsInsideRadius(pos, radius);
10071000
}
10081001

10091002
void ServerEnvironment::clearObjects(ClearObjectsMode mode)
10101003
{
10111004
infostream << "ServerEnvironment::clearObjects(): "
10121005
<< "Removing all active objects" << std::endl;
10131006
std::vector<u16> objects_to_remove;
1014-
for (auto &it : m_active_objects) {
1007+
for (auto &it : m_active_objects.getObjects()) {
10151008
u16 id = it.first;
1016-
ServerActiveObject* obj = it.second;
1009+
ServerActiveObject* obj = it.second.object;
10171010
if (obj->getType() == ACTIVEOBJECT_TYPE_PLAYER)
10181011
continue;
10191012

@@ -1040,7 +1033,7 @@ void ServerEnvironment::clearObjects(ClearObjectsMode mode)
10401033

10411034
// Remove references from m_active_objects
10421035
for (u16 i : objects_to_remove) {
1043-
m_active_objects.erase(i);
1036+
m_active_objects.removeObject(i);
10441037
}
10451038

10461039
// Get list of loaded blocks
@@ -1338,8 +1331,8 @@ void ServerEnvironment::step(float dtime)
13381331
send_recommended = true;
13391332
}
13401333

1341-
for (auto &ao_it : m_active_objects) {
1342-
ServerActiveObject* obj = ao_it.second;
1334+
for (auto &ao_it : m_active_objects.getObjects()) {
1335+
ServerActiveObject* obj = ao_it.second.object;
13431336
if (obj->isGone())
13441337
continue;
13451338

@@ -1425,40 +1418,7 @@ void ServerEnvironment::deleteParticleSpawner(u32 id, bool remove_from_object)
14251418

14261419
ServerActiveObject* ServerEnvironment::getActiveObject(u16 id)
14271420
{
1428-
ServerActiveObjectMap::const_iterator n = m_active_objects.find(id);
1429-
return (n != m_active_objects.end() ? n->second : NULL);
1430-
}
1431-
1432-
/**
1433-
* Verify if id is a free active object id
1434-
* @param id
1435-
* @return true if slot is free
1436-
*/
1437-
bool ServerEnvironment::isFreeServerActiveObjectId(u16 id) const
1438-
{
1439-
if (id == 0)
1440-
return false;
1441-
1442-
return m_active_objects.find(id) == m_active_objects.end();
1443-
}
1444-
1445-
/**
1446-
* Retrieve the first free ActiveObject ID
1447-
* @return free activeobject ID or 0 if none was found
1448-
*/
1449-
u16 ServerEnvironment::getFreeServerActiveObjectId()
1450-
{
1451-
// try to reuse id's as late as possible
1452-
static u16 last_used_id = 0;
1453-
u16 startid = last_used_id;
1454-
for (;;) {
1455-
last_used_id++;
1456-
if (isFreeServerActiveObjectId(last_used_id))
1457-
return last_used_id;
1458-
1459-
if (last_used_id == startid)
1460-
return 0;
1461-
}
1421+
return m_active_objects.getObject(id);
14621422
}
14631423

14641424
u16 ServerEnvironment::addActiveObject(ServerActiveObject *object)
@@ -1469,6 +1429,12 @@ u16 ServerEnvironment::addActiveObject(ServerActiveObject *object)
14691429
return id;
14701430
}
14711431

1432+
void ServerEnvironment::updateActiveObject(ServerActiveObject *object)
1433+
{
1434+
assert(object);
1435+
m_active_objects.updateObject(object);
1436+
}
1437+
14721438
/*
14731439
Finds out what new objects have been added to
14741440
inside a radius around a position
@@ -1490,11 +1456,11 @@ void ServerEnvironment::getAddedActiveObjects(PlayerSAO *playersao, s16 radius,
14901456
- discard objects that are found in current_objects.
14911457
- add remaining objects to added_objects
14921458
*/
1493-
for (auto &ao_it : m_active_objects) {
1459+
for (auto &ao_it : m_active_objects.getObjects()) {
14941460
u16 id = ao_it.first;
14951461

14961462
// Get object
1497-
ServerActiveObject *object = ao_it.second;
1463+
ServerActiveObject *object = ao_it.second.object;
14981464
if (object == NULL)
14991465
continue;
15001466

@@ -1578,16 +1544,14 @@ void ServerEnvironment::setStaticForActiveObjectsInBlock(
15781544

15791545
for (auto &so_it : block->m_static_objects.m_active) {
15801546
// Get the ServerActiveObject counterpart to this StaticObject
1581-
ServerActiveObjectMap::const_iterator ao_it = m_active_objects.find(so_it.first);
1582-
if (ao_it == m_active_objects.end()) {
1547+
ServerActiveObject *sao = m_active_objects.getObject(so_it.first);
1548+
if (!sao) {
15831549
// If this ever happens, there must be some kind of nasty bug.
15841550
errorstream << "ServerEnvironment::setStaticForObjectsInBlock(): "
15851551
"Object from MapBlock::m_static_objects::m_active not found "
15861552
"in m_active_objects";
15871553
continue;
15881554
}
1589-
1590-
ServerActiveObject *sao = ao_it->second;
15911555
sao->m_static_exists = static_exists;
15921556
sao->m_static_block = static_block;
15931557
}
@@ -1644,7 +1608,7 @@ u16 ServerEnvironment::addActiveObjectRaw(ServerActiveObject *object,
16441608
{
16451609
assert(object); // Pre-condition
16461610
if(object->getId() == 0){
1647-
u16 new_id = getFreeServerActiveObjectId();
1611+
u16 new_id = m_active_objects.getFreeId();
16481612
if(new_id == 0)
16491613
{
16501614
errorstream<<"ServerEnvironment::addActiveObjectRaw(): "
@@ -1660,7 +1624,7 @@ u16 ServerEnvironment::addActiveObjectRaw(ServerActiveObject *object,
16601624
<<"supplied with id "<<object->getId()<<std::endl;
16611625
}
16621626

1663-
if(!isFreeServerActiveObjectId(object->getId())) {
1627+
if (!m_active_objects.isFreeId(object->getId())) {
16641628
errorstream<<"ServerEnvironment::addActiveObjectRaw(): "
16651629
<<"id is not free ("<<object->getId()<<")"<<std::endl;
16661630
if(object->environmentDeletes())
@@ -1681,7 +1645,7 @@ u16 ServerEnvironment::addActiveObjectRaw(ServerActiveObject *object,
16811645
/*infostream<<"ServerEnvironment::addActiveObjectRaw(): "
16821646
<<"added (id="<<object->getId()<<")"<<std::endl;*/
16831647

1684-
m_active_objects[object->getId()] = object;
1648+
m_active_objects.addObject(object);
16851649

16861650
verbosestream<<"ServerEnvironment::addActiveObjectRaw(): "
16871651
<<"Added id="<<object->getId()<<"; there are now "
@@ -1727,9 +1691,9 @@ u16 ServerEnvironment::addActiveObjectRaw(ServerActiveObject *object,
17271691
void ServerEnvironment::removeRemovedObjects()
17281692
{
17291693
std::vector<u16> objects_to_remove;
1730-
for (auto &ao_it : m_active_objects) {
1694+
for (auto &ao_it : m_active_objects.getObjects()) {
17311695
u16 id = ao_it.first;
1732-
ServerActiveObject* obj = ao_it.second;
1696+
ServerActiveObject* obj = ao_it.second.object;
17331697

17341698
// This shouldn't happen but check it
17351699
if (!obj) {
@@ -1794,7 +1758,7 @@ void ServerEnvironment::removeRemovedObjects()
17941758
}
17951759
// Remove references from m_active_objects
17961760
for (u16 i : objects_to_remove) {
1797-
m_active_objects.erase(i);
1761+
m_active_objects.removeObject(i);
17981762
}
17991763
}
18001764

@@ -1916,11 +1880,11 @@ void ServerEnvironment::activateObjects(MapBlock *block, u32 dtime_s)
19161880
void ServerEnvironment::deactivateFarObjects(bool _force_delete)
19171881
{
19181882
std::vector<u16> objects_to_remove;
1919-
for (auto &ao_it : m_active_objects) {
1883+
for (auto &ao_it : m_active_objects.getObjects()) {
19201884
// force_delete might be overriden per object
19211885
bool force_delete = _force_delete;
19221886

1923-
ServerActiveObject* obj = ao_it.second;
1887+
ServerActiveObject* obj = ao_it.second.object;
19241888
assert(obj);
19251889

19261890
// Do not deactivate if static data creation not allowed
@@ -2051,7 +2015,7 @@ void ServerEnvironment::deactivateFarObjects(bool _force_delete)
20512015

20522016
// Remove references from m_active_objects
20532017
for (u16 i : objects_to_remove) {
2054-
m_active_objects.erase(i);
2018+
m_active_objects.removeObject(i);
20552019
}
20562020
}
20572021

‎src/serverenvironment.h

+2-14
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
2222
#include "activeobject.h"
2323
#include "environment.h"
2424
#include "mapnode.h"
25+
#include "server/serveractiveobjectmap.h"
2526
#include "settings.h"
2627
#include "util/numeric.h"
2728
#include <set>
@@ -193,8 +194,6 @@ enum ClearObjectsMode {
193194
This is not thread-safe. Server uses an environment mutex.
194195
*/
195196

196-
typedef std::unordered_map<u16, ServerActiveObject *> ServerActiveObjectMap;
197-
198197
class ServerEnvironment : public Environment
199198
{
200199
public:
@@ -254,18 +253,7 @@ class ServerEnvironment : public Environment
254253
*/
255254
u16 addActiveObject(ServerActiveObject *object);
256255

257-
/**
258-
* Verify if id is a free active object id
259-
* @param id
260-
* @return true if slot is free
261-
*/
262-
bool isFreeServerActiveObjectId(u16 id) const;
263-
264-
/**
265-
* Retrieve the first free ActiveObject ID
266-
* @return free activeobject ID or 0 if none was found
267-
*/
268-
u16 getFreeServerActiveObjectId();
256+
void updateActiveObject(ServerActiveObject *object);
269257

270258
/*
271259
Add an active object as a static object to the corresponding

‎src/unittest/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ set (UNITTEST_SRCS
2222
${CMAKE_CURRENT_SOURCE_DIR}/test_serialization.cpp
2323
${CMAKE_CURRENT_SOURCE_DIR}/test_settings.cpp
2424
${CMAKE_CURRENT_SOURCE_DIR}/test_socket.cpp
25+
${CMAKE_CURRENT_SOURCE_DIR}/test_serveractiveobjectmap.cpp
2526
${CMAKE_CURRENT_SOURCE_DIR}/test_servermodmanager.cpp
2627
${CMAKE_CURRENT_SOURCE_DIR}/test_threading.cpp
2728
${CMAKE_CURRENT_SOURCE_DIR}/test_utilities.cpp

‎src/unittest/test.h

+4
Original file line numberDiff line numberDiff line change
@@ -99,6 +99,10 @@ class TestFailedException : public std::exception {
9999
UASSERT(exception_thrown); \
100100
}
101101

102+
#define CONCAT_IMPL(x,y) x##y
103+
#define CONCAT(x,y) CONCAT_IMPL(x, y)
104+
#define NEWNAME(prefix) CONCAT(prefix, __COUNTER__)
105+
102106
class IGameDef;
103107

104108
class TestBase {

‎src/unittest/test_serveractiveobjectmap.cpp

+214
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,214 @@
1+
/*
2+
Minetest
3+
Copyright (C) 2018 nerzhul, Loic BLOT <loic.blot@unix-experience.fr>
4+
5+
This program is free software; you can redistribute it and/or modify
6+
it under the terms of the GNU Lesser General Public License as published by
7+
the Free Software Foundation; either version 2.1 of the License, or
8+
(at your option) any later version.
9+
10+
This program is distributed in the hope that it will be useful,
11+
but WITHOUT ANY WARRANTY; without even the implied warranty of
12+
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13+
GNU Lesser General Public License for more details.
14+
15+
You should have received a copy of the GNU Lesser General Public License along
16+
with this program; if not, write to the Free Software Foundation, Inc.,
17+
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18+
*/
19+
20+
#include "test.h"
21+
22+
#include "server/serveractiveobjectmap.h"
23+
#include "content_sao.h"
24+
25+
class TestServerActiveObjectMap : public TestBase
26+
{
27+
public:
28+
TestServerActiveObjectMap() { TestManager::registerTestModule(this); }
29+
const char *getName() { return "TestServerActiveObjectMap"; }
30+
31+
void runTests(IGameDef *gamedef);
32+
33+
void testAddObject();
34+
void testRemoveObject();
35+
void testUpdateObject();
36+
void testGetObject();
37+
void testIsFreeID();
38+
void testGetFreeID();
39+
void testGetObjectsInsideRadius();
40+
void testGetObjectsTouchingBox();
41+
};
42+
43+
static TestServerActiveObjectMap g_test_instance;
44+
45+
void TestServerActiveObjectMap::runTests(IGameDef *gamedef)
46+
{
47+
TEST(testAddObject);
48+
TEST(testRemoveObject);
49+
TEST(testUpdateObject);
50+
TEST(testGetObject);
51+
TEST(testIsFreeID);
52+
TEST(testGetFreeID);
53+
TEST(testGetObjectsInsideRadius);
54+
TEST(testGetObjectsTouchingBox);
55+
}
56+
57+
void TestServerActiveObjectMap::testAddObject()
58+
{
59+
ServerActiveObjectMap saom;
60+
UASSERT(saom.getObjects().empty());
61+
62+
LuaEntitySAO ob1(nullptr, v3f(0, 0, 0), "", "");
63+
ob1.setId(saom.getFreeId());
64+
saom.addObject(&ob1);
65+
66+
UASSERT(saom.getObjects().size() == 1);
67+
bool found = false;
68+
for (const auto &pair : saom.getObjects()) {
69+
UASSERT(pair.second.object == &ob1);
70+
found = true;
71+
}
72+
UASSERT(found);
73+
}
74+
75+
void TestServerActiveObjectMap::testRemoveObject()
76+
{
77+
ServerActiveObjectMap saom;
78+
UASSERT(saom.getObjects().empty());
79+
80+
LuaEntitySAO ob1(nullptr, v3f(0, 0, 0), "", "");
81+
ob1.setId(saom.getFreeId());
82+
saom.addObject(&ob1);
83+
84+
UASSERT(saom.getObjects().size() == 1);
85+
bool found = false;
86+
for (const auto &pair : saom.getObjects()) {
87+
UASSERT(pair.second.object == &ob1);
88+
found = true;
89+
}
90+
UASSERT(found);
91+
92+
saom.removeObject(&ob1);
93+
}
94+
95+
void TestServerActiveObjectMap::testUpdateObject()
96+
{
97+
ServerActiveObjectMap saom;
98+
LuaEntitySAO ob1(nullptr, v3f(1, 0, 0), "", "");
99+
ob1.accessObjectProperties()->physical = true;
100+
ob1.setId(saom.getFreeId());
101+
saom.addObject(&ob1);
102+
UASSERT(saom.getObjectsInsideRadius(v3f(0, 0, 0), 2).size() == 1);
103+
UASSERT(saom.getObjectsInsideRadius(v3f(6, 0, 0), 2).size() == 0);
104+
ob1.setBasePosition(v3f(5, 0, 0));
105+
saom.updateObject(&ob1);
106+
UASSERT(saom.getObjectsInsideRadius(v3f(0, 0, 0), 2).size() == 0);
107+
UASSERT(saom.getObjectsInsideRadius(v3f(6, 0, 0), 2).size() == 1);
108+
}
109+
110+
void TestServerActiveObjectMap::testGetObject()
111+
{
112+
ServerActiveObjectMap saom;
113+
LuaEntitySAO ob1(nullptr, v3f(0, 0, 0), "", "");
114+
u16 id = saom.getFreeId();
115+
ob1.setId(id);
116+
saom.addObject(&ob1);
117+
UASSERT(saom.getObject(0) == nullptr);
118+
UASSERT(saom.getObject(id) == &ob1);
119+
UASSERT(saom.getObject(id + 1) == nullptr);
120+
}
121+
122+
void TestServerActiveObjectMap::testIsFreeID()
123+
{
124+
ServerActiveObjectMap saom;
125+
UASSERT(!saom.isFreeId(0));
126+
UASSERT(saom.isFreeId(1));
127+
UASSERT(saom.isFreeId(2));
128+
}
129+
130+
void TestServerActiveObjectMap::testGetFreeID()
131+
{
132+
ServerActiveObjectMap saom;
133+
u16 first_id = saom.getFreeId();
134+
UASSERT(first_id > 0);
135+
UASSERT(saom.getFreeId() > first_id);
136+
}
137+
138+
void TestServerActiveObjectMap::testGetObjectsInsideRadius()
139+
{
140+
ServerActiveObjectMap saom;
141+
#define ADD_OBJECT_IMPL(name, pos) \
142+
LuaEntitySAO name(nullptr, pos, "", ""); \
143+
name.accessObjectProperties()->physical = true; \
144+
name.setId(saom.getFreeId()); \
145+
saom.addObject(&name)
146+
#define ADD_OBJECT(pos) ADD_OBJECT_IMPL(NEWNAME(ob), pos)
147+
#define OBJECT_COUNT (saom.getObjectsInsideRadius(v3f(0, 0, 0), 5).size())
148+
149+
UASSERT(OBJECT_COUNT == 0);
150+
151+
ADD_OBJECT(v3f(0, 0, 0));
152+
UASSERT(OBJECT_COUNT == 1);
153+
154+
ADD_OBJECT(v3f(-1, -1, -1));
155+
UASSERT(OBJECT_COUNT == 2);
156+
157+
ADD_OBJECT(v3f(4.9, 0, 0));
158+
UASSERT(OBJECT_COUNT == 3);
159+
160+
ADD_OBJECT(v3f(5.1, 0, 0));
161+
UASSERT(OBJECT_COUNT == 3);
162+
163+
ADD_OBJECT(v3f(3, 3, 3));
164+
UASSERT(OBJECT_COUNT == 3);
165+
}
166+
167+
void TestServerActiveObjectMap::testGetObjectsTouchingBox()
168+
{
169+
ServerActiveObjectMap saom;
170+
171+
LuaEntitySAO ob1(nullptr, v3f(1 * BS, 0, 0), "", "");
172+
ob1.accessObjectProperties()->physical = true;
173+
// Collision boxes are in nodes, not in world units:
174+
ob1.accessObjectProperties()->collisionbox = {-1, -1, -1, 1, 1, 1};
175+
ob1.setId(saom.getFreeId());
176+
saom.addObject(&ob1);
177+
178+
LuaEntitySAO ob2(nullptr, v3f(1.5 * BS, 2.5 * BS, 0), "", "");
179+
ob2.accessObjectProperties()->physical = true;
180+
ob2.accessObjectProperties()->collisionbox = {-0.5, -0.5, -1, 3.5, 2, 1};
181+
ob2.setId(saom.getFreeId());
182+
saom.addObject(&ob2);
183+
184+
std::vector<u16> list;
185+
186+
list = saom.getObjectsTouchingBox(
187+
{2.1 * BS, -1.0 * BS, -1.0 * BS, 2.5 * BS, 1.0 * BS, 1.0 * BS});
188+
UASSERT(list.size() == 0);
189+
190+
// intersecting ob1
191+
list = saom.getObjectsTouchingBox(
192+
{1.9 * BS, -1.0 * BS, -1.0 * BS, 2.5 * BS, 1.0 * BS, 1.0 * BS});
193+
UASSERT(list.size() == 1 && list[0] == ob1.getId());
194+
195+
// intersecting ob2
196+
list = saom.getObjectsTouchingBox(
197+
{2.1 * BS, -1.0 * BS, -1.0 * BS, 2.5 * BS, 2.1 * BS, 1.0 * BS});
198+
UASSERT(list.size() == 1 && list[0] == ob2.getId());
199+
200+
// contained in ob1
201+
list = saom.getObjectsTouchingBox(
202+
{1.5 * BS, -0.1 * BS, -0.1 * BS, 1.9 * BS, 0.1 * BS, 0.1 * BS});
203+
UASSERT(list.size() == 1 && list[0] == ob1.getId());
204+
205+
// contains ob2
206+
list = saom.getObjectsTouchingBox(
207+
{0.9 * BS, 1.5 * BS, -5.0 * BS, 6.0 * BS, 20.0 * BS, 500.0 * BS});
208+
UASSERT(list.size() == 1 && list[0] == ob2.getId());
209+
210+
// intersecting both
211+
list = saom.getObjectsTouchingBox(
212+
{1.9 * BS, -1.0 * BS, -1.0 * BS, 2.5 * BS, 2.1 * BS, 1.0 * BS});
213+
UASSERT(list.size() == 2);
214+
}

‎util/travis/clang-format-whitelist.txt

+1-2
Original file line numberDiff line numberDiff line change
@@ -311,8 +311,7 @@ src/script/scripting_server.cpp
311311
src/script/scripting_server.h
312312
src/serialization.cpp
313313
src/serialization.h
314-
src/serveractiveobjectmap.cpp
315-
src/serveractiveobjectmap.h
314+
src/server/serveractiveobjectmap.cpp
316315
src/server.cpp
317316
src/serverenvironment.cpp
318317
src/serverenvironment.h

0 commit comments

Comments
 (0)
Please sign in to comment.