Ich möchte für mein Spiel eine Weg-Suche implementieren.
Dabei ist die Vorgabe eine Karte mit passierbaren Gebieten und Bergen/Mauern als nicht passierbare Gebiete

Jetzt gibt es 2 Möglichkeiten, eine Karte für die Wegsuche daraus zu erstellen:
1) Alles in (ausreichend kleine) Quadrate unterteilen und dann z.b. den A* drüber schicken
Vorteil: jeder Punkt ist in einem Quadrat, sehr einfaches Handling der Werte
Nachteil: Sehr aufwendig zu erstellen (sehr große Karte), möglicherweise längere Laufzeit

2) Ich erstelle gewisse Gebiete, die passierbar sind. Alles innerhalb der Gebiete kann auf direktem Weg erreicht werden.
Bei der Wegsuche muss dann zwischen den Gebieten gewechselt werden, bis man im Zielgebiet ist
Es müssten dann auch "Wegpunkte" erstellt werden, die die verbindungen zwischen den Gebieten darstellen
Vorteil: relativ wenig gebiete, einfach handhabar (bei Fehlern kann einfach ein gebiet in kleinere aufgeteilt werden; es müssen nur begehbare gebiete erstellt werden)
Nachteil: es muss ein Graph werden (jedes Gebiet muss zu angrenzend eine (programierte) Verbindung haben, problem wenn ein punkt außerhalb eines gebietes versucht wird zu betreten (es sollte dann wenigstens ein weg in die nähe gefunden werden)

Im Anhang befindet sich eine (abstrahierte) Karte
Die Gebiete sind nicht unbedingt rund (war aber jetzt zu aufwendig da polygone zu zeichnen )
Ein weg von 1->2 wäre dann schon sowas wie: gehe zur verbindungsstelle 1/4 gehe zur stelle 4/3, dann zu 3/5, dann zu 2/5 und dann zum ziel

Ich tendiere (aufgrund des geringeren aufwandes) zur 2.Lösung
Aber wie lässt sich das speichern? (Soll fest eincompiliert werden)
also welche structur wäre dafür gut?

Im Grunde genommenbaust Du Dir dein Gebiet aus Dreiecken (oder anderen einfach zu handhabenden Flächen) zusammen und beschreibst dann in einem Graph einfach nur, welche Kanten aneinander grenzen.

Wichtig dabei ist, dass die gesamte durch deine Grundflächen abgedeckte Landschaft "erreichbar" sein muss und dein Graph zusammenhängend sein muss (Teleporter sind Verbindungen zweier Dreiecke, die nicht aneinander grenzen).

Zur Speicherung speicherst Du nun 3 Listen:
1. Die Eckpunkte (ohne Duplikate)
2. Die Dreiecke (wobei Du nur die Indizes auf die eigentlichen Koordinaten speichern brauchst)
3. Die Verbindungen zwischen den Dreiecken (vereinfacht: Alle Paare von Dreiecken mit gemeinsamer Kante).

Wenn Du das hast, kannst Du einen Weg finden, indem Du:
1. Ermittelst, in welchen Dreiecken Start- und Zielpunkt liegen
2. Breitensuche den Weg suchst
3. Die Mittelpunkte aller beteiligten Dreiecke als Wegpunkte ergänzt
4. Den Weg linearisierst (alle überflüssigen Abbiegungen entfernst, Umwege minimierst)

Ein Wegpunkt kann entfernt werden, wenn:
1. sein Vorgänger und Nachfolger auf einer Geraden liegen (Trivial)
2. sein Vorgänger und Nachfolger eine Strecke aufspannen, die vollständig innerhalb von Dreiecken liegt
3. Wenn Start- und Endpunkt im gleichen oder benachbarten Dreiecken liegen. (Trivial)

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ok hab da gestern und heute weiter dran gearbeitet
das problem: ein automatisches erstellen dieser flächen ist sehr aufwendig
darum ist mir jetzt doch das mit den quadraten lieber
es bleiben trotzdem probleme:
die karte ist sehr groß (selbst wenn ich ein quadrat in der karte als ein 8x8 feld auffasse komme ich auf eine größe von ca 3000x600=1,8Mio Felder)
ok ich kann das ganze in gebiete aufteilen, da die getrennt sind
dann ist ein (rechteckiges) gebiet "nur" noch 200.000 Felder groß
Da kann die Wegsuche doch schon eine Weile dauern. Ich habe aufgrund der Geschwindigkeit an A* gedacht (hab den schon mehrfach implementiert)
vorteil: wenn das zielfeld nicht erreichbar ist kann ich anhand der berechneten werte auslesen welches feld am nächsten dran ist

aber da brauche ichje feld min. 4 Werte (Integer-->4Byte) dann wären das 200.000*4*4=3,2MB Hauptspeicher
ok das geht ja heutzutage
aber wie bekomme ich den schnell (laufzeit <=1,5sec)
oder dann doch lieber breitensuche?
oder ein ganz andrer algo?

wegen der struktur habe ich gedacht ich wandle den A* ab und nehme ein array der felder
also zu jedem feld wird schon gespeichert was F,G,H ist und ob es offen, geschlossen oder noch nicht betrachtet ist
nachteil: ich belege immer die 3,2MB hauptspeicher egal welcher weg es wird
vorteiL: ich muss nicht mit listen arbeiten und kann so direkt auf ein feld zugreifen (einfach multiplikation statt suche in einer liste aus vl 1000 werten)

na gut jetzt bräcuhte ich wieder andre meinungen ob das so richtig ist oder ob es was besseres gibt

Eine relativ generische Lösung für Eine Wegsuche mit Breitensuche findest Du unter omorphia.svn.sourcef...y/OAIBacktracing.pas Das ist zwar im Zweifelsfall in der Form nicht die Speichereffizienteste Lösung, jedoch ist die extrem schnell: Auf einer Fläche mit >1 Mio.* Punkten dauert ein Prepare etwa 1 Sekunde, das eigentliche Erstellen des Weges geht dann in Bruchteilen einer Millisekunde.

Als Grundlage nutze ich dort eine Breitensuche sowie eine recht generische Datenstruktur zum Abbilden eines beliebigen Raumes. Die 2D-Struktur dort kann man u.U. ignorieren, aber das ist ein anderer Punkt. Wichtig zu wissen bei dieser Lösung ist die Tatsache, dass im Vorbereitungsschritt zuerst eine Distanz-Messung gemacht werden muss. Solange sich das Ziel nicht ändert, brauch diese nur einmal ausgeführt werden. Das anschließende Suchen des kürzesten Weges zwischen Start- und Endpunkt geht dann in linearer Zeit (abhängig von der Anzahl nötiger Schritte**).

Was Du glaube in deinem Fall noch übersehen hast, ist die Tatsache, dass der Vorbereitungsschritt (mit den Dreiecken\Quadraten) beim Compilieren der Map, oder im Notfall beim Laden der Map) erledigt werden kann. Sobald Du einmal diese Strukturen hast, brauchst Du diese nicht weiter bearbeiten und kannst diese damit ggf. komprimiert im Speicher halten. Wichtiger ist eher, dass Du den Gebietsverbindungsgraphen in schnellem Zugriff hast, da dieser sehr oft benötigt wird.

