 |
Reimplemented spatial data structure in svn rev 9918. Copying commit message below. ======================================== The old data structure was fixed BSP tree, which splits the world bounds into 16 x 16 x 16 cells, with linked list of clipmodels attached to every cell (BSP leaf). Non-adaptive space subdivision and linked lists caused ClipModelsTouching(Moving)Bounds run slow due to cache/TLB misses. This new data structure idBoxOctree stores dynamic object/boxes of varying sizes. It is an octree, with every node (not only leaves) containing a list of objects in it. The tree is grown on demand: when a node gets more than 90 objects which are smaller than 25% of node box size, 8 sons are generated and small objects are pushed down to them. This allows the structure to naturally adapt to the shape and density of the particular map. The attached list of objects is stored as a linked list of 127-object chunks, which combines fast traversal of arrays and simple custom memory allocation. On Lucy's Quest first beta, I see the following improvement in timings: Fresh start (1 min): 9.62 -> 9.14 RunGameTic 1.16 -> 1.04 ProcessStimResponse 0.66 -> 0.63 ServiceEvents Savegame load (5 min): 7.82 -> 7.52 RunGameTic 1.09 -> 0.96 ProcessStimResponse 0.64 -> 0.62 ServiceEvents This map has a lot of AIs, each of them regularly sends visualStim to the others. In order to send visualStim, idClip query is done on a pretty large box. This stresses ClipModelsTouchingBounds function inside ProcessStimResponse. ======================================== Forum post: https://forums.thedarkmod.com/index.php?/topic/21389-growing-arrays-and-memory-allocation/&do=findComment&comment=473374 |
|
|
While investigating a crash of 0006225, I noticed that numSmall sometimes becomes negative. It is an independent issue of idBoxOctree implementation, which is caused by fast update. It turns out that occasionally fast update breaks numSmall value. I don't think it can cause any problems except for maybe some tiny performance issues. But better fix it of course =) r10246. Added assert in idBoxOctree + disabled full-scale validity checks. r10247. Disable fast update in idBoxOctree if object's level has changed. |
- Anonymous
