Pathfinder

[Puccini]

Hi!

Ich hab ein kleines Hängerschen.
Ich hab eine Karte feld für Feld in einer DB abgelegt.
Dabei hat jeder eintrag die Werte X und Y abgespeichert.
Es gibt Felder die können betretten werden und felder eben nicht.
Wie errechne ich nun den kürzesten Weg über die karte ohne auf ein Feld zu kommen was nicht betretten werden darf?

GIbt es da schon was oder muss ich mich da selber ransetzen?
Danke schonmal

 

[degabs]

glaube kaum dass es da schon was gibt!
aber is doch nicht schwer, ich glaube du suchst länger als wie du zum selbre machen brauchst!
wenn du felder hast und dazu x und y werte ist das ja nicht schlimm!
einfach per schleifen und mathematik!
kommt drauf an was du willst, den schnellsten weg oder einfach nur den weg!
für den schnellsten weg brauchste ne sinus bzw cosinus rechnung, und ob du ein feld betreten darfst oder nicht fragste mit ner if abfrage ab!

 

[Asterixus]

Das ist zwar möglich, aber die Berechnungszeit würde sehr sehr lange dauern. Außerdem brauchen wir die Größe der Karte. Ist es ein Torus, ein Globus oder was?

a²+b²=c² ;)

Anhand dieser Formel berechnest du den kürzesten Weg (auch wo Hindernisse sind) zum Ziel. Nun weißt du über welche Felder du kommst. Jetzt ist angesagt, dass du alle Ausweichungen (wahrscheinlich mit for()-Schleifen, frag mich aber nicht, wie das gehen soll) berechnen musst und nun noch der Entfernung die Ausweichdistanz addieren musst.

 

[Gelöschtes Mitglied 3007]

solche algorhytmen benaspruchen einiges an rechenleistung darum solltest du dir vielleicht eine alternative überlegen wenn du nicht gerade mehrere server besitzt ;)

ansonsten guck hier mal nach Problem des Handlungsreisenden – Wikipedia

 

[Puccini]

die karte is sagen wir mal 30 felder breit und 20 hoch
der server gehört mir leider net...

Daher such ich eine möglichst rechnerschonende funktion ;)
Mir wäre der kürzeste Weg lieb.
Dabei darf nur horizontal bzw vertical gezogen werden, nicht schräg.

Gibts irgendwo tuts wie man einen pfadfinder schreibt?
Wie das Mathe aussehn muss und so.

Danke schonmal

 

[Puccini]

Ich hab mir jetzt mal nen kleinen Pathfinder/Wegfinder gebastelt.
Er orientiert sich am A*-Algorithmus.

wenn ihr ihn testen wollt hier der Link:
ragesoft

Hoffe es klappt alles.
Sollten Probleme auftauchen bitte bescheid geben!
Wenn jemand Sourcecode haben will, einfach melden. Ich räum den dann vorher noch etwas auf ;)