Pathfinding Auf einer riesigen Karte

Question

Ich brauche eine Art der Pfadfindung, also habe ich im Internet gesucht und einige Algorithmen gefunden.

Es scheint, dass sie alle auch eine Art Karte benötigen. Diese Karte kann dargestellt werden durch:

• Grid
• Knoten

Da meine Karte zur Zeit ziemlich umfangreich ist (20.000 x 20.000 Pixel), eine Rasterkarte von 1 x 1 Pixel Fliesen führen würde zu 400.000.000 einzigartige Punkte auf dem Grid und auch die beste Qualität, die ich denke. Aber das ist viel zu viele Punkte für mich, so dass ich entweder

• die Kachelgröße erhöhen (zB 50 x 50 px = 160,000 einzigartige Punkte)
• Schalter zu Knoten

Als 160,000 einzigartigen Punkte sind auch zu viel für mich, oder ich würde sagen, nicht die Qualität, die ich gerne hätte, da einige Einheiten größer sind als 50 px, ich denke, Knoten sind der bessere Weg zu gehen.

fand ich diese im Internet 2D Nodal Pathfinding without a Grid und haben einige Berechnungen:

local radius = 75        -- this varies for some units so i stick to the biggest value 
local DistanceBetweenNodes = radius * 2   -- to pass tiles diagonaly 
local grids = 166        -- how many col/row 
local MapSize = grids * DistanceBetweenNodes -- around 25.000 
local walkable = 0        -- used later 

local Map = {} 

function even(a) 
    return ((a/radius) % 2 == 0) 
end 

for x = 0, MapSize, radius do 
    Map[x] = {} 
    for y = 0, MapSize, radius do 
     if (even(x) and even(y)) or (not even(x) and not even(y)) then 
      Map[x][y] = walkable 
     end 
    end 
end 

Ohne die unpassable Knoten und eine Einheitsgröße von 75 Entfernen von i mit ~ 55.445 eindeutige Knoten enden würde. Die Knoten werden drastisch schrumpfen, wenn ich die nicht passierbaren Knoten entferne, aber da meine Einheiten unterschiedliche Größen haben, muss ich den Radius zur kleinsten Einheit machen, die ich bekommen habe. Ich weiß nicht, ob das später mit größeren Einheiten funktioniert.

So suchte ich wieder im Internet und fand diese Nav Meshes. Dies wird die Knoten in meinen Augen auf nur "ein paar" reduzieren und würde mit jeder Einheitsgröße arbeiten.

AKTUALISIEREN 28.09 Ich habe eine Knotenkarte aller passierbaren Gebiete jetzt ~ 30.000 Knoten erstellt.

Hier ist ein völlig willkürliches Beispiel einer Karte und die Punkte i haben: Example Map

Answer 1

Dies erfordert einige Optimierung und reduzieren die Menge der Knoten, die Sie haben.

Fast jeder Pfadfindungsalgorithmus kann eine Knotenliste verwenden, die kein Gitter ist. Sie müssen jedoch den Abstand zwischen den Knoten anpassen.

Sie könnten auch Ihre Rastergröße erhöhen, damit sie nicht so viele Quadrate enthält. Sie müssen jedoch kleine, schmale Pfade auf irgendeine Art kompensieren.

Am Ende des Tages, würde ich vorschlagen, Sie reduzieren Ihre Anzahl von Knoten, indem Sie einfach Knoten in einem angeordneten Pfad, wo Sie wissen, ist es möglich, von Punkt A nach B zu bekommen, unter Angabe der Nachbarn. Sie müssen jedoch manuell einen Knotenpfad für jede Ebene erstellen.Nehmen Sie meinen Test als Beispiel (Es gibt keine Wände, sondern nur die Knotenpfad):

Für Ihre bereitgestellt Karte, Sie würden mit einem Pfadknoten am Ende wie folgt aus:

Das hat etwa 50 Knoten, verglichen mit den Hunderten, die ein Gitter haben kann.

Dies kann in jedem Maßstab funktionieren, da die Anzahl der Knoten im Vergleich zum Grid-Ansatz drastisch reduziert ist. Sie müssen einige Anpassungen vornehmen, z. B. die Entfernung zwischen Knoten berechnen, jetzt, da sie nicht in einem Raster liegen. Für diesen Test verwende ich den Dijkstra-Algorithmus in Corona SDK (Lua), aber Sie können versuchen, einen anderen wie A-Stern (A *) zu verwenden, der in vielen Spielen verwendet wird und schneller sein kann.

fand ich eine Einheit Beispiel, das einen ähnlichen Ansatz mit Knoten nimmt, und man kann sehen, dass der Ansatz in 3D funktioniert auch: