View Issue Details

IDProjectCategoryView StatusLast Update
0009397New Feature Requests[All Projects] Generalpublic2017-09-05 20:18
Reporterharon4iggAssigned To 
PrioritynormalSeverityfeatureReproducibilityN/A
Status newResolutionopen 
Summary0009397: [REQUEST]: Add possibility to specify searchable elements for colshape
Description

Hi,

I want to suggest small optimization for colshape collision-search mechanism.
lets call it:

setColShapeCollisionTarget(colshape, root/parent/elementList/element)

The idea is to reduce search-range for colshape if you moving it and vise-versa, if you have a lot of colshapes and you move the element.

For example, you have about 10 000 physical elements on map, you are moving colshape, and you have only 100 elements on map which should be detected by this colshape.
In current implementation, colshape on server side runs 10000 range-checks for each position change, which is pretty noticeable on server performance.

TagsNo tags attached.

Users sponsoring this issue
Sponsors List Total Sponsorship = EUR 50

2017-09-03 16:51: haron4igg (EUR 50)
Users sponsoring this issue (Total Sponsorship = EUR 50)

Activities

CrosRoad95

2017-09-03 17:23

viewer   ~~0026192

make list with all your elements and your own function to check collision

haron4igg

2017-09-05 19:39

viewer   ~~0026197

Lua has low performance for doing such things.

Jusonex

2017-09-05 19:57

administrator   ~~0026198

Last edited: 2017-09-05 19:57

View 2 revisions

In current implementation, colshape on server side runs 10000 range-checks for each position change

That's not the case. It uses an RTree (https://en.wikipedia.org/wiki/R-tree) internally. It's similar to a binary tree, but extends it by a spatial component.

Wikipedia says it's average case complexity is O(log_M(n)), where M=8 (in MTA's implementation) and n is the number of elements in the list. That means in an average case of 10000 elements, we've to do only log_M(10000)=4.4 checks - that's not much.

Introducing setColShapeCollisionTarget will ofc reduce the number of elements to check. However, the RTree is shared among all colshapes, so introducing setColShapeCollisionTarget will require either adding extra checks to the tree (which make it slower) or generating trees per colshape (which leads to more memory consumption and sometimes more CPU load).
In conclusion, such a function will speed up or slow down collision detection depending on the amount of elements in the list.

haron4igg

2017-09-05 20:18

viewer   ~~0026199

I see, but the memory consumption is not the issue for such kind of data... building separate tree across 'Target' objects will be the perfect solution here. It's up to developer to decide what is the priority CPU or Memory. And if my server will require more memory to save CPU - i will just extend the configuration. But currently i have no way to save CPU.

Issue History

Date Modified Username Field Change