Für weitere Fragen steh ich gern zur Verfügung.

*Kleine Demo, die auf einem Fullscreen-Canvas ein zufälliges Labyrinth gezeichnet hat. Bei 1280x1024 ging dieser erste Schritt samt Grafik in 2 Sekunden auf einem moderat schnellen Rechner (800MHz). Da der Vorbereitungsschritt mit einer Queue arbeitet, sollte sich die Arbeit des Algorithmus gut parallelisieren lassen.

**eigentlich noch multipliziert mit der Anzahl der Abzweigungen an jedem Schritt, da diese Zahl aber konstant UND sehr gering ist, kann das vernachlässigt werden. Zumal bereits beim Erstellen der Struktur nur noch minimale Wege verlinkt werden.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Dein Algo sieht sehr interressant aus. Nur leider sehe ich da 0 durch...
Ich habe mal das ganze mit A* gemacht, um mal nen Vergleich zu haben.
Mein Algo braucht bei einem Feld von 1000*1000 Feldern zufälliges Labyrinth quer durch ohne Lösung zu finden (weil kein Weg vorhanden-->Worst case) 3,5 sec
Optimierungen sind aber noch möglich (aber nur geringfügig)

Vorteil: Ich kann, wenn kein Weg zum Ziel existiert, dann einfach das Feld suchen, das die geringste Entfernung zum Ziel hat.

