Berechnen Sie die Entfernung in 2D int-Array effizient

Question

Ich mache ein Bomberman-Spiel. Ich möchte den Abstand zwischen zwei Punkten berechnen; Spieler können sich in vier Richtungen bewegen. Wenn ich bei (0,0) bin und zu (5,5) gehen möchte, kann ich die Entfernung berechnen, indem ich die Taxicab-Abstandsformel ((5-0) + (5-0)) verwende, da ich mich nur horizontal bewegen kann und vertikal.

Aber jetzt möchte ich Wände im Spiel implementieren, die der Spieler nicht durchziehen kann.

Meine aktuelle Implementierung der Entfernung, die nur Taxicab Formel verwendet.

int distanceTo(Position Pos) 
{ 
    return (abs(this->x - Pos.x) + abs(this->y - Pos.y)); 
} 

Wie finde ich den Abstand zwischen zwei Punkten (x1, y1) und (x2, y2), die unbeweglich Boxen/Wände betrachtet, das zwischen reinkommen?

Answer 1

Mit den Hindernissen, müssen Sie Ihre einfache Taxikab Abstand Formel mit einem ausgefeilteren Pathfinding-Algorithmus ersetzen.

Wie groß ist Ihr Netz? Dijkstras Algorithmus würde für kleine Gitter und A * (eine Modifikation von Dijkstra) für größere Gitter funktionieren.

Amit Patel verfügt über eine ausgezeichnete Quelle, die Dijkstra und A * beschreibt, sowie Implementierungsdetails für jeden. Sie können es sehen here.