Написал две системы поиска путей для hill. На видео можно увидеть их в действии.

A* используется для поиска путей жителей, его суть состоит в выборе наиболее выгодного пути на каждом шаге поиска используя эвристику (оценку расстояния до цели). Это эффективно по причине наличия у каждого жителя собственной цели. Алгоритм находит кратчайший путь от одной точки до другой, минимизируя обход игрового поля.

Flowfield используется для поиска путей бесов, его суть состоит в построении векторного поля, указывающего направление к ближайшей цели. Это эффективно поскольку у всех бесов одна общая цель. Достаточно построить всего одно поле и обновлять его при изменении объектов на карте. Цель каждого отдельного беса при этом не выбирается намеренно, она зависит от направления поля.