Das Problem mit dem "Vorbereitungsschritt" ist, dass ich die Map nicht direkt vorliegen habe und derzeit nicht genau auslesen kann, was begehbar ist und was nicht. Ich habe einige Gebiete von denen ich das schon weiß und andere sind sozusagenFog of War (Unbekannt) und werden erst nach und nach als begehbar erkannt.
Ich muss also durchaus die Strukturen weiter bearbeiten.
Außerdem tue ich mich sehr schwer mit Dreiecken und ähnlichen Gebieten. Bei quadraten ist alles noch schön durchschaubar. Aber wenn ich ein Dreick aufteilen und neue einfügen, neue Verbindungen herstellen muss, halte ich das für sehr aufwendig.
Auch wenn das bei komplett bekannter Karte eine gute Alternative wäre, da große freie Gebiete zusammengefasst werden können und nicht nochmal durchsucht werden müssen.

Wie lange braucht dein Algo zur Wegsuche, wenn er keinen Weg findet (also die ganze Karte durchsuchen muss)?
Und kannst du dir meinen mal angucken?

Außerdem: der aktuelle Algo würde bei einer Konstellation, bei der start und ziel 3 felder in x richtung und 2 in y-richtung entfernt sind erst 2 felder quer dann eins zur seite gehen
Lässt sich sowas vermeiden? Denn eigendlich ist es kürzer gleich die komplette Diagonale zu nehmen.
Das hattest du bei der Nachbearbeitung. Wie kann ich die machen?
Denn du hattest gesagt: Wegpunkt entfernen wenn vorgänger+nachfolger auf geraden liegen. ok...(x-x1)=(x-x2) && (y-y1)=(y-y2)
das geht...
aber krieg ich auch solche 3:2 fälle weg? Das wäre ja dann: Vorgänger+Nachfolger bilden eine Strecke, die in begehbaren Feldern liegt. Aber wie geht das?

Danke schonmal für deine Mühen bisher

Flamefire hat folgendes geschrieben :

Dein Algo sieht sehr interressant aus. Nur leider sehe ich da 0 durch...

Mein Algorithmus ist extrem abstrakt geschrieben. Der funktioniert theoretisch auf jeglichen gerichteten Graphen (auf ungerichteten auch, wenn man auch die Rückverbindung immer mit angibt).

Das Vorgehen ist eine einfache Breitensuche:
- Fange mit einem Feld an (das Ziel) und setze Gewicht Entfernung 0.
- Nimm ein Feld aus der Queue
- Wenn die Kosten zu einem Knoten geringer sind, als bereits bekannt, aktualisiere die Kosten und füge diesen Knoten in die Queue ein.
- Ermittel alle von diesem Feld aus erreichbaren Knoten des Graphen, diese Knoten in die Queue einfügen, wenn deren Kosten geringer sind, als bisher bekannt
- Solange noch Einträge in der Queue sind, nimm einen neuen Knoten

Das wirkt nur durch den Ringpuffer den ich als Queue nutze und die Abstrakte Darstellung des Graphen bei mir etwas gewöhnungsbedürftig.

Vorteil: Aufsuchen des am kürzesten entfernten Zieles von mehreren möglichen.

Flamefire hat folgendes geschrieben :

Ich habe mal das ganze mit A* gemacht, um mal nen Vergleich zu haben. Mein Algo braucht bei einem Feld von 1000*1000 Feldern zufälliges Labyrinth quer durch ohne Lösung zu finden (weil kein Weg vorhanden-->Worst case) 3,5 sec Optimierungen sind aber noch möglich (aber nur geringfügig)

Dafür wäre dann die Algo&Opti-Sparte zuständig

Flamefire hat folgendes geschrieben :

Vorteil: Ich kann, wenn kein Weg zum Ziel existiert, dann einfach das Feld suchen, das die geringste Entfernung zum Ziel hat.

Gut, das kann mein Algo nicht. Der ist dann aufgeschmissen, DAFÜR weißt Du aber in O(1), dass kein Weg existiert.

Flamefire hat folgendes geschrieben :

Das Problem mit dem "Vorbereitungsschritt" ist, dass ich die Map nicht direkt vorliegen habe und derzeit nicht genau auslesen kann, was begehbar ist und was nicht. Ich habe einige Gebiete von denen ich das schon weiß und andere sind sozusagenFog of War (Unbekannt) und werden erst nach und nach als begehbar erkannt. Ich muss also durchaus die Strukturen weiter bearbeiten.

