На современном рынке игр с открытым миром существует запрос на правдоподобное, но управляемое поведение неигровых персонажей (NPS) при ограниченных вычислительных ресурсах. Существующие решения предлагают две крайности. Либо они перегружают систему попыткой полной симуляции, либо дают предсказуемые скриптовые паттерны. Цель работы – предложить метод псевдореалистичного перемещения NPC, заполняющий разрыв между этими крайностями. Метод основан на проверке достижимости появления NPC: используется матрица кратчайших расстояний между областями игрового мира. При входе игрока в область алгоритм выбирает тех неигровых персонажей, которые физически могли туда добраться с учетом прошедшего времени, заданной скорости и доступных маршрутов, что интерпретирует встречу как следствие скрытого перемещения, а не мгновенного появления. Частота встреч регулируется системой приоритетов. Разработчик может управлять редкостью отдельных персонажей без детальной симуляции их маршрутов. Выбор кандидатов ускоряется переупорядочением почти отсортированного списка, уменьшая стоимость повторных выборок при близких входных условиях. Эксперименты на сгенерированных графах показали, что время выполнения основной части алгоритма на стороне клиента остается в пределах миллисекунд при численности до 1000 NPC. Метод обеспечивает правдоподобие и контролируемость встреч при низкой нагрузке и может быть интегрирован в существующие системы для настройки сложности и баланса.
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.
The authors declare that there are no conflicts of interest present.