Algorithmus zur Wegfindung
lima-city → Forum → Programmiersprachen → C/C++ und D
algorithmus
anwenden
auftauchen
ausarbeitung
beliebigen stellen
beliebiger zahl
berechnen
ecke
ermittlung
hindernis
http
kur
linie
links hoch diagonal laufen
passend vorkommen
problem
punkt
spieler
url
ziel
-
Hi
Ich bin gerade dabei ein Spiel das ich mal programmiert habe weiter zu entwickeln. Bin gerade dabei die Ki, also den Computer-Spieler neu zu programmieren. Dieser muss unter anderem dazu in der Lage sein, sich auf einer 2D-Fäche mit Hindernissen gezielt von Punkt A nach Punkt B zu bewegen.
Folgende Situation:
1. Der Spieler kann hoch, runter, links und durch Kombination von z.B. links+hoch diagonal laufen.
2. Die Hindernisse sind nicht alle fest. Die können an beliebigen stellen in beliebiger Zahl auftauchen. Es gibt aber auch feste.
3. die Hindernisse haben eine Mindestgröße von ~40*40 Punkten
4. Das Feld hat eine Größe von bis zu 4000*4000 Punkten auf der sich der Spieler frei bewegen kann (bis auf die Hindernisse)
Ziel ist es jetzt mit möglichst wenig Rechenaufwand einen kuren, aber nicht unbedingt optimalen Weg von Punkt A nach Punkt B zu finden.
Die einzigen Algorithmen zum Wegfinden die ich kenne wären der A* und der Dijkstra-Algorithmus, welche mir beide nicht wirklich passend vorkommen. Kennt ihr vielleicht ne brauchbare Lösung für mein Problem?
MfG
Faultier -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Nun, wenn es nur eine Person gibt für die du das berechnen musst und sind die Hindernisse in Grenzen halten würde es sich denke ich durchaus anbieten A* zu nutzen.
Der einzige andere Ansatz der mir einfällt wäre das ganze auf Zufallsbasis zu machen. Ich kenne Simulated Annealing nur für das Traveling Salesman Problem, aber ich denke mal es lässt sich hier ähnlich anwenden. -
das hier wäre noch eine Möglichkeit.
Wobei das letzendlich glaube ich (länger her das ich das gelesen habe) auch ein a* ist.
Stichwort "Corner Graphs"
Kurz beschrieben:
A=start
B=ziel
1-Denk Dir eine Linie von A nach B
2-Guck welche hindernisse von der Linie geschnitten werden
3- such alle Ecken der Hindernisse
4-Such Dir den günstigsten weg entlang der Ecken (und da wird's wohl wieder A* sein)
edit:
Das hier finde ich übrigens allgemein zum Thema pathfinding sehr lesenswert.
Beitrag zuletzt geändert: 11.10.2010 0:09:33 von simuliertes -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
