View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0009397||New Feature Requests||[All Projects] General||public||2016-09-25 22:18||2017-09-05 20:18|
|Summary||0009397: [REQUEST]: Add possibility to specify searchable elements for colshape|
I want to suggest small optimization for colshape collision-search mechanism.
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.
|Tags||No tags attached.|
|Users sponsoring this issue|
Total Sponsorship = EUR 50
2017-09-03 16:51: haron4igg (EUR 50)
make list with all your elements and your own function to check collision
Lua has low performance for doing such things.
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).
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.