The open-world game market increasingly demands NPC (non-player character) behaviour that feels believable yet remains designer-controllable under tight computational budgets. Common solutions tend to be extreme: either they attempt full simulation and overload the system, or they rely on predictable scripted patterns. This paper proposes a pseudo-realistic NPC movement method that bridges these extremes. The core idea is to verify spawn reachability using a matrix of shortest-path distances between world areas. When the player enters an area, the algorithm selects only those NPCs that could have physically reached it given elapsed time, movement speed and available routes, making an encounter consistent with hidden travel rather than instantaneous spawning. Encounter frequency is controlled via a priority scheme, allowing designers to tune event density and the rarity of specific characters without maintaining a detailed simulation. Candidate selection is further accelerated by reordering an almost-sorted list, reducing the cost of repeated queries under similar conditions. Experiments on synthetic graphs show that the core client-side runtime stays within milliseconds for up to 1000 NPCs. The method delivers believability and control at low computational cost and can be integrated into existing engines to adjust difficulty and balance.
1. Uludağlı M.Ç., Oğuz K. Non-player character decision-making in computer games. Artificial Intelligence Review. 2023;56(12):14159–14191. https://doi.org/10.1007/s10462-023-10491-7
2. Da Silva G.A., de Souza Ribeiro M.W. Development of Non-Player Character with Believable Behavior: a systematic literature review. In: 2021: Companion Proceedings of the 20th Brazilian Symposium on Games and Digital Entertainment, 18–21 October 2021, Gramado, Brazil. Porto Alegre: Sociedade Brasileira de Computação; 2021. P. 319–323. https://doi.org/10.5753/sbgames_estendido.2021.19660
3. Yang D., Kleinman E., Harteveld C. GPT for Games: An Updated Scoping Review (2020–2024). arXiv. URL: https://arxiv.org/abs/2411.00308 [Accessed 5th October 2025].
4. Yakan S.A. Analysis of Development of Artificial Intelligence in the Game Industry. International Journal of Cyber and IT Service Management. 2022;2(2):111–116. https://doi.org/10.34306/ijcitsm.v2i2.100
5. Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. Cambridge: MIT Press; 2022. 1312 p.
6. Shutov K.I., Akatiev Ya.A., Lobanov A.A. Analysis of the behavior of non-player characters in virtual worlds. E-Scio. 2023;(3):140–154. (In Russ.).
7. Guimarães M., Santos P.A., Jhala A. Emergent Social NPC Interactions in the Social NPCs Skyrim Mod and Beyond. arXiv. URL: https://doi.org/10.48550/arXiv.2207.13398 [Accessed 3rd October 2025].
8. Park J.S., O'Brien J., Cai C.J., et al. Generative Agents: Interactive Simulacra of Human Behavior. In: UIST '23: Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, 29 October – 01 November 2023, San Francisco, CA, USA. New York: ACM; 2023. https://doi.org/10.1145/3586183.3606763
9. Guo S., Adamo N., Mousas Ch. Developing a Scale for Measuring the Believability of Virtual Agents. In: ICAT-EGVE 2023: 33rd International Conference on Artificial Reality and Telexistence, 28th Eurographics Symposium on Virtual Environments, 06–08 December 2023, Trinity College Dublin, Ireland. Eurographics Association; 2023. P. 45–52. https://doi.org/10.2312/egve.20231312
10. Sprevak M., Smith R. An Introduction to Predictive Processing Models of Perception and Decision-Making. Topics in Cognitive Science. 2023. https://doi.org/10.1111/tops.12704
11. Clark A. The Experience Machine: How Our Minds Predict and Shape Reality. New York: Pantheon Books; 2023. 320 p.
12. Bai X., Coester Ch. Sorting with Predictions. In: Advances in Neural Information Processing Systems 36 (NeurIPS 2023), 10–16 December 2023, New Orleans, LA, USA. 2023. URL: https://papers.neurips.cc/paper_files/paper/2023/file/544696ef4847c903376ed6ec58f3a703-Paper-Conference.pdf
13. Durrani O.Kh., AbdulHayan S. Performance Measurement of Popular Sorting Algorithms Implemented using Java and Python. In: 2022 International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME), 16–18 November 2022, Maldives. IEEE; 2022. P. 1–6. https://doi.org/10.1109/ICECCME55909.2022.9988424
14. Michail D. JHeaps: An open-source library of priority queues. SoftwareX. 2021;16. https://doi.org/10.1016/j.softx.2021.100869
15. Mubarak A., Iqbal S., Naeem T., Hussain Sh. 2 mm: A new technique for sorting data. Theoretical Computer Science. 2022;910:68–90. https://doi.org/10.1016/j.tcs.2022.01.037
16. Auger N., Jugé V., Nicaud C., Pivoteau C. On the Worst-Case Complexity of TimSort. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), 20–22 August 2018, Helsinki, Finland. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2018. https://doi.org/10.4230/LIPIcs.ESA.2018.4
Shutov Kirill Igorevich
MIREA – Russian Technological University
Moscow, Russian Federation
Lobanov Aleksandr Anatolyevich
Candidate of Engineering Sciences, Docent
MIREA – Russian Technological University
Moscow, Russian Federation
