spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wieso? da gibt es auch ein startpunkt ein zielpunkt und eine 2D karte mit den feldangaben begehbar oder unwegsam.

Zitat von »"Crash"«

Wie geht denn eigentlich Pathfinding in Strategiespielen? Die Charaktere können dann ja schlecht einem Pfad folgen.

Wie bereits angesprochen: Mit dem (bzw. einem modifizierten) A*-Algorithmus, wobei man natürlich auch andere Algorithmen heranziehen kann.

durch die iso perspektive geht das doch auch einfacher, denk ich mir.
da sind die karten größtens teils ja sowieso zusammengestückelt aus vor gefertigten stückchen landschaft

auf der dusmania gabs nen vortrag zu dem thema (von ein paar schweizern glaub ich). so weit ich mich erinnere hatten die was mit dem Dijkstra-algorithmus
vorgeschlagen das gegenüber von A* einige vorteile hatte....

Ich wüsste nicht, welche Vorteile der Dijkstra-Algorithmus gegenüber dem A*-Algorithmus im Allgemeinen haben sollte...

beim a* berechnest du wohl fuer alle pfade die laenge und entscheidest dann
erst welcher der kuerzeste ist waehrend du beim dijkstra nur den kuerzesten berechnest.
so wurde es jedenfalls gesagt so weit ich mich erinnere.
kenn den a* naemlich nicht.

ps: die algo klausur im 1. semster hab ich auch ohne kenntnise von dijkstra
gepackt....

ergo: eigentl. hab ich gar keinen plan

Zitat von »"0x00000023"«

beim a* berechnest du wohl fuer alle pfade die laenge und entscheidest dann
erst welcher der kuerzeste ist waehrend du beim dijkstra nur den kuerzesten berechnest.

Das ist falsch! Wenn überhaupt ist es umgekehrt, denn Dijkstra generiert alle möglichen Wege, bis der Zielknoten erreicht ist und benutzt als Kostenfunktion lediglich die Kosten vom Startpunkt bis zum aktuell betrachteten Knoten, während A* eine Heuristik benutzt, um zuerst die Wege zu betrachten, die der Heuristik nach am kürzesten sind.
Auf einen Punkt gebracht vereint der A*-Algorithmus die Vorteile von Dijkstra und von Best-First-Search, ist also nicht nur optimal, sondern auch optimal-effizient

na ich sag ja dass ich von beiden keinen plan hab sondern nur das
wiedergebe an was ich mich noch erinnere
aber du hast recht, ich hab mir kurz die artikel bei wiki durchgelesen
und da steht mehr oder weniger genau das.

ich wär mit der aussage "optimal" generell etwas vorsichtiger

Zitat von »"0x00000023"«

ich wär mit der aussage "optimal" generell etwas vorsichtiger

Vollkommen richtig. Ist ja auch nicht meine Meinung, die ich hier vertrete obwohl außer Frage steht, dass Dijkstra und A* optimal sind. Das ist nämlich bewiesen (zumal man es mit dem "bloßen Auge sehen" kann).
"Optimal-effizient" ist so 'ne Sache! Aber man kann "optimal-effizient" ja auch so verstehen, dass es ZUR ZEIT keinen effizienteren Algo gibt