JLI Spieleprogrammierung

[The Lord of Programming]

Hi,

ich hab immer mal wieder vom A* Algorythmus was im i-Net gelesen. Aber es wurde da irgendwie nirgendwo richtig erklärt.
Die googlesuche hat bei mir nur irgendein unverständliches Zeug gebracht(mit Code).
Aber mich interessiert mehr, auf was der Algo basiert und wie er funktioniert.

Kennt sich da jemand aus?
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console

Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet...

[Hazel]

Letzte Woche auf GameDev.Net... die Seite scheint irgendwie keiner zu besuchen.....

A* for Beginners:
http://www.gamedev.net/reference/programming/features/astar/
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R

[The Lord of Programming]

thx

[Fallen]

Der A* (A-Stern) Algorithmus ist ein Wegfindungsalgorithmus der den Weg sucht der am einfachsten zu gehen ist.

Dabei wird am Anfang geschätzt wie einfach der Weg zu begehen ist.

Dann werden einige Felder die zur Schäötzung passen um den Startpunkt herum bis zum Zielpunkt untersucht ob ein Weg möglich ist. Das wird einige male durchgeführt, je besser die Schätzung der Kosten desto weniger durchläufe.

Dann wird der (hoffentlich) erfolgreich gefundenen Weg in eine liste übertragen.

Das Gelände muss dazu aus einem 2Dimensionalen Array bestehen und dieses Array muss die Kosten für jedes Feld enthalten.

(Zahlen sind Kosten und nur eine Angabe)
0 - Strasse
5000 - Berg
usw.

So kann man es ermöglichen das ein Trupp Soldaten möglichst Berge meidet und stattdessen Strassen benutzt.

Zum A* Algorithmus gibt es noch eine bessere Version B* (glaub ich) der schneller arbeitet und auch auf dynamische Veränderungen (Einheit blockiert plötzlich den Weg) reagiert. Dabei wird auch mit direkten Luftlinien gearbeitet.

Quellcode hätte ich auch für dich aber nur in Delphi. (A* und der Algorithmus der für Autoroutenprogramme genutzt wird)
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[The Lord of Programming]

Aha

Aber wie wird denn das errechnet, ob der weg begehbar ist und in welche Richtung der nächste Schritt gehen soll?

btw: Den Code würde ich mir wahrscheinlich sowieso selbst machen
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console

Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet...

[Hazel]

Google gefragt. Dritten Link angeklickt.

http://www.irf.uni-dortmund.de/seminar/schlette/stdt_0.htm
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R

[Fallen]

Am ende wird überprüft welcher Weg die niedrigsten Gesammtkosten hat. So kann der schnellste Weg berechnet werden. Wie genau das gemacht wird: siehe Hazel
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[The Lord of Programming]

thx, ich hab den englischen Artikel tatsächlich verstanden(mit tatkräftiger Hilfe einese Lexikons ).
Außerdem sind meine Englischkenntnisse verbessert worden
_________________
www.visualgamesentertainment.net
Current projects: RDTDC(1), JLI-Vor-Projekt, Tetris(-Tutorial), JLI-Format
(1) Realtime Developer Testing and Debugging Console

Anschlag, Anleitung zum Atombombenbau, Sprengkörper...
Hilf Schäuble! Damit er auch was findet...