Ich habe eine Wegsuche geschrieben. (Einige Hilfen habe ich aus anderen Beiträgen erhalten)
Jetzt bin ich dabei aus dem weg eine liste von sinnvollen waypoints zu erstellen.
Bisher arbeitet der algo 2-stufig:
0) wegsuche-->Jedes Feld auf dem Weg ist ein Waypoint
1) Waypoint 1 entfernen, wenn (x0-x1)*(y1-y2)=(x1-x2)*(y0-y1) ist -->Gerade in der 2D ebene (y=mx+n und "m" ist vom vorgängerpunkt zum punkt gleich dem "m" vom punkt zum nachfolger)
2) Erstelle Breesenham-Linie vom Vorgänger zum Nachfolger. Wenn keine nicht begehbaren Felder auf dem Weg sind-->Punkt entfernen

So weit so gut. Nur ist der Breesenham algo nicht so ganz dafür geeignet, da er oft die "wahl" hat erst 1 nach links dann eins nach unten oder umgedreht zu gehen (je nachdem von welcher seite aus man startet). Dadurch ergibt sich aber manchmal, dass er von der einen richtung nur begehbare felder und von der andren richtung ein nicht begehbares erwischt.
Außerdem können kleine hindernisse bei der waypoint-erzeugung vernachlässigt werden (z.b. das ende einer mauer. da kommt die einheit noch drumrum)

Als Bsp: die grafik im anhang:
schwarz=mauer
weis=frei
farbig=je 2 punkte die es zu verbinden gilt

rot:breesen ham sollte die 2 w. felder liefern: geht ohne zwischenpunkt
gelb: je nachdem von welcher seite man den breesenham beginne lässt geht der weg über das schwarze feld oder nicht, sollte aber ohne zwischenpunkt verbunden werden können
grün: mauerende im weg, algo sollte das als ende erkennen und direkten weg ermöglichen
blau: zu viel mauer dazwischen-->ein wegpunkt direkt über der mauer nötig

wie kann ich jetzt also diese aufgabe lösen?
meine bisher einzige idee wäre: wegsuche von vorgänger zum nachfolger starten (geht ja schnell, wegen geringer entfernung und ziel immer erreichbar) und gucken ob die anzahl der felder = abstand der punkte in x oder y richtung(je nachdem welche größer ist)
bei grün kommt dann raus: weg von 4 felder
abstand in x-richtung:4 -->OK; abstand in y: 4 -->OK

oder jemand ne bessere idee?


Moderiert von Christian S.: Topic aus Sonstiges (Delphi) verschoben am Sa 04.04.2009 um 11:24

Hier könnte Dir helfen, was ich im anderen Thread zur Punkt-Optimierung geschrieben hab:

Nehmen wir die gelben kästchen: Wenn man vom linken kästchen bis in die vorletzte Zeile geht, und dann rüber zum zweiten Kästchen, wobei man immer den Kästchen-Mittelpunkt als "Stützpunkt" annimmt, kann man den Weg dadurch optimieren, dass diesen so verschiebt, dass er nirgends zwischen Start und Ziel ein schwarzes Feld schneidet. In diesem konkreten Fall könnte man also den Wegpunkt im zweiten Kästchen von unten, ganz links, in die rechte obere Ecke des Kästchens verschieben. So meinte ich das auch bereits im anderen Thread, zu dem Du bitte mal noch einen Link ergänzen solltest

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.

Hallo,

deine Wegsuche kann also auch diagonal laufen ( rot-rot ) und nicht nur die vier Himmelsrichtungen.
Wie wäre es, wenn du in jedem Feld mit Mauer mit hineinschreibst:
Richtung Nord Süd oder Ost West oder Kreuzung
Wie lang / Ausdehnung
Welche Position gerade dieses Stück hat
also
Mauer in Nord Süd Richtung
6 Einheiten lang
Pos 6 (also unten die Endposition)
Oder Du arbeitest mit einer Mauerliste und schreibst in das Suchfeld statt der Eigenschaft Mauer einen Zeiger auf diese Mauer
Dort steht dann Start und Endkoordinate und die kreuzenden Mauern von Start zu Endkoordinate gestaffelt.

