(Brauche hilfe)[PHP] mit Pathfinderprogramm

[eno_gib]

Hi,

ich möchte versuchen ein kleines Spiel Programmieren, leider fehlt mir an einigen Stellen noch das notwendige Wissen.
Könnte mir jemand sagen wie ich am besten ein Programm schreibe, das für eine
Einheit den idealen Weg auf einer karte sucht?
Die Karte wird helbwegs komplex, es gibt "Felder" auf die Einheiten nicht können, und generell haben die "Felder" unterschiedlichen Bewegungswiederstand.
Das heist, dass Einheiten sich auf einer Strasse schneller fortbewegen als auf einer einfachen Wiese, und noch langsamer werden sie im Wald oder gar im Sumpf.
Die hauptsprache des Spiels ist PHP.
Ich habe schon Lösungen wie ich auf kurtze Distanz meine Einheiten fortbewege aber sie ist sehr sehr Rechenintensiv, es muss eine bessere Lösung geben.
Ich such im Prinzip jede mögliche route ab, dass ist aber meiner Meinung nach uneffektiv, es muss einfacher gehen! Zumindest für denn Rechner dammit er nicht so ausgelastet wird. Es handelt sich um ziemlich grosse Karten, und da kann man nicht für Einheiten jedes Spielers, immer alle möglichen Routen berechnen.

Hoffe mir kann einer weiterhelfen.
Am liebsten hätte ich es, wenn mir jemand das mathematische Prinzip dahinter erklären würde, aber ein Link zu einem Tutorial, oder einem Fertigen PhP Script, wären genauso geschäzt.
Vielen Dank im Voraus
Mit freundlichen Grüßen,
eno_gib

 

[Sebbo]

Das mathematische System dahinter heißt "Graph". Bei Wikipedia: https://de.wikipedia.org/wiki/Graph_%28Graphentheorie%29

Die Fragte ist, wie du jetzt den kürzesten/besten Weg hinbekommst. Wenn du diese Frage endültig beantworten willst, dann müßtest du wohl tatsächlich alle Möglichkeiten durchrechnen. Da das seht aufwendig ist, wird in der Praxis nur ein Teil der Möglichkeiten berechnet. Das sollten natürlich die besten Möglichkeiten sein. Dazu gibt es mehrere Strategien. Mal sehen was mir so einfällt... (ich mach einfach Beispiele in Stunden, das ist einfach zu verstehen)

1. Man muss nie alle möglichen Routen berechnen. Zumindest nicht komplett.
Man kann die Berechnung eine Route dann abbrechen, wenn sie teurer (länger) wird, als die momentan günstigste.
Bsp: Günstigste Route = 3 Stunden
Sobald eine neue Route (noch in der Berechnung) 3 Stunden braucht, kann ich die restliche Berechnung dieser Route abbrechen, weil sie nicht mehr besser als 3 Stunden werden kann.

2. Für eine bestimmte Entfernung kann man einen durchschnittlichen Wert ermitteln. Wenn eine Route deutlich länger wird als dieser Durchschnitt, dann kann man die Berechnung dieser Route erstmal zurückstellen und versucht eine andere Route. (Das kann aber nach hinten losgehen, wenn der Wert stark über dem Durchschnitt liegt).
Bsp: Durchschnittliche Entfernung liegt bei 4 Stunden
Sobald eine Route (noch in der Berechnung) mehr als 5 Stunden hat, wird sie zurückgestellt, weil es vermutlich bessere gibt.

3. Bestimmte Richtungen scheinen sinnvoller als andere. Direkt auf das Ziel zu ist wahrscheinlich sinnvoller als direkt vom Ziel weg. (Könnte aber auch ne Sackgasse sein )
Bsp: Ich will von oben nach unten. Es gibt schierigkeitsgrade (z.B. Geländeart)
Ausgehend von meinen Standpunkt bestimmte ich für jeden möglichen Weg einen Wert, der angiebt, wie gut dieser Weg wahrscheinlich wird. Dabei beziehe ich die Richtung ein (nach oben = 0, nach unten = 3, nach links bzw. rechts = 1) und das Gelände, das mich dort erwartet (eben = 3, sumpf = 1, gebirge = 0). Beide Sachen addiert ergeben die wahrscheinlichkeit. Jetzt gehe ich den besten Schritt und wiederhole meine Analyse.
Dabei brauche ich diesen Schritt natürlich nicht rückwärts zu analysieren.

4. Man gibt sich mit einem "guten" Wert zufrieden und sucht nicht den "Besten". Hier gibt es zwei Möglichkeiten:
4.1. Bewertung über die Rechen-Zeit
Nach einer akzeptablen Rechenzeit nimmt man das Beste, was man hat (das machen z.B. Schachprogramme)
4.2. Bewertung über die Qualität
Sobald sich keine deutliche Verbesserung der Qualität (der Zeit, die man für den Weg braucht) mehr ergibt, bricht man ab.

5. Viele Wege würden sich irgendwann wiederholen. Diese Wiederholungen wären unsinnig zu berechnen.

So. Das fällt mir dazu erstmal ein. Natürlich kann man alles diese Möglichkeiten kombinieren.
Wenn du ernsthaft daran interesse hast, dann kauf dir dazu ein ordentliches Buch und sei gewarnt: Da kommt ne ganze Menge Mathe auf dich zu.

 

[ice-breaker]

Nejia ich würde da nun an den A*-Algorithmus denken, jedoch hat dieser keine Möglichkeit gute Wege von schlechten Wegen zu entscheiden, mir ist da auch keiner bekannt, vllt findest du über A* ein paar verwandte Algorithmen die dieses Problem angehen, oder du baust dne Algorithmus um, so dass du noch die Zeiteinheiten einbaust und Wege abbrichst die zuviele Zeiteinheiten brauchen werden

 

[eno_gib]

Ok Vielen Dank.
Hast mir ne Gute Idee gegeben.
Ich hab immer nach dem Besten Weg gesucht, aber wenn ich drüber nachdenke das haben andere Spiele auch nicht! Wie oft habe ich mich geärgert das ich bei irgend einem Spiel, Einheiten einen Befehl gebe und diese dumm in ner Sackgasse rumirren.
Danke
MfG
eno_gib

 

[eno_gib]

A algorithmus? habe schon über ihn gelesen bei Wiki,
aber gesehen oder Verstanden habe ich ihn nie..

MFG

 

[eno_gib]

Wenn es weitere Ansätze gibt würd ich sie gern höhren.
ICh hab zwar jetzt schon ne Idee wie ichs angehen kann von Sebbo bekommen aber wenn es bessere methoden gibt nur raus dammit!

THX nochmal
MfG
eno_gib

 

[ice-breaker]

Ich hab immer nach dem Besten Weg gesucht, aber wenn ich drüber nachdenke das haben andere Spiele auch nicht! Wie oft habe ich mich geärgert das ich bei irgend einem Spiel, Einheiten einen Befehl gebe und diese dumm in ner Sackgasse rumirren.

Solltest du dies rauswerfen, wäre A* das effektivste und einfachste.