Skip to content

Commit e8ac5a3

Browse files
nerzhulnerzhul
authoredApr 16, 2020
Optimize get_objects_inside_radius calls (#9671)
* Optimize getObjectsInsideRadius calls our previous implementation calls the ActiveObjectMgr to return ids and then lookup those ids in the same map and test each object Instead now we call the global map to return the pointers directly and we ask filtering when building the list using lamba. This drop double looping over ranges of active objects (and then filtered one) and drop x lookups on the map regarding the first call results
·
5.11.05.3.0
1 parent 62ae7ad commit e8ac5a3

File tree

7 files changed

+55
-39
lines changed

7 files changed

+55
-39
lines changed
 

‎src/collision.cpp

+11-9
Original file line numberDiff line numberDiff line change
@@ -360,17 +360,19 @@ collisionMoveResult collisionMoveSimple(Environment *env, IGameDef *gamedef,
360360
// Calculate distance by speed, add own extent and 1.5m of tolerance
361361
f32 distance = speed_f->getLength() * dtime +
362362
box_0.getExtent().getLength() + 1.5f * BS;
363-
std::vector<u16> s_objects;
364-
s_env->getObjectsInsideRadius(s_objects, *pos_f, distance);
365363

366-
for (u16 obj_id : s_objects) {
367-
ServerActiveObject *current = s_env->getActiveObject(obj_id);
368-
369-
if (!self || (self != current &&
370-
self != current->getParent())) {
371-
objects.push_back((ActiveObject*)current);
364+
// search for objects which are not us, or we are not its parent
365+
// we directly use the callback to populate the result to prevent
366+
// a useless result loop here
367+
auto include_obj_cb = [self, &objects] (ServerActiveObject *obj) {
368+
if (!self || (self != obj && self != obj->getParent())) {
369+
objects.push_back((ActiveObject *)obj);
372370
}
373-
}
371+
return false;
372+
};
373+
374+
std::vector<ServerActiveObject *> s_objects;
375+
s_env->getObjectsInsideRadius(s_objects, *pos_f, distance, include_obj_cb);
374376
}
375377
}
376378

‎src/script/lua_api/l_env.cpp

+12-12
Original file line numberDiff line numberDiff line change
@@ -681,22 +681,22 @@ int ModApiEnvMod::l_get_player_by_name(lua_State *L)
681681
int ModApiEnvMod::l_get_objects_inside_radius(lua_State *L)
682682
{
683683
GET_ENV_PTR;
684+
ScriptApiBase *script = getScriptApiBase(L);
684685

685686
// Do it
686687
v3f pos = checkFloatPos(L, 1);
687688
float radius = readParam<float>(L, 2) * BS;
688-
std::vector<u16> ids;
689-
env->getObjectsInsideRadius(ids, pos, radius);
690-
ScriptApiBase *script = getScriptApiBase(L);
691-
lua_createtable(L, ids.size(), 0);
692-
std::vector<u16>::const_iterator iter = ids.begin();
693-
for(u32 i = 0; iter != ids.end(); ++iter) {
694-
ServerActiveObject *obj = env->getActiveObject(*iter);
695-
if (!obj->isGone()) {
696-
// Insert object reference into table
697-
script->objectrefGetOrCreate(L, obj);
698-
lua_rawseti(L, -2, ++i);
699-
}
689+
std::vector<ServerActiveObject *> objs;
690+
691+
auto include_obj_cb = [](ServerActiveObject *obj){ return !obj->isGone(); };
692+
env->getObjectsInsideRadius(objs, pos, radius, include_obj_cb);
693+
694+
int i = 0;
695+
lua_createtable(L, objs.size(), 0);
696+
for (const auto obj : objs) {
697+
// Insert object reference into table
698+
script->objectrefGetOrCreate(L, obj);
699+
lua_rawseti(L, -2, ++i);
700700
}
701701
return 1;
702702
}

‎src/server/activeobjectmgr.cpp

+6-4
Original file line numberDiff line numberDiff line change
@@ -111,17 +111,19 @@ void ActiveObjectMgr::removeObject(u16 id)
111111
}
112112

113113
// clang-format on
114-
void ActiveObjectMgr::getObjectsInsideRadius(
115-
const v3f &pos, float radius, std::vector<u16> &result)
114+
void ActiveObjectMgr::getObjectsInsideRadius(const v3f &pos, float radius,
115+
std::vector<ServerActiveObject *> &result,
116+
std::function<bool(ServerActiveObject *obj)> include_obj_cb)
116117
{
117118
float r2 = radius * radius;
118119
for (auto &activeObject : m_active_objects) {
119120
ServerActiveObject *obj = activeObject.second;
120-
u16 id = activeObject.first;
121121
const v3f &objectpos = obj->getBasePosition();
122122
if (objectpos.getDistanceFromSQ(pos) > r2)
123123
continue;
124-
result.push_back(id);
124+
125+
if (!include_obj_cb || include_obj_cb(obj))
126+
result.push_back(obj);
125127
}
126128
}
127129

‎src/server/activeobjectmgr.h

+3-2
Original file line numberDiff line numberDiff line change
@@ -35,8 +35,9 @@ class ActiveObjectMgr : public ::ActiveObjectMgr<ServerActiveObject>
3535
bool registerObject(ServerActiveObject *obj) override;
3636
void removeObject(u16 id) override;
3737

38-
void getObjectsInsideRadius(
39-
const v3f &pos, float radius, std::vector<u16> &result);
38+
void getObjectsInsideRadius(const v3f &pos, float radius,
39+
std::vector<ServerActiveObject *> &result,
40+
std::function<bool(ServerActiveObject *obj)> include_obj_cb);
4041

4142
void getAddedActiveObjectsAroundPos(const v3f &player_pos, f32 radius,
4243
f32 player_radius, std::set<u16> &current_objects,

‎src/serverenvironment.cpp

+5-7
Original file line numberDiff line numberDiff line change
@@ -1608,14 +1608,12 @@ void ServerEnvironment::getSelectedActiveObjects(
16081608
const core::line3d<f32> &shootline_on_map,
16091609
std::vector<PointedThing> &objects)
16101610
{
1611-
std::vector<u16> objectIds;
1612-
getObjectsInsideRadius(objectIds, shootline_on_map.start,
1613-
shootline_on_map.getLength() + 10.0f);
1611+
std::vector<ServerActiveObject *> objs;
1612+
getObjectsInsideRadius(objs, shootline_on_map.start,
1613+
shootline_on_map.getLength() + 10.0f, nullptr);
16141614
const v3f line_vector = shootline_on_map.getVector();
16151615

1616-
for (u16 objectId : objectIds) {
1617-
ServerActiveObject* obj = getActiveObject(objectId);
1618-
1616+
for (auto obj : objs) {
16191617
aabb3f selection_box;
16201618
if (!obj->getSelectionBox(&selection_box))
16211619
continue;
@@ -1630,7 +1628,7 @@ void ServerEnvironment::getSelectedActiveObjects(
16301628
if (boxLineCollision(offsetted_box, shootline_on_map.start, line_vector,
16311629
&current_intersection, &current_normal)) {
16321630
objects.emplace_back(
1633-
(s16) objectId, current_intersection, current_normal,
1631+
(s16) obj->getId(), current_intersection, current_normal,
16341632
(current_intersection - shootline_on_map.start).getLengthSQ());
16351633
}
16361634
}

‎src/serverenvironment.h

+3-2
Original file line numberDiff line numberDiff line change
@@ -323,9 +323,10 @@ class ServerEnvironment : public Environment
323323
bool swapNode(v3s16 p, const MapNode &n);
324324

325325
// Find all active objects inside a radius around a point
326-
void getObjectsInsideRadius(std::vector<u16> &objects, const v3f &pos, float radius)
326+
void getObjectsInsideRadius(std::vector<ServerActiveObject *> &objects, const v3f &pos, float radius,
327+
std::function<bool(ServerActiveObject *obj)> include_obj_cb)
327328
{
328-
return m_ao_manager.getObjectsInsideRadius(pos, radius, objects);
329+
return m_ao_manager.getObjectsInsideRadius(pos, radius, objects, include_obj_cb);
329330
}
330331

331332
// Clear objects, loading and going through every MapBlock

‎src/unittest/test_serveractiveobjectmgr.cpp

+15-3
Original file line numberDiff line numberDiff line change
@@ -148,14 +148,26 @@ void TestServerActiveObjectMgr::testGetObjectsInsideRadius()
148148
saomgr.registerObject(new TestServerActiveObject(p));
149149
}
150150

151-
std::vector<u16> result;
152-
saomgr.getObjectsInsideRadius(v3f(), 50, result);
151+
std::vector<ServerActiveObject *> result;
152+
saomgr.getObjectsInsideRadius(v3f(), 50, result, nullptr);
153153
UASSERTCMP(int, ==, result.size(), 1);
154154

155155
result.clear();
156-
saomgr.getObjectsInsideRadius(v3f(), 750, result);
156+
saomgr.getObjectsInsideRadius(v3f(), 750, result, nullptr);
157157
UASSERTCMP(int, ==, result.size(), 2);
158158

159+
result.clear();
160+
saomgr.getObjectsInsideRadius(v3f(), 750000, result, nullptr);
161+
UASSERTCMP(int, ==, result.size(), 5);
162+
163+
result.clear();
164+
auto include_obj_cb = [](ServerActiveObject *obj) {
165+
return (obj->getBasePosition().X != 10);
166+
};
167+
168+
saomgr.getObjectsInsideRadius(v3f(), 750000, result, include_obj_cb);
169+
UASSERTCMP(int, ==, result.size(), 4);
170+
159171
clearSAOMgr(&saomgr);
160172
}
161173

1 commit comments

Comments
 (1)

oilboi commented on Apr 17, 2020

@oilboi
oilboi
on Apr 17, 2020
Contributor

This is extremely helpful, thank you

Please sign in to comment.