Gut, das würde zumindest immer einen neuen Vorbereitungsschritt benötigen, da sich die Weglänge durchaus bereits geändert haben könnte ...

Flamefire hat folgendes geschrieben :

Außerdem tue ich mich sehr schwer mit Dreiecken und ähnlichen Gebieten. Bei quadraten ist alles noch schön durchschaubar. Aber wenn ich ein Dreick aufteilen und neue einfügen, neue Verbindungen herstellen muss, halte ich das für sehr aufwendig. Auch wenn das bei komplett bekannter Karte eine gute Alternative wäre, da große freie Gebiete zusammengefasst werden können und nicht nochmal durchsucht werden müssen.

Ich sagte ja bereits: Was man als Grundform für die Gebiete nimmt, ist egal. Die Grundfläche sollte nur konvex sein.

Flamefire hat folgendes geschrieben :

Wie lange braucht dein Algo zur Wegsuche, wenn er keinen Weg findet (also die ganze Karte durchsuchen muss)? Und kannst du dir meinen mal angucken?

Muss ich meine Test-Implementierung mal raussuchen.

Flamefire hat folgendes geschrieben :

Außerdem: der aktuelle Algo würde bei einer Konstellation, bei der start und ziel 3 felder in x richtung und 2 in y-richtung entfernt sind erst 2 felder quer dann eins zur seite gehen Lässt sich sowas vermeiden? Denn eigendlich ist es kürzer gleich die komplette Diagonale zu nehmen. Das hattest du bei der Nachbearbeitung. Wie kann ich die machen? Denn du hattest gesagt: Wegpunkt entfernen wenn vorgänger+nachfolger auf geraden liegen. ok...(x-x1)=(x-x2) && (y-y1)=(y-y2) das geht... aber krieg ich auch solche 3:2 fälle weg? Das wäre ja dann: Vorgänger+Nachfolger bilden eine Strecke, die in begehbaren Feldern liegt. Aber wie geht das?

Das ist die Geschichte, warum ich konvexe Grundflächen voraussetze. Dann bekommst Du nämlich beim Weglassen deines Punktes eine Strecke, die trotzdem durch deine Grundfläche (aktuelles Dreieck in meinem Fall) geht.

Flamefire hat folgendes geschrieben :

Danke schonmal für deine Mühen bisher

NP.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ok. wenn ich deine erklärung richtig verstanden habe, ist dein algo eigendlich eine pure breitensuche, wobei nur die entfernungen mit geloggt werden.

der a* (weißt du wie der geht?) ist ja auch eine art breitensuche, nur priorisiert er die felder
er geht im prinzip so vor, wie deiner, nur wird das feld aus der queue genommen, von dem geschätzt wird, dass es den geringsten weg von start zum ziel hat (es wird mitgeloggt, wielange man zum feld braucht und geschätzt wie weit es zum ziel ist)
darum ist meine vermutung: dass dein algo im worst case etwas schneller ist (inkl. vorbereitung) als A*
aber im bestcase und avg case dürft a* schneller sein
darum mal die frage nach der laufzeit von deinem

mehrere ziele hab ich nicht. hab nur start und ziel

nach dem a* fertig ist weiß ich ob ein weg existiert und wenn nicht kann ich immer noch den besten weg (so nah wie möglich) raussuchen, ohne neubrechnung

wegen dem neuen vorbereitungsschritt: wenn dein algo inkl vorbereitung schneller/besser ist als mein A* wäre der noch ne überlegung wert
was muss den als vorbereitung gemacht werden? als was muss der graph vorliegen?
als bsp mal mein programm: so eine karte aus quadraten kann ich automatisch erstellen (auch wenn sie sich häufig ändert)
wenn ein graph erst ertstellt werden müsste, der dann fest ist, hat das den nachteil,d ass es per hand gemacht werden muss.
ich bekomme gelegendlich infos wie: quadrate a,b und c sind begehbar. dann soll das sofort in zukünftige rechnungen aufgenommen werden

Zitat:

Das ist die Geschichte, warum ich konvexe Grundflächen voraussetze. Dann bekommst Du nämlich beim Weglassen deines Punktes eine Strecke, die trotzdem durch deine Grundfläche (aktuelles Dreieck in meinem Fall) geht.

