A-Star mit unterschiedlich teuren Feldern

[DeRal]

Hallo zusammen!
Ich möchte für ein kleines Spiel eine Wegfindung mit dem A-Star-Algorithmus programmieren. Der Algorithmus selbst ist ja nicht besonders schwer zu implementieren, allerdings möchte ich den Feldern unterschiedliche Werte geben können, also z.B. einem Feld mit einer Straße die Kosten 1, einem Feld mit Sand die Kosten 3 etc..
Zum Abschätzen der Gesamtstrecke (Start -> Ende) nehme ich einfach die Luftlinie. Ich muss ja aber auch für jeden Schritt von Feld zu Feld zunächst die Kosten abschätzen. Wenn ich das mit der Luftlinie mache, komme ich natürlich überall auf 1. Wenn ich so vorgehen würde, würde meine Figur evtl. anstatt einen kurzen Umweg über die schnellere Strasse zu nehmen, durch den "teuren" Sumpf laufen, weil das Feld näher am Ziel liegt.
Hat jemand einen Tipp für mich? Oder hab ich vllt. einfach irgendwo falsch gedacht? ^^

 

[zeja]

A* ist aber ja ein Suchalgorithmus... daher sollte es nicht passieren dass du einen falschen Weg läufst. Zu den geschätzten Wegkosten d.h. der Anzahl der Felder, addierst du die tatsächlichen Kosten der bisher passierten Felder hinzu. Dadurch wirst du ausgehend vom aktuellen Feld bei Betrachtung der umliegenden Felder auch das günstigste wählen. Dadurch dass deine Funktion unterschätzt und nicht überschätzt gehst du dann auch keinen falschen Weg...

Der Wikipedia Artikel dazu ist gar nicht schlecht: http://de.wikipedia.org/wiki/A*-Algorithmus