Anzeige des Bereichs auf dem sechseckigen Gitter

Hier ist die Situation.

Ich habe ein sechseckiges Brett und eine Einheit mit Geschwindigkeit oder Bewegungswert. 4. Unterschiedliches Gelände hat unterschiedliche Kosten. Wenn ich auf die Einheit klicke, sollte mir das Spiel eine Bewegungsreichweite anzeigen.

Meine Lösung bestand darin, jedes Hex im Bereich von 4 mit A * -Pfadfindung zu überprüfen. Wenn die Pfadkosten weniger als 4 betrugen, befand sich dieses Hex im Bereich. Das Spiel zeigt mir schließlich die Reichweite dieser Einheit.

Meine Frage ist: Gibt es eine andere Lösung, um auf Hex- oder Quadratgittern nach Reichweite zu suchen, denn selbst wenn ich wirklich stolz auf das bin, was ich in meiner Lösung getan habe, denke ich, ist es ein wenig übertrieben? :))

Was hat mich dazu gebracht, diese Frage zu stellen? Ich bemerkte, dass bei einer Geschwindigkeit von 4 oder 6 oder sogar 8 die Zeit bis zur Rechenreichweite für meinen Computer wirklich gut war, aber bei einer Geschwindigkeit von 10 und mehr bemerkte ich, dass ich einige Sekunden warten musste, um zu berechnen Nun, in echten Spielen sehe ich so etwas eher nicht und meine A * -Pfadfindung ist ziemlich gut optimiert, also denke ich, dass meine Lösung falsch ist.

Vielen Dank für alle Antworten.

Sie haben Recht, dass A * ein wenig übertrieben ist, aber nicht viel. Sie sollten keine Verzögerungen wie Sie sehen. A * ist wirklich nur ein modifizierter Dijikstra-Algorithmus . Da Sie keine Endposition verwenden (da Ihre Endposition nur "so weit wie möglich" ist), ist die Verwendung von A * mit der hinzugefügten Heuristik nicht erforderlich. Es reicht aus, nur Dijikstra oder eine einfache Breitensuche zu verwenden.

Zum Beispiel wird sich Dikikstra gleichmäßig in alle Richtungen ausbreiten:

(Eine einfache erste Suche sieht ähnlich aus.)

Behalten Sie die Kosten für die Fahrt zu jedem Knoten im Auge. Sobald ein Knoten die maximalen Reisekosten erreicht hat, verarbeiten Sie seine verbundenen Knoten nicht weiter. (Ähnlich wie dort, wo die Knoten in die Wand darunter laufen).

Wenn bei nur 10 Knoten Leistungsprobleme auftreten, sollten Sie sich ansehen, wie Sie auf die Knoten zugreifen. Eine umfassende erste Suche sollte in der Lage sein, Hunderte von Knoten ohne merkliche Verzögerung (sicherlich nicht einige Sekunden) zu navigieren. Speichern Sie eine einfache Version Ihrer Welt in einem Diagrammformat, um sie schnell zu durchlaufen.

Amit Patel hat eine hervorragende Ressource bereitgestellt , um Reichweiten auf seiner Website zu erhalten . In dem Artikel verwendet er den folgenden Algorithmus zum Sammeln von Hex-Kacheln innerhalb eines Bereichs:

for each -N ≤ Δx ≤ N:
    for each max(-N, -Δx-N) ≤ Δy ≤ min(N, -Δx+N):
        Δz = -Δx-Δy
        results.append(H.add(Cube(Δx, Δy, Δz)))

Dadurch werden Grenzen erstellt, die am Hex-Raster ausgerichtet sind:

Dadurch werden alle Felder in einem bestimmten Abstand vom mittleren Feld gefunden. Wenn Sie Hindernisse berücksichtigen möchten, verwenden Sie die breiteste erste Suche aus meiner anderen Antwort.

Falls jemand es braucht, hier ist die C # -Implementierung des Patel-Algorithmus:

IEnumerable<Hex> GetRange(Hex center, int range)
    {
        var inRange = new List<Hex>();
        for (int q = -range; q <= range; q++)
        {
            int r1 = Math.Max(-range, -q - range);
            int r2 = Math.Min(range, -q + range);
            for (int r = r1; r <= r2; r++)
            {
                inRange.Add(center.Add(new Hex(q, r, -q - r)));
            }
        }

        return inRange;
    }