Też kiedyś się zastanawiałem jak to dokładnie działa, ale nigdy samemu nie próbowałem czegoś takiego napisać. Przede wszystkim pomyślałbym najpierw jak będą wyglądać mapy. Jeśli nie będzie map, które będą miały przejścia np. węższe niż 3 jednostki to bym prawdopodobnie próbował rozwiązywać kolizje dopiero w momencie kiedy nastąpią. Czyli:
1) znajdź ścieżkę do celu:
* jeśli cel nieosiągalny to jednostka zaczyna narzekać i się nie rusza
* jeśli osiągalny (jako obszar) ale samo pole jest zajęte to szukałbym pola najbliżej położonego, a jak będziemy się zbliżać do celu to raz jeszcze sprawdzić, czy pole faktycznie jest zajęte
* jeśli pole wolne to ścieżka bezpośrednio do tego pola
2) po znalezieniu ścieżki przesuwamy się po gridzie i badamy czy następne pole do którego chcemy iść nie będzie zajęte:
* jeśli nie to idziemy
* jeśli zajęte to jednostki między sobą muszą rozwiązać tę kolizję; przydałyby się jakieś reguły postępowania w różnych sytuacjach i według tych reguł rozwiązać kolizje np. poprzez dodanie jakiejś sekwencji ruchów do pola/pól obok, po jakimś czasie można odwrócić sekwencję i kontynuować drogę albo obliczyć nową ścieżkę od pola na którym skończyliśmy kolizję;
3) powtarzaj do momentu aż nie dojdziesz do wyznaczonego celu
Jeśli mapy będą zawierać jakieś wąskie przejścia, wąwozy, mosty, cokolwiek to:
1) można spróbować postępować jak wyżej przy czym należałoby dodać odpowiednie reguły przy przechodzeniu przez takie przejścia (np. tak, żeby zminimalizować czas przejścia wszystkich jednostek na drugą stronę); np. ustalić która strona ma pierwszeństwo i oszacować czas jak długo będą zajmowały przejście; po tym czasie jednostki z drugiej grupy skorzystałyby z szansy że przejście jest wolne, jeśli rzeczywiście jest
2) można by oznaczyć w edytorze takie wąskie przejścia i już przy liczeniu ścieżki brać pod uwagę, że będziemy przez nie przechodzić; wtedy jeśli akurat się zdarzy sytuacja że przejście będzie zajęte to podzielić ścieżkę na dwie części, idziemy do punktu przed przejściem, czekamy odpowiednią ilość czasu i kontynuujemy drogę drugą ścieżką / ewentualnie jeśli nie jest to jedyne przejście, a droga będzie wystarczająco długo zablokowana możemy szukać innej drogi; kolizje które by występowały w miejscach innych niż wąwozy rozwiązywać dopiero w momencie wystąpienia
3) podzielić mapę na obszary (logiczne) lub wyznaczyć pewien obszar dookoła jednostek; przy każdej zmianie liczby jednostek w obszarze sprawdzić czy wystąpi kolizja; jeśli tak to ją rozwiązać zanim wystąpi