finde-weg-durch-labyrinth-algo

[Illuminator-23-5]

Folgendes Problem: Gegeben ist eine Welt für ein Game gespeichert sind die daten so: wege=-, Mauern=A. d.h., eine einfache welt könnte so aussehen:

Code:

A-AA
A---
AAAA

ich möchte nun einen Algorithmus erstellen, der mir die einzelnen eckpunkte sagt, die ich entlang gehen muss, um zum zielpunkt zu gelangen:
vom Punkt [1,0] zum Punkt [3,1] würde das dann so aussehen:
Aktuelle Position:
[1,0]
Ziel:
[3,1]
Liste der zu besuchenden Punkte:
[1,1]
[3,1]

etwas schwieriger wäre dann:

Code:

--AAAA--------AAAAA
A-AAAA-AAAAAA-AAAAA
A----AAAAAAAA-AAAAA
A-AAAAAAA-AAA-AAAAA
A-AAAAAAA-AAA-AAAAA
A-AAAAAAA-AAA-AAAAA
A-AAAAAAA-AAA------
A-AAAAAAA-AAAAAAAAA
A----------------AA

Aktuelle Position:
[0,0]
Ziel:
[9,3]
Liste der zu besuchenden Punkte:
[1,0]
[1,8]
[9,8]
[9,3]

Ich tüftle schon seit tagen, aber hab immer noch keine idee, wie man so etwas machen könnte!!
kann mir irgendjemand helfen?

[edit=sakura]Code-Tags zur Formatierung gesetzt. Mfg, sakura[/edit]

[theomega]

Also:
das hatten wir schon des öffteren, aber "A Stern" sollte bei Google ein paar ergebnisse auspucken, die ganz hilfreich sind.

Ich habe irgendwo auf meiner Platte ein Delphi-Proggi rumfahren, das genau das tut, aber bis ich das gefunden habe, wirst du bei Google schneller sein.

Grüße
TO

[Sanchez]

Hallo erstmal,

Schau dir mal das hier an: Strecken auf TImage berechnen
Da hab ich ein DemoProg angehägt, dass den AStar-Algo benutzt. EInes der 2 Progs macht genau das, was du brauchst

grüße daniel