-
Notifications
You must be signed in to change notification settings - Fork 0
Test THST on keeperfx for querying nearby creatures
To address https://github.com/Linvail/keeperfx/issues/3, I want to incorporate THST.
THST: Templated hierarchical spatial trees designed for high-performance and hierarchical spatial partitioning use cases.
https://github.com/tuxalin/THST
- Use THST to build an R-tree of creatures at every turn.
- Use THST to query the nearest creatures in the visual range of the specified creature.
- Cache the above results in one game turn. The results can be used for different ranged buffs and different locations of code.
- Player 0: 10 Avatars, 10 Vampires, 10 Druids, 10 Dark mistresses, 50 Imps. Imps are level 1, the others are level 10.
- Player 1: 50 Imps. Imps are level 1.
- Player 2: 10 Warlocks, 10 Witches, 10 Druids, 10 Wizards, 50 Imps. Imps are level 1, the others are level 10.
- Hero player: 5 Druids, 5 Witches, 5 Wizards, 5 Archers, 5 Time Mages, 5 Fairies, 10 Monks. All are level 10.
270 creatures in total.
- Druid is granted RANGED_HEAL.
- Wizard is granted RANGED_REBOUND and RANGED_HEAL.
- Time Mage is granted RANGED_SPEED.
Measure the elapsed time of update() function in main.cpp (within gameplay_loop_logic()).
Calculate the average among a period of time.
During game turn 100 ~ 1600 (total 1500 turns).
- CPU 12th Gen Intel(R) Core(TM) i5-12500
- 32 GB RAM
Built in development mode, no optimization.
Base commit Id: 6e617711db88f9e72343a203946bdb048618e062 (development branch of Linvail/keeperfx)
Before the change, the average time spent is 6690 (in microseconds).
After the change, the average is 5541 (in microseconds).
Roughly 17.17% improvement.
If more creatures get ranged buff skills, the improvement will be greater.