Многие наверное помнят, как ведут себя мобы в ваниле и нпс в легаси версии, порой, ради того, чтобы нпс дошёл до точки приходилось чуть ли не гору снести... Поэтому в 2.0 я занялся доработкой алгоритма поиска пути. Minecraft использует модифицированный алгоритм A* (читается как AStar).

🔍 Как он работает?

1️⃣ Алгоритм начинает с стартовой точки (А), а именно позиции нпс и добавляет её в список "мест, которые нужно проверить".

2️⃣ A* смотрит на соседние блоки вокруг этой точки. Он оценивает каждый блок по двум параметрам:

Пройденное расстояние — сколько блоков алгоритм уже прошёл от начальной точки.

Цена достижения цели — каждое действие имеет свою "цену", например при передвижении по воде эта "цена" больше, потому что плыть медленнее, чем идти. Поэтому когда между нпс и его целью есть озеро, нпс вероятно предпочтёт пройти по земле, если итоговое время ходьбы пешком будет меньше, чем если он его проплывёт.

3️⃣ В процессе работы, A* выбирает путь, который сочетает минимальное пройденное расстояние (количество блоков) и самую низкую цену до финиша (наиболее выгодные блоки).

4️⃣ Алгоритм повторяет шаги 2 и 3, пока не дойдёт до финиша. Если упёрся в стену или в тупик, A* продолжает поиск за счёт других соседних блоков.

5️⃣ Когда алгоритм доберётся до финиша, он соберёт самый оптимальный маршрут.

🤔Ну и собственно что я изменил в этом алгоритме, чтобы мобы не тупили?

1️⃣Повысил глубину поиска с 16 блоков (нпс раньше могли думать не больше, чем на 16 шагов вперёд :D) до 128. Скорее всего в будущем добавлю настройку приоритетов, ведь чем больше вариантов пути сможет просмотреть нпс, тем больше будет нагрузка на сервер.

2️⃣При поиске соседних блоков добавил к соседям также блоки, на которые нпс может запрыгнуть с текущего. А также сделал их "цену" выше, чем "цену" ходьбы, хотя как наверное многие знают, в прыжках ты перемещаешься быстрее, чем ходьбой. Но вряд ли вам бы понравилось, если бы нпс всё время прыгал от точки к точке :D 

Вот и всё! Теперь ты знаешь, как работает этот алгоритм поиска пути, а я пошёл учить нпс, ломать и ставить блоки, а также воровать предметы из ваших сундуков...