Können A * Pfadfindungskostenfunktionen Pfadverfolgungsformen ermöglichen?

7

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.

Beispielbild

Hinweis: Der Algorithmus hat auch Zugriff auf die normale Richtung der Start- und Endziele.

CluelessGameMaker
quelle
3
Sie erhöhen die Wahrscheinlichkeit, dass Personen Ihre Frage lesen, indem Sie gut platzierte Absatzumbrüche hinzufügen.
Vaillancourt
Gibt es jemals Hindernisse, um die der Weg herumlaufen muss? Wenn nicht, können Sie möglicherweise A * vollständig überspringen und den Pfad ohne die inkrementelle Suche geometrisch konstruieren. Dies würde eine sehr freie Kontrolle über die resultierenden Formen geben.
DMGregory
Um DMGregory zu beschreiben, müssen Sie geometrische Zeichenfunktionen verwenden und alle Aufrufe von some_putpixel (x, y) durch map [x] [y] = SOME_TILE ersetzen. Er hat einen fairen Punkt, die gleiche Aufgabe könnte auch wie in meiner Antwort beschrieben erfüllt werden, indem der Abstand zwischen zwei Orten durch zwei geteilt und drei Linien mit einem Algorithmus wie dem Bresenhams-Linienalgorithmus gezeichnet werden.
Joshua Hedges

Antworten:

3

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.

Joshua Hedges
quelle
2

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.

John McDonald
quelle
1

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.

Codepants
quelle