Метод реализации псевдореалистичного перемещения неигровых персонажей в открытых виртуальных мирах

На современном рынке игр с открытым миром существует запрос на правдоподобное, но управляемое поведение неигровых персонажей (NPS) при ограниченных вычислительных ресурсах. Существующие решения предлагают две крайности. Либо они перегружают систему попыткой полной симуляции, либо дают предсказуемые скриптовые паттерны. Цель работы – предложить метод псевдореалистичного перемещения NPC, заполняющий разрыв между этими крайностями. Метод основан на проверке достижимости появления NPC: используется матрица кратчайших расстояний между областями игрового мира. При входе игрока в область алгоритм выбирает тех неигровых персонажей, которые физически могли туда добраться с учетом прошедшего времени, заданной скорости и доступных маршрутов, что интерпретирует встречу как следствие скрытого перемещения, а не мгновенного появления. Частота встреч регулируется системой приоритетов. Разработчик может управлять редкостью отдельных персонажей без детальной симуляции их маршрутов. Выбор кандидатов ускоряется переупорядочением почти отсортированного списка, уменьшая стоимость повторных выборок при близких входных условиях. Эксперименты на сгенерированных графах показали, что время выполнения основной части алгоритма на стороне клиента остается в пределах миллисекунд при численности до 1000 NPC. Метод обеспечивает правдоподобие и контролируемость встреч при низкой нагрузке и может быть интегрирован в существующие системы для настройки сложности и баланса.

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. Шутов К.И., Акатьев Я.А., Лобанов А.А. Анализ особенностей поведения неигровых персонажей в виртуальных мирах. E-Scio. 2023;(3):140–154.

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