Ich versuche gerade, ein Videospiel zu erstellen, in dem Charaktere AI sind und sich in einer kreisförmigen Karte mit Ressourcen befinden.
Ich versuche gerade, die kürzeste Entfernung zwischen zwei Punkten auf dieser Karte zu berechnen, aber mein Problem ist, dass die Karte zirkulär ist: zum Beispiel
Wenn meine Karte 20 * 20 ist und ich in (0,0) bin, hat der Punkt (19,0) nur eine Entfernung von 1. Ich habe im Internet gesucht, aber ich habe keine Antworten für mein Problem gefunden. Ich muss mich auch um die Orientierung (North South West East) meines Charakters kümmern, in dem er sich drehen muss um zum Punkt zu kommen, der Abstand muss länger sein.
Gibt es eine bestehende Formel?
Danke fürs Lesen!
Das Problem bleibt ein Problem mit dem kürzesten Pfad in einem Diagramm, Sie müssen nur Kanten für die kreisförmige Karte hinzufügen:
G = (V,E) wo V = {all squares} und E = { (u,v) | [(u.x + 1 % 20 = v.x or u.x -1 % 20 = v.x) and u.y == v.y] or ... [same for y] }
Was die obige mathematische Notation sagt: Es gibt eine Kante zwischen zwei Quadraten wenn (und nur wenn), die Differenz zwischen ihren x- oder y-Koordinaten ist 1 oder -1 in Z 20 (modolus 20) Ring). Da der Ring Z20 selbst kreisförmig ist, löst er das Zirkularitätsproblem der Abbildung.
In diesem Diagramm können Sie BFS verwenden, um den kürzesten Pfad aus einer einzigen Quelle zu finden (keine Notwendigkeit für dijkstra's) Algorithmus, weil der Graph nicht gewichtet ist)
Hinweis: Wenn es keine Hindernisse gibt, berechnen Sie sie einfach mit Ihrer normalen Abstandsfunktion, aber verwenden Sie den Z 20 Ring anstelle des Z-Feldes in Ihrer Mathematik.