den teil verstehe ich nicht. was meinst du genau mit konvexen fläschen? ich denk da immer an ne linse
und wenn ich bei den quadraten was weglasse bekomme ich ja nur 45° winkel.

Flamefire hat folgendes geschrieben :

ok. wenn ich deine erklärung richtig verstanden habe, ist dein algo eigendlich eine pure breitensuche, wobei nur die entfernungen mit geloggt werden.

Jap.

Flamefire hat folgendes geschrieben :

der a* (weißt du wie der geht?) ist ja auch eine art breitensuche, nur priorisiert er die felder er geht im prinzip so vor, wie deiner, nur wird das feld aus der queue genommen, von dem geschätzt wird, dass es den geringsten weg von start zum ziel hat (es wird mitgeloggt, wielange man zum feld braucht und geschätzt wie weit es zum ziel ist) darum ist meine vermutung: dass dein algo im worst case etwas schneller ist (inkl. vorbereitung) als A* aber im bestcase und avg case dürft a* schneller sein darum mal die frage nach der laufzeit von deinem

Hab den grad nicht hier, muss ich bei Gelegenheit mal raussuchen, wo ich die Demo hab.

Flamefire hat folgendes geschrieben :

mehrere ziele hab ich nicht. hab nur start und ziel

Das ist ja egal, hab ich nur bei meinem Algo gesehen, dass das bei mir problemlos klappt. Ist in meiner Demo sogar umgesetzt ...

Flamefire hat folgendes geschrieben :

nach dem a* fertig ist weiß ich ob ein weg existiert und wenn nicht kann ich immer noch den besten weg (so nah wie möglich) raussuchen, ohne neubrechnung

Bei meinem Algo ist die Laufzeit von der Anzahl der vom Ziel aus erreichbaren Felder abhängig. Wenn also nur weniger Felder erreichbar sind, hat mein Algo auch nur wenig zu tun.

Flamefire hat folgendes geschrieben :

wegen dem neuen vorbereitungsschritt: wenn dein algo inkl vorbereitung schneller/besser ist als mein A* wäre der noch ne überlegung wert was muss den als vorbereitung gemacht werden? als was muss der graph vorliegen?

Die Vorbereitung ist die Ausführung des Algos, der in die Datenstruktur die Entfernungen\Kosten einträgt. In der verlinkten Unit hatte ich für das Liefern des Graphen glaube sogar nen Callback drin gehabt: Sprich die Anwendung konnte ihr eigenes Datenformat entscheiden. Wichtig war nur, dass Du Quellknoten, Zielknoten und Kosten lieferst; wobei der Callback dich für die benötigten Knoten nur fragt. Du brauchst also nicht den Gesamtgraphen im RAM halten.

Flamefire hat folgendes geschrieben :

als bsp mal mein programm: so eine karte aus quadraten kann ich automatisch erstellen (auch wenn sie sich häufig ändert) wenn ein graph erst ertstellt werden müsste, der dann fest ist, hat das den nachteil,d ass es per hand gemacht werden muss.

Der Graph bei mir muss nur für den Vorbereitungsschritt und die darauffolgenden Abfragen konstant bleiben. Sobald sich dein Zielknoten ändert, ODER neue Knoten zum Graphen dazukommen, ist eine Neuberechnung der Gewichte nötig. Solange aber sowohl die Kanten des Graphen, als auch das Ziel konstant sind, können die berechneten Gewichte gecacht werden.

Flamefire hat folgendes geschrieben :

ich bekomme gelegendlich infos wie: quadrate a,b und c sind begehbar. dann soll das sofort in zukünftige rechnungen aufgenommen werden

Sollte bei hinzukommenden Verbindungen theoretisch durch Ergänzung des gecachten Ergebnisses einpflegbar sein (also nur betroffene Knoten neu berechnen). Beim Entfernen von Verbindungen muss der Cache vollständig neu berechnet werden. Genauso bei Änderungen, bei denen Kosten für einen Weg steigen (wenn sie sinken, geht das partielle Neuberechnen)

Flamefire hat folgendes geschrieben :

