Path Finding

http://www.gnome-gohome.com/bilder/path.JPG

So ich habe folgendes Problem.
Ich habe einen Startpunkt und ein Zielpunkt. Es muss eine Linie vom Startpunkt zum Zielpunkt gemahlt werden ohne
das er die schwarzen Wände berüht. Die Wände werden immer anders gezeichnet er muss sich also den Weg finden.

Wie macht man sowas? Hat einer Ideen oder vieleicht Lösungen?

vielen dank

borg

ich würde das feld rastern und A* machen.

Es ist aus diesem Bild nicht ersichtlich, dass man rastern muss. A* ist natürlich ein feiner Tipp. Als Knoten würden sich Sichtbarkeitspunkte anbieten, die aber aufwändig zu berechnen sind. Der Einfachheit halber würden es die Eckpunkte auch tun. Wenn dir A* zu aufwändig ist, taugt Dijkstra auch noch. Wenn die Landschaften so einfach bleiben, wäre A* Verschwendung.

(kleiner Tipp am Rande, ein PNG-Bild wäre vermutlich eine kleinere Datei gewesen und du hättest ein sauberes Bild gehabt)

Ja das Problem ist wie ich die Linien erkennen soll? Kann man die Linien irgendiwe in Vectoren umwandeln und dann die genaue position zu wissen?

borg

also ich würde, wie gesagt, das feld rastern und jedes feld, in welchem etwas schwarzes ist, ist mauer. A* dann darauf anzuwenden sollte nicht kompliziert sein eigentlich.

- bild einlesen
- 100x100 bool array anlegen
- bild in width/100, height/100 kästchen zerlegen
- 1 in array eintragen, falls etwas schwarzes im kästchen ist, 0 sonst
- A* anwenden

Ob man das Feld rastern sollte, hängt von den Anforderungen ab. Wenn du es grundlos rasterst, machst du aus 4 Knoten 10000 und wofür?
Man kann die Linien genauso gut als Endpunkte gegeben haben. Normalerweise baut man Hindernisse aus Polygonen auf. Der Einfachheit halber kann man sie aus Rechtecken aufbauen, damit lässt sich das Labyrinth darstellen. Knoten für den A*/Dijkstra sind dann alle begehbaren Außen-Eckpunkte, in deinem Beispiel 4, plus Start und Endpunkt. Man kann leicht einsehen, dass sich der optimale Weg immer auf den Kanten zwischen diesen Punkten befinden muss.
Noch besser sind bei statische Umgebung Sichtbarkeitspunkte, davon müsstest du hier nur 3 platzieren. Die sind aber je nach Perfektion schwierig zu berechnen.

borg

Optimizer schrieb:

Man kann die Linien genauso gut als Endpunkte gegeben haben.

ich hab ihn so verstanden das er ein bild gegeben hat. wenn er das feld schon in digitaler form als graph oder so vorliegen hat ist es natürlich was anderes.
dann muss er das aber genauer spezifizieren

Nein ich habe die Daten nicht in Graphen. Es sind linien die in einem Bitmap drinne sind. Die Schwierigkeit ist die Wände zu erkennen. Keine Eckpunkte und Sichtbarkeitspunkte sind gegeben!!!

borg

ja, dann bleib ich bei meiner methode
wenn in einem kästchen von dem raster auch nur ein pixel schwarz ist, ist es wand.
falls 100x100 nicht präzise genug ist musst du im zweifelsfalls die kästchen auf pixelgröße verkleinern.

Andreas XXL

Hallo, ich habe mal ne Frage zu A*

Den Algorithmus verstehe ich so halbwegs aber wenn ich z.B nen Spiel ala CßC habe mit z.B 512 * 512 Feldern, dann müsste es ja 512 * 512 Knoten geben.
Und von Jedem Knoten die kanten zu seinen 8 Nachbarn.
Das is doch nen bisl viel oder?

Ich habe mir überlegt, dass wenn ich z.B nur jeden 2. Knoten nehme, dann gibt es ja Felder, zu denen ich nicht gehen kann!

Wie verringert man also die Knoten- und Kantenzahl ohne "nichtbegehbahre" Stellen zu erhalten?

rapso

Andreas XXL schrieb:

Hallo, ich habe mal ne Frage zu A*

Den Algorithmus verstehe ich so halbwegs aber wenn ich z.B nen Spiel ala CßC habe mit z.B 512 * 512 Feldern, dann müsste es ja 512 * 512 Knoten geben.
Und von Jedem Knoten die kanten zu seinen 8 Nachbarn.
Das is doch nen bisl viel oder?

in den C&C versionen die 2d sind, sind es im leveleditor, wenn ich mich recht erinnere, 128*128 maximal und sie haben 4nachbarn. zudem gibt es dort nicht nur einen wegfinde algorithmus. zum einen gibt es etwas wie A*, das wird aber nur begrenzt oft aufgerufen (würde sonst bei ein paar hundert einheiten das spiel stehen lassen), und es gibt kleine lokale suchalgos, z.b. immer aufs ziel zu, wenn du auf ein hinderniss triffst, rechts abbiegen. und es gibt natürlich optimierungen z.b. wenn du mehrere einheiten selektierst, dann wird nur für die erste gesucht, die anderen versuchen dann einfach einen sehr nahen path zum ziel zu wählen sofern die einheiten in sichtweite sind.

Ich habe mir überlegt, dass wenn ich z.B nur jeden 2. Knoten nehme, dann gibt es ja Felder, zu denen ich nicht gehen kann!

Wie verringert man also die Knoten- und Kantenzahl ohne "nichtbegehbahre" Stellen zu erhalten?

heutzutage wären die maps viel zu hochauflösend für den speicherverbrauch und die performance eines normalen suchalgorithms, deswegen gibt es mehrere hierarchien, zum einen gibt es wichtige knotenpunkte im level (manchmal als raster ausgelegt, manchmal wie z.b. bei unreal auch von den leveldesignern per hand). diese knotenpunkte decken ein gewisses gebiet ab. möchte man nun eine einheit zu einer bestimmten stelle schicken, wird für die position der einheit zuständige knoten gewählt und für den zielpunkt ebenfalls. nun wird A* nur auf die knoten angewendet, so bekommt die einheit einen groben weg zum ziel.
währenddessen führt jede einheit stumpfe wegfindung zwischen den knoten druch, manchmal anhand eines ziemlich hoch aufgelösten rasters, manchmal auch anhand von geometrischen (oft konvexen) formen. diese "lowlevel" suche ist dann zwar sehr stumpf (und schnell), sie läuft aber auch nur für so lokale gebiete ab, dass diese stumpfheit nicht scheitern kann, sobald es ein problem geben würde (z.b. ein U-formiges gebilde), würden die A*-Knoten das gebiet in kleinere stücke aufteilen.

rapso->greets();