• Registrierungsdatum: 09-05-2001
  • Beiträge: 147

Thema: Pathfinding

Hi!<BR>Koennt mir jemand bitte mit Pathfinding weiterhelfen?<BR>Ich hab mir ein paar Gedanken gemacht, aber noch keine besonders gute Loesung gefunden:<BR>1. Ich koennte zwei Linien ziehen. Eine vom Startpunkt und eine vom Zielpunkt. Dann die so lange drehen (anderer Winkel), bis sie sich schneiden. Das funzt aber nur um eine Ecke.<BR>2. Ich koennte einfach auf den Zielpunkt loslaufen und wenn ich auf ein Hindernis stosse nach links/rechts laufen und dann wieder versuchen, aufs Hindernis zuzugehen. Das ist schon besser, funzt aber nicht bei folgendem Beispiel:<BR>(Stellt das Feld dar. X=Hindernis, S=Start Z=Ziel)<BR><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre><BR>XXXXXXXXXX<BR>X   Z    X<BR>XX XXXXXXX<BR>X  X     X<BR>X  X S   X<BR>X        X<BR>XXXXXXXXXX<BR></pre><HR></BLOCKQUOTE><BR>3. Einfach an einer Wand zu bleiben und immer weiterzulaufen kann den Weg viel zu lange machen<BR>4.Vielleicht kann ich es irgendwie so machen, dass ich versuch, es wie in einem Malprogramm auszufuellen um so den besten Weg zu finden. Ist aber nur ne Idee und ich weiss noch nicht, wie das genau funktionieren soll  [img]images/icons/wink.gif" border="0[/img].<P>Naja, vielleicht habt ihr ja ne Loesung?

awakening's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

Later...

mfG whitehouse
  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

Wie ist Pathfinding gemeint? Der optimale Weg? Das ist wirklich kompliziert, dazu gibts Bücher.

mfG whitehouse
  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

Aber jetzt mal ne fiese Idee: einfach alle Wege testen.

mfG whitehouse

5 Antwort von matho

  • matho
  • Moderator
  • Offline
  • Herkunft: Deutschland
  • Registrierungsdatum: 21-01-2001
  • Beiträge: 1.352

Re: Pathfinding

Also, korrigier mich, falls ich falsch liege:<BR>Wenn die Wände definiert sind, sind auch die Lücken definiert - eine Lücke ist eine Wand ohne Fortsetzung.<BR>Die Anweisung sollte also heißen (Vom Startpunkt aus gesehen):<BR>Suche eine Lücke und addiere 1 (in der jeweiligen Richtung). Von diesem Punkt suche die nächste Lücke und<BR>addiere wieder 1 (um auch über jene Hürde zu kommen) usw.usf. bis irgendwann suche Grade zum Zielpunkt.<BR>Und die Schlußgrade ist wieder eine, die keinen Schnittpunkt mit einer Wand hat.<BR>Und diesen Vorgang wiederholen, bis die kleinste Summe aller Teilstrecken gefunden ist.<P>Hoffe, ich habe mich einigermaßen verständlich ausgedrückt<P>gruß <P>matho

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

Um das aber einfacher zu finden müsste man doch zumindest teilweise an den Wänden gehen, oder?

mfG whitehouse

7 Antwort von matho

  • matho
  • Moderator
  • Offline
  • Herkunft: Deutschland
  • Registrierungsdatum: 21-01-2001
  • Beiträge: 1.352

Re: Pathfinding

Versteh ich nicht so recht.<BR>Weil, die Grade durch die Lücke ist doch definiert als eine, die keinen Schnittpunkt<BR>mit einer Wand hat.<P>gruß<P>matho

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

Und wie ist der Algorithmus für eine Linie?

mfG whitehouse

9 Antwort von odoggy

  • Registrierungsdatum: 08-02-2001
  • Beiträge: 90

Re: Pathfinding

uup, einmal zu viel<p>[ 23.05.2001: Beitrag editiert von: odoggy ]

Member of Vatos Locos

10 Antwort von odoggy

  • Registrierungsdatum: 08-02-2001
  • Beiträge: 90

Re: Pathfinding

Hehe, kommt mir irgendwie bekannt vor.<BR>Bei mir war es damals ne Maus die ein Käsestück finden sollte, erschwerend hinzu kam des es mehrere Käsestücke waren und die Maus nun den kürzesten Weg finden mußte um alle Käsestücke aufzuessen (ist wie das Traveling-Salesman-Problem).<P>Zum Thema:<P>Also als Speichertyp brauchst du eine Schlange (Fifo - first in first out).<P>1) <BR>-Überprüfe oberen Nachbarn<BR> wenn kein Hinderniss makiere mit 1 und lege Koordinaten des Punktes in Schlange<BR>-Überprüfe rechten Nachbarn<BR> wenn kein Hinderniss markiere mit 1 und lege Koordinaten des Punktes in Schlange<BR>...<BR>usw. für alle vier Nachbarn<BR>2) Nehme eine Koordinate aus Schlange<BR>-Überprüfe davon oberen Nachbarn<BR> wenn kein Hinderniss makiere mit 2 und lege Koordinaten des Punktes in Schlange<BR>...usw<P>irgendwann ist man am Ziel:<P><BR><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre><BR>XXXXXXXXXX<BR>X   Z    X<BR>XX XXXXXXX<BR>X  X 1   X<BR>X  X1S1  X<BR>X    1   X<BR>XXXXXXXXXX<BR></pre><HR></BLOCKQUOTE><BR><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre><BR>XXXXXXXXXX<BR>X   Z    X<BR>XX XXXXXXX<BR>X  X212  X<BR>X  X1S12 X<BR>X   212  X<BR>XXXXXXXXXX<BR></pre><HR></BLOCKQUOTE><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre><BR>XXXXXXXXXX<BR>X   Z    X<BR>XX XXXXXXX<BR>X  X2123 X<BR>X  X1S123X<BR>X  32123 X<BR>XXXXXXXXXX<BR></pre><HR></BLOCKQUOTE><P>usw, bis Treffer<P><BLOCKQUOTE><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><HR><pre><BR>XXXXXXXXXX<BR>X989Z    X<BR>XX7XXXXXXX<BR>X76X21234X<BR>X65X1S123X<BR>X54321234X<BR>XXXXXXXXXX<BR></pre><HR></BLOCKQUOTE><P>Nun muß man noch vom Ziel aus den Weg rekunstruieren. <BR>1) <BR>-Merke Zielkoordinate<BR>-Suche Nachbar mit Schrittgröße 10-1 (also 9)<BR>2)Merke Koordinate<BR>-Suche Nachbar mit Schrittgröße 9-1 (also 8)<P>irgendwann ist man wieder am Start und hat sich dazu den ganzen weg in Form von Koordinaten.<p>[ 23.05.2001: Beitrag editiert von: odoggy ]

Member of Vatos Locos
  • Registrierungsdatum: 09-05-2001
  • Beiträge: 147

Re: Pathfinding

Danke oddygo. Genau das, was ich gebraucht habe!

awakening's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Pathfinding

OR

mfG whitehouse