a* kollision der einheiten

[krys001]

Hallo, habe gerade für ein Uni Projekt einen A* algorithmus implementiert für einheiten die von einem startpunkt losgehen, zu einem variablen zielpunkt gehen eine ressource sammeln und diese wieder zum startpunkt transportieren.

Mein problem an der stelle ist aber das z.B. wenn eine einheit mit einer ressource zum startpunkt geht, eine andere vom startpunkt einen zielpunkt in der nähe anpeilt dann kann es vorkommen das sie den gleichen weg gehen und irgentwann sich im weg stehen. die folge ist (da sich alle einheiten gleichzeitig bewegen müssen) das sie nur noch hin und her laufen und iren weg nichtmehr verfolgen können.
Bewegt wird sich auf einem 2-Dimensinalen Grid ohne diagonale züge.
Ich habe probiert die wegkosten für in auf dem weg befindliche figuren zu erhöhen, das hat aber nur bedingt geholfen.

Weis jemand Rat?

 

[Jardcore]

Hey krys001,

dafür musst du dir eine bestimmte Strategie ausdenken.
Beispielsweise könntest du eine zusätzliche Rangfolge ausdenken von der abhängt wer sich als nächstes bewegen darf.
Dadurch würde eine Figur stehen bleiben und die anderen vorbei ziehen. Als Erweiterung könnte ich mir vorstellen, dass die wartende Figur in der Rangfolge für jede Zeiteinheit aufsteigt. Dann könnte sie sich nach einiger Zeit weiter bewegen und andere Figuren müssten warten.
Wenn nun eine Rettungsarztfigur kommt^^ würde die natürlich mit Prio 1 durchrauschen

In diesem Video sieht man auch ganz gut die stehen bleibe Taktik:

Beste Grüße,
Jar

 

[dayaftereh]

Du könntest dir überlegen einen neu Planung zu machen falls gerade das eine Grid Feld von einer Einheit blockiert wird. Das heißt immer nur eine Einheit darf auf ein Feld, falls dort mehrere Pfade von anderen Einheiten durch geht, müssen die dann ihren Weg neu planen. Falls es keinen Weg gibt, bleibt die Einheit stehen. Schau dir mal den D* Lite an. Der plannt effektive und Resourcen schonend neu.

 

[krys001]

Vielen Dank!! ^^
Hat mir sehr geholfen, den D* hab ich noch nicht implementiert aber sieht sehr interessant aus, der würde glaub ich das ganze noch etwas optimieren