Kürzlich habe ich begonnen, einen Spielprototyp zu entwickeln, mit dem prozedural generierte Dungeons unter Verwendung einer Sammlung von Raumtypen erstellt werden können. Um sicherzustellen, dass die Flurwege zwischen diesen Räumen immer verbunden sind, habe ich einen A * -Pfad-Suchalgorithmus implementiert, der der Kachelkarte zufällig platzierter Räume folgt.
Das Problem dabei ist jedoch, dass ich nicht unbedingt versucht habe, den kürzesten Weg zwischen Räumen zu finden, der in den meisten Fällen eine Diagonale wäre. Da sie thematisch ein "Dungeon" sind, wollte ich, dass sie sich in einem Winkel von 90 Grad drehen und drehen. Durch die Verwendung einer Manhattan-Distanz für die Heuristik habe ich es geschafft, die beabsichtigte Form zu erhalten, aber ich habe ein letztes Problem, bei dem ich zu euch freundlichen Leuten komme, um mir zu helfen :).
Obwohl jetzt 90-Grad-Winkel zum Verschieben des Pfads verwendet werden, wird der Lauf bis zum Ende des Pfads gespeichert (siehe Abbildung unten). Dadurch fühlt sich das Ganze in einiger Entfernung an einigen Stellen eng an, anstatt den gesamten Raum effektiv zu nutzen. Angesichts der Tatsache, dass das einfache Ändern der Heuristik von Entfernung zu Entfernung in Manhattan einen Unterschied gemacht hat, ist meine Frage: Gibt es eine Kostenfunktion, die ich implementieren könnte, um die gewünschten Ergebnisse dieses nicht konventionellen Pfades zu erzielen? Alle Antworten wäre dankbar, danke.
Hinweis: Der Algorithmus hat auch Zugriff auf die normale Richtung der Start- und Endziele.
quelle
Antworten:
Ihr Problem ist einfach und als solches auch die Lösung. Was Sie im Wesentlichen wollen, ist, dass Ihr A * für jede Zeit, in der Ihr A * zwei Räume verbindet, deren Türen 90 Grad voneinander entfernt sind, um Standard zu bleiben. Wenn die Türen, die zwei Räume verbinden, 180 Grad voneinander entfernt sind, den A * -Algorithmus zweimal in der Generation verwenden Phase, von der Tür zum Trennmittelpunkt (natürlich auf die nächste Kachel gerundet) und von dieser Kachel zur nächsten Tür.
quelle
Bearbeiten Sie die Kachelkostenfunktion, um zusätzlich zu den Manhattan-Entfernungen die Entfernungen (in Luftlinie) vom Start bis zum Ziel zu nutzen. Fügen Sie diesen Hälften der Kostenfunktion Gewichte hinzu, damit Sie die Manhattan-Entfernung priorisieren und mit geringem Aufwand ein wünschenswertes Ergebnis erzielen können.
Je kleiner das Gewicht ist, das Sie auf die Krähenentfernung im Verhältnis zur Manhattan-Entfernung anwenden, desto wahrscheinlicher wird die gewünschte Manhattan-Entfernung übernommen. Wenn Ihr aktueller Algorithmus eine 50/50-Auswahl hat, möchten Sie die Entscheidung beeinflussen, eine Kachel weiter von Ihrem Raum entfernt auszuwählen.
quelle
Ich denke, der einfachste Weg wäre, eine Strafe für Straightaways zu verhängen, die länger als ein bestimmter Betrag sind. Sagen wir, der halbe Abstand zwischen den beiden Punkten, die Sie verbinden möchten, abgerundet auf die nächste Maßeinheit, die Sie verwenden (Gitterquadrat?).
Ein schwierigerer Weg wäre es, die Lösung in Stücke zu zerbrechen. Wenn die Lösung beispielsweise über 5, über 5 liegt, können Sie sie in 2, über 5 und 3 aufteilen. Das Problem bei dieser Lösung ist, dass es sich möglicherweise nicht um einen gültigen Pfad handelt. Mein erster Vorschlag ist besser, weil Sie es sind Ändern des Algorithmus, um einen besseren Pfad zu finden, der immer funktioniert, anstatt einen Pfad zu verwenden und ihn so zu verbessern, dass er möglicherweise nicht funktioniert.
quelle