Разминка для мозга

А* ?

Дочитал только до «Встала задача нахождения пути в толпе», не обессутьте.

Код попробуй прочитать. А лучше запустить, сразу всё поймешь.

Если чесно – ЯННП. В твоём коде я вообще не увидел поиска пути.

Я про это писал.

И ещё я не понял вот это

и выбирается вариант от меньших к большим

// я с андроида в кофейне)

поиска пути

Весь путь не нужен, т.к. ситуация постоянно меняется. Алгоритм принимает решение в текущей ситуации. Он не должен быть дальновидным.

И ещё я не понял вот это

Если точка х занята боец пытается пройти в точки 1, потом(если и они заняты) в 2,3 и 4. Если всё занято - стоит на месте и ждёт погоду с моря.

может графы или алгоритм А*, но если в толпе, то там все препятствия не статичны.

все препятствия не статичны.

Да. Поэтому с графами накладно получается.

Почему вам не нравится алгоритм A* и его производные? На маленьких картах даже с большим количеством перемещающихся персонажей базовый A* будет очень шустрый и экономичный.

ну тем не менее наверно это лучший вариант, просто придется при каждом шаге перестраивать граф, но зато он маленький, всего 9 вершин кажется, так что вполне пригодно.

В нём нет особо смысла, т.к. конечный путь всё равно не важен. Пример:

A*:  1          2             3
    @     $|            |    @    $             
@   @  ...$|   .......  |  ..%.....$  (% - прилёг)
 .  @ .   $|  @  @@   $$| @  @    $ 
  ....     |     @     $|    
Костыльный:
     1     |    2
    @     $|            |    @    $
@...@.....$|  @..@@...$$| @..%.....$
    @     $|     @     $|    @    $

Вам нужен минимакс, который будет действовать для всех ИИ. Тогда все ваши бойцы будут добигать до цели быстрее некуда.

Это как?

Почитай, вполне может сойти за решение

Поковыряю завтра.

https://en.wikipedia.org/wiki/Minimax

В кратце, составляется дерево всех возможных ходов (состояний мира) всех игроков в порядке их ходов (подразумевая, что игра может быть разумно смоделирована пошаговой моделью). В дререве ищется путь, соответствующий оптимальному поведению в узле того, чей ход в этом узле. Если дерево получается очень большим (бесконечным), например, как в этом случае, то можно прервать вычисление дерева на некоторой глубине, например, n. И для каждого из этих состояний (т.е. все состояния мира через n ходов) вычислить приближенное значение каким-либо способом, например A*.

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

Да используй ты A* с эвристикой. Можешь, например не просчитывать его до конца, а обрывать после n-ой итерации и брать наилучший вариант из подсчитанных им.