Damit kannst Du dann schneller die Verschiebung herausfinden, die nötig ist.
Das lohnt sich sicher nur bei vielen verschiedenen Startpunkten Endpunkten.
Ich dachte dabei an ein "richtiges" Labyrinth.

Gruß Horst

@Horst: Das problem es ist keine mauer in dem sinne eine geraden sondern eine arte gebirge mit ecken und kanten.
da geht z.b. ein halbwegs gewinkelter pfad durch wo die waypoint suche ebn an den ecken hängen bleibt

link kommt später bin grad etwas in eile...versteh deinen ansatz aber ne ganz...

EDIT: Link zum anderen Thread: www.delphi-forum.de/....php?p=555616#555616

Und zum verschieben einer geraden: Als Bsp ein gerader weg von oben nach unten. Jetzt ist da einmal eine einbuchtung von links und einmal von rechts von je einem Feld
Es muss also eine ganz leichte S-Kurve gegangen werden, damit das funktioniert. Das soll auch erlaubt sein, mit nur je einem Wegpunkt am Anfang und Ende der Strecke mit der Kurve
Dann kann man doch nix mehr verschieben, da man dann entweder das feld links oder das rechts schneidet

hmm...hab grad mal mein testlabyrinth(1000x1000 Felder; ziel versperrt; max. entfernung) genutzt und ausprobiert, was passiert wenn ich für die wegpunkte nach der simplen überprüfung mittels direkte line (dy/dy) und breesenham (da sehr schnell) nochmal A* drüberjage und den punkt entferne wenn die anzahl der weg-felder<=abstand der wegpunkte +1 ist
war aber ne dumme idee:
zwar ergebnis: aus 1149 punkten sehr viel weniger gemacht (~100 oder so) aber zeitdauer für die restliche auswertung: 38sec
und das geht gar nicht

nächster versuch: feld entfernen nach test durch
abstand <=2
direkte linie dx/dy
breesenham vorwärts und rückwärts, und test ob alle felder begehbar

Dauer 10ms
felder am ende: 220 statt 1149

ist mir aber immer noch zu viel
besonders da manche die noch drin sind, durch eine linie verbunden werden können, wenn die toleranz etwas höher ist (breesenham ist da ja etwas stur) von wegen IMMER in die eine richtung und manchmal in die andre

hab jetzt mal eine tiefensuche implementiert, die auf diesen zweck angepasst ist.
erlaubt sind nur 3 varianten der schritte:
1: schritt in x + y richtung
2: schritt in x richtung
3: schritt in y richtung

und zwar ausschließlich in richtung ziel (wird vorher festgestellt)
wenn ich in x oder y über die ziel koordinaten komme, wird zurückgegangen.
da ich grad am uni rechner bin kann ich den quellcode nicht posten, werde das aber nachher nachholen.
ich denke damit die schwäche des breesenham ausgleichen zu können, und viel bessere resultate zu erhalten, da der algo auch sehr schnell ist.
so schnell, dass ich schon überlegt habe, den A* damit zu ersetzen...bis mir aufgefallen ist, dass er durch das verbot des "zurück"-gehens zum teil längere wege findet, wenn überhaupt. aber das war ja klar

ergebnis in dem programm poste ich auch wenn ich wieder zuhause bin

ok habs nochmal optimiert sodass ich jetzt auf eine laufzeit von insgesammt 1,2 sec komme
(davon knapp 1sec für A*)

der tiefensuche-algo macht auch was er soll (1300 schritte->103 schritte)
aber ist noch zu effektiv. sprich: die abweichung von einer geraden linie ist noch zu groß
ich muss also ein fehlerglied mit reinbringen.
wie schaffe ich das? wie kann ich das fehlerglied berechnen?