Adaptive Broad-Phase Collision Detection in Unity Using Thompson Sampling

Raul Costa Feitosa; Maria Andréia
 Formico Rodrigues

doi:10.5753/sbgames.2026.25550

Raul Costa Feitosa UNIFOR
Maria Andréia Formico Rodrigues UNIFOR

DOI: https://doi.org/10.5753/sbgames.2026.25550

Resumo

Introduction: Broad-phase collision detection strongly affects frame rate, memory use, and responsiveness in games and interactive simulations. However, the best strategy depends on runtime conditions such as object count, spatial distribution, and motion. Objective: To present an adaptive mechanism that selects broad-phase collision detection algorithms at runtime using Thompson Sampling. Methodology: The system was implemented as a Unity plugin linked to a native broad-phase library containing Brute Force, Grid, SAP, AxisSweep, DBVT, Tracy, and KDTree. Selection uses a multi-metric reward based on FPS, detection time, memory use, and Axis-Aligned Bounding Box (AABB) checks, together with adaptive FPS normalization, cooldown control, and post-switch stabilization. Evaluation covered Brownian Motion, Rotating Gravity, and Hurricane scenarios with 1,000, 2,000, and 3,000 heterogeneous dynamic objects. Results: Across five runs per condition, AxisSweep dominated Brownian Motion with 1,000–2,000 objects and Hurricane with up to 2,000 objects. KDTree dominated Hurricane and Rotating Gravity with 3,000 objects, while Brownian Motion with 3,000 objects and Rotating Gravity with 1,000 objects showed mixed dominance. Results suggest that Thompson Sampling is a promising strategy for adaptive broad-phase selection, especially in workloads where the best spatial data structure changes.

Palavras-chave: Broad-Phase Collision Detection, Spatial Data Structures, Thompson Sampling, Multi-Armed Bandits, Game Physics, Runtime Adaptation

Referências

Avril, Q., Gouranton, V., and Arnaldi, B. (2014). Collision Detection: Broad Phase Adaptation from Multi-Core to Multi-GPU Architecture. Virtual Reality and Broadcasting, 6(11):1–13.

Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learn., 5(1):1–122.

Capannini, G. and Larsson, T. (2017). Adaptive collision culling for massive simulations by a parallel and context-aware sweep and prune algorithm. IEEE Transactions on Visualization and Computer Graphics, 24(7):2064–2077.

Chapelle, O. and Li, L. (2011). An empirical evaluation of Thompson sampling. In Advances in NeurIPS, volume 24, pages 2249–2257.

Coumans, E. (2018). Bullet physics library 2.88. [link].

Ericson, C. (2004). Real-Time Collision Detection. Morgan Kaufmann.

Feitosa, R. C. (2026). Adaptive Broad-Phase Collision Detection in Unity: A Plugin-Based Framework for AI-Assisted Algorithm Selection. Master’s thesis, PPGIA - Universidade de Fortaleza, Fortaleza, CE, Brazil. [link].

Kopta, D., Ize, T., Spjut, J., Brunvand, E., Davis, A., and Kensler, A. (2012). Fast, effective BVH updates for animated scenes. In Proc. of the SIGGRAPH Symposium on I3D, page 197–204, NY, USA. ACM.

Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.

Liu, F., Harada, T., Lee, Y., and Kim, Y. (2010). Real-time Collision Culling of a Million Bodies on Graphics Processing Units. ACM ToG, 29:154.

Lo, S.-H., Lee, C.-R., Chung, I.-H., and Chung, Y.-C. (2013). Optimizing Pairwise Box Intersection Checking on GPUs for Large-Scale Simulations. ACM Transactions on Modeling and Computer Simulation (TOMACS), 23:19:1–19:22.

NVIDIA (2019). Physx 4.1. [link].

Rice, J. R. (1976). The algorithm selection problem. Advances in Computers, 15:65–118.

Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., and Wen, Z. (2018). A tutorial on Thompson Sampling. Foundations and Trends in Machine Learning, 11(1):1–96.

Serpa, Y. R. and Rodrigues, M. A. F. (2019). Flexible use of temporal and spatial reasoning for fast and scalable CPU broad-phase collision detection using KD-Trees. Computer Graphics Forum, 38(1):260–273. DOI: 10.1111/cgf.13529.

Serpa, Y. R. and Rodrigues, M. A. F. (2020). Broadmark: A testing framework for broad-phase collision detection algorithms. Computer Graphics Forum, 39(1):436– 449. DOI: 10.1111/cgf.13884.

Terdiman, P. (2017). Physics Engine Evaluation Lab (PEEL). [link].

Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3–4):285–294.

Tornede, A., Bengs, V., and Hüllermeier, E. (2022). Machine learning for online algorithm selection under censored feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8417–8424.

Tracy, D., Buss, S., and Woods, B. (2009). Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal. IEEE Virtual Reality, pages 191–198.

Woulfe, M. and Manzke, M. (2009). A framework for benchmarking interactive collision detection. In Proceedings of the 25th SCCG’09, pages 205–212, NY, USA. ACM.