Zitat: Das ist die Geschichte, warum ich konvexe Grundflächen voraussetze. Dann bekommst Du nämlich beim Weglassen deines Punktes eine Strecke, die trotzdem durch deine Grundfläche (aktuelles Dreieck in meinem Fall) geht. den teil verstehe ich nicht. was meinst du genau mit konvexen fläschen? ich denk da immer an ne linse und wenn ich bei den quadraten was weglasse bekomme ich ja nur 45° winkel.

Konvex und Konkav bei Polygonen sagt einfach nur aus, ob es Einbuchtungen gibt, oder ob alle Kanten zur Hüllkurve gehören. PacMan ist Konkav

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

da ich IMMER verschiedene start und ziel coords habe, müsste die vorbereitung also immer wieder ausgeführt werden.

ich würde also bei A* bleiben auch wenn deiner sein könnte. jedoch will ich auch an nicht erreichbare gebiete möglichst nah ran kommen. und wenn bei dir das ziel auf nicht erreichbarem gebiet liegt, schlägt der algo fehl, wenn ich das richtig verstanden habe

bleibt also jetzt noch die frage nach dem entfernen von wegpunkten wenn die anliegenden wegpunkte eine gerade durch begehbare quadrate aufspannen

wie mach ich das?
gehn müsste es ja denn quadrate sind ja (grade noch) konvex, richtig verstanden?

Du durchquerst eine Fläche, wenn Du mindestens 2 Schnittpunkte mit ihren Kanten hast, die zwischen Start und Endpunkt deiner Strecke liegen. Siehe Schnittpunktberechnung Gerade und Dreieck.

Das DelphiGL-Wiki könnte Dir in dieser Frage recht gute Hinweise für die Implementierung geben.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

so könnte ich u.u. berechnen ob ein quadrat auf der strecke liegt
aber ich will ja aus der strecke das quadrat bekommen das den eigenschaften genügt
sosmnt müsste ich ja zu jedem quadrat die schnittpunkte berechnen...

Ich geh bei dieser Weg-Vereinfachung davon aus, dass Du z.B. einen Weg von A nach B hast, und die Dreiecke 1, 2 und 3 Teil des Weges bilden, sprich A liegt in 1 und B in 3. Wenn ich jetzt S1 als Schwerpunkt von 1 nehme, geht mein temporärer Weg jetzt A->S1->S2->S3->B. Bei einer Wegvereinfachung kann ein Punkt nun immer dann entfernt werden, wenn er IMMER innerhalb dieser Dreiecke bleibt, selbst wenn man einzelne Wegpunkte entfernt. So war das bei mir mit dem oben genannten Algo gemeint.

Wenn Du jetzt einen Punkt entfernst, muss die resultierende Linie zwischen den beiden Punkten immer noch innerhalb der von den Dreiecken "maskierten" Fläche liegen. Tut sie das nicht, darf der Punkt nicht entfernt werden.

Wenn Du nun auf diese Weise die Route vereinfacht hast, kannst Du die Routen-Punkte vom Zentrum der Dreiecke auf die Randpunkt der Dreiecke verlegen (außer Start und Ziel). Fliegst Du damit aus dem markierten Bereich raus, musst Du wieder zusätzliche Punkte am Rand zusätzlich einfügen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ich zeigs mal per grafik:

Ich will von A1->D3
Alle Felder sind begehbar

Das blaue ist der gefundene Weg mit wegpunkten.
Mit der Linien-berechnung bekomme ich den wegpunkt B2 weg
Theoretisch kann auch der Wegpunkt C3 weg, da man direkt von A1 nach D3 kommt (schwarzer weg)

Wie kann ich ermitteln, dass C3 weg kann?

Eine Möglichkeit ist mir gerade eingefallen:
Mittels Bresenham-Linien-Algo die Quadrate raussuchen die auf einer linie zwischen A1 und D3 sind
wenn alle begehbar sind, kann C3 weg

ich müsste nur sehr häufig bresenham einsetzen. falls es noch eine andere idee gibt wäre ich dankbar
sonst sieht der eigendlich sehr passend aus

PS: de.wikipedia.org/wik...resenham-Algorithmus

Bei meinem Elimierungsalgo würde das auch ohne Bresenhem gehen, wenn Du nur 4-Wege zulässt, ODER die Gewichte so anpasst, dass die 4-Wege-Richtungen keinen Nachteil gegenüber den Diagonalen haben (dann liefert mein Algo eine reihe alternativer Wege, die alle als gültig markiert sind und damit eine Vereinigung zulassen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.