As part of OTC 1.0, we knew that battleList had issues for a while know (first issue raised about it on nov 2017, ironically by me):
When you have too many monsters in your battle list the fps drops drastically. Before creating an issue, please ensure: This is a bug in the software that resides in this repository, and not a supp...
github.com
I've felt tempted to compare some implementations of this module and understand (really understand) what was causing this.
Vanila OTC:
- Pick all creatures of screen with getSpectators
- Iterate all creatures adding them to array in a sorted way (depending on current sortType)
- Each change on Health we remove the creature and add it again in a sorted way (!!)
- Each change on Distance (local player) we sort everything from scratch (!!!!!)
- Each change on Distance (creature) we remove it and add it again in a sorted way (!!)
Comments: We are spending too much calculations, especially on distance case and the way we "insert in a sorted way" is basically iterating and trying to find the correct position, which has a cost around N/2 being N the size of array. Also everytime we need to recalculate the sort, we do M * N * log2(N) * C, where N is the number of creatures in the array, M being the number of movements and C being the number of corrections we need to perform in the array. It's easy to understand why this explodes so quickly;
OTC V8:
- Kondra started by throwing away all the events, except the onPositionChange
- 1) Pick all creatures (currently visible) of screen with getSpectatorsInRangeEx
- 2) Sort all creatures using quicksort [complexity of N * log2(N)]
- 3) Repeat 1 and 2 each 100 ms. (!!!)
- Each change on Distance (local player) we sort everything from scratch (!!!!!)
Comments: The idea started wrong, the biggest advantage in this case is
information, aka called "
entropy".
Throwing away all this information leave us with no choice than sort it from scratch every single time, but I believe this was intended as this is exacly the approach he chose (in 1, 2 and 3). We continue to spend the EXACT amount of calculations every single time the local player moves but we did had a significant improvement in the checkCreatures function by only asking for the getSpectators to give us the creatures that are currently visible in my zoom mode (which means if you zoom in, it will return you less creatures than vanila version). While this small improvement is good, by deleting the events, Kondra made the list worst than it was initially, since now NO MATTER WHAT we will recalculate 10 times per second, so our complexity would be something like this:
(R * (2N + N * log2(N)) + (M * (2N + N * log2(N))
The
first part is related to the automatic refreshes, being R the Ratio of refresh.
The second is related to movements of local player.
The good thing is that despite the mess, kondra actually had a lot of good ideas that he tried to put into practice in his code such as:
- Not considering creatures when zooming in (implemented successfully)
- Initiate the widgets in advance (implemented successfully)
- Instead of recalculating the array when you change from asc to sort we just iterate it backwards (implemented successfully)
- Use a simple counter instead of os.time() for Age. (implemented successfully)
- Overall code refactors (debatable)
- Limiting the number of creatures to be added (not implemented though we see some checks that indicate that he was trying to do this)
... and the most important one:
- When we have a zillion creatures in screen, we should limit the ratio of refresh.
But ok, you might be asking yourself now "why the hell I'm making those comparations?". Understanding the flaws is the only way to start making something better and while I have came up with a new implementation of my own, I want you all to understand the concepts and flaws because I hope someday someone improve my code even further as there are still some TODOs that needs to be concluded.
OTC 1.0: -- After pull
#24
- Pick all creatures of screen with getSpectators (planning to use v8 approach soon)
- Instead of creating one array (battleButtons) we create also one called (BinaryTree)
- 1) When adding a new creature, we do as usual but we also use binaryInsert to get the correct index in sorted order.
- Each change we use the information from the current event and also from our cache (battleButton) to locate the current index (using binary search) and update it (swaps). This lead us to the following scenarios:
- OnAppearing: We do as [1]
- OnDisappearing: BinarySearch to find the current index and swap to correct positions all next positions.
- OnHealthChange: BinarySearch to find current index and update it, also swaps to correct position all next or previous positions (depending if the health increased or decreased). Also we iterate the widgets to correct their visual localization.
- onPositionChange: If the localPlayer moves, we simply recalculate distance to every creature and use quickSort. If it's a creature moving, we search it by using binarySearch and swaps to correct position all next or previous positions (depending if the health increased or decreased).
Comments: While I still don't have implemented most of V8 ideas, by using binarySearch and Insertion we reduce the amount of time to search from N/2 (average) to Log2(N) (worst case). While this may sound strange to understand for people who are not from computer science, for 100 monsters it would mean 50 checks vs 7.
I could reduce this even further by instead of saving data on battleButton, actually saving the index of BinatryTree, this would make access time be constant (1 check).
The bad thing is that now I'm using 3 arrays (battlePanel, battleButtons and BinaryTree) instead of two but we could do further improvements to have the binarytree be actually our battlePanel if I'm not mistaken, but in this particular case our goal is to reduce processing and not memory.
I highly encourage you to test this rework, report issues and more importantly: understand the concepts and check the TODOs to see if you can make it better. This is an issue that has been going on for years now and took me several days to actually start understanding and rewritting it.
Any help is welcome, remember that this will be used by
all of us.
