Hat jemand eine Ahnung von Pathfinding?

[Mivey]

Ich hätte da mal eine Frage. Ist es möglich ein Sript zu schreiben das es ermöglicht das sich der Hero von einem Punkt A zu einem Punkt B bewegt und dabei etwaige Hindernisse vermeidet bzw. umgeht. Den kürzesten Weg zu finden wäre auch wichtig

Ich kann mir vorstellen das so ein Script sich vom Kosten/Nutzen her nicht lohen würde, jedoch frage ich aus reiner Neugier und selbst wenn ihr mir kein Script schicken könnte wäre es nett wenn mit jemand grob sagen würde wie man soetwas überhaupt realisieren könnte. Denn momentan habe ich nicht die leiseste Ahnung wie so etwas ginge.

Frohes Neues Jahr und schon im vorhinein Danke für jede nützliche Antwort.

mfg

Mivey

[Pray]

Das er Hindernisse umgeht. Ich glaub sowas gibt es nicht.
Was du machen könntest ist ein Tagesablauf für die Person mit Move Event. Der Rest erklärt sich eigentlich von selber.

[Mivey]

ich denke schon das es gehen könnte. und ich meine mehr als bloß abstand finden und dann x und y durch move event reduzieren. das ist primitiv. es muss irgendwie möglich sein hindernisse zu umgehen. hat den niemand eine idee?. das würde mir schon reichen, falls sie umsetzbar wäre

[SMWma]

X und Y-Koordinaten und damit nach dem Terrain nachfragen???
Wenn das Terrain unpassierbar ist, weiß ich auch nicht weiter...
Aber samt den X und Y Koordinaten des Helden und denen, des Ziels[also bisher vier] und dann nochmal zwei weitere für die X und Y, um nachzufragen zu können, ob dieses Feld passierbar ist.
Wenn ja, gehe dadurch, wenn nein, Pech gehabt...
Hoffe, konnte dir weiterhelfen.

[Mivey]

du bist dir schon im klaren das man nur die Terrain ID abfragen kann? das hat nicht viel mit begehbar/nicht begehbar zu tun.

ich suche ehern nach einem script oder dem konzept für ein script das die optimale Route findet.
da reicht es nicht einfach durch das ersnächste feld, auch wenn es passierbar ist durch zugehen, denn was wäre wenn zb. genau zwischen A und B (also Ursprungspunkt und Ziel) eine Mauer verlaufen würde die zwar später offen wäre aber den Optimalsten Weg also die Gerade unmöglich macht. wie müsste ein script funktionieren um trotzdem an dieser Mauer vorbei zu kommen. ( hier wird angenommen das es eine möglichkeit gibt die mauer zu überwinden bzw um sie herumzugehen.)

[SMWma]

also.............Und die Terrain ID???
Was ist dies genau???

[Mivey]

schau mal bitte antworte NUR wenn du eine antwort auf meine frage hast und wenn du nicht einmal weißt was eine Terrain ID ist , und die hat, denke ich, NICHTS mit meinen Problem oder Frage zu tunt, was machst du hier überhaupt.
ich beantworte hier keine frage sonder stelle eine.
sorry für den harten ton aber poste nur wenn es sinn macht

[DSA-Zocker]

Ist es nicht möglich Terrain IDs für nicht passierbar (z.B. Graslandschaft_blocked) und passierbar (z.B. Graslandschaft) zu erstellen, die zwar die gleichen Eigenschaften haben, aber die jeweils auf geblockte und freie Tiles verteilt werden und die KI entsprechend handeln zu lassen? Ich bin zwar ein Anfänger, aber zumindest das Feststellen, ob man da durch kann oder nicht sollte nicht so schwer sein, wenn man die Terrain ID abrufen kann.

EDIT: Vorpost eben gelesen... aber könnte die KI nicht erst mit diesem Ansatz einige Wege zum Ziel durchrechnen und den kürzesten auswählen?

[Mivey]

Das habe ich mir auch schon gedacht aber bleiben wir beim beispiel mit A und B und der Mauer dazwischen. auchwenn ich abfragen kann ob die felder in der umgebung des helden begehbar sind. wie finde ich heraus wo die mauer umgangen werden kann dazu reicht simple abfrage nicht aus. und um einen weg zu finden müsste das script von einem punkt zum nöchsten sich erfragen aber wie findet es sich an der mauer zu recht? wie kann ermittelt werden wie die mauer am effizientesten umgangen werden kann ohne vorher xmal im kreis zu gehen?

Vorpost eben gelesen... aber könnte die KI nicht erst mit diesem Ansatz einige Wege zum Ziel durchrechnen und den kürzesten auswählen?

...

edit: diese "wege" müsten irgendwie abgespeichert werden selbst wenn in eine vari für jede richtung die der hero gehen müsste also 1-8 (diagonal geht ja auch) eine ziffer in die vari gibt und diese sich zusammenketten wäre nach 6 ziffern schluss, da die varis nur 6-stellig sind. und selbst wenn ich die wege perfekt gespeicher da hätte, wie könnte er den optimalen, also küzesten weg denn auswählen?

edit: noch etwas: es gibt doch wenn wir die kürzeste verbindung,die gerade, ausschliesen theoretisch unendlich viele verbindungen zwischen 2 punkten, da man ja auch im kreis gehen kann. wielannge soll ich dieses hypothetische script den suchen lassen? auf einer riesen map wäre das so als ob der hero, falls das ganze den funktioniert, 8 Stunden wartet nur um einen sanften bogen zu gehen.

[DSA-Zocker]

eine zufallsrichtung wählen vor einem Hindernis, weitergehen bis weg wieder frei. die zufallsrichtung wird abgespeichert und nicht mehr aufgerufen, dann folgen meinetwegen noch 2-3 nächste Versuche und der kürzeste wird tatsächlich ausgeführt. Imo müsste das so gehen, auch wenn ich eig. (fast) keine Skript-Erfahrung habe.

EDIT: erst den weg mit den zahlen speichern, in zusätzlicher Vari die zahl der schritte zusammenrechnen und dann in noch einer Vari (am besten die vor der Wegbeschreibung) abspeichern, wieviele Varis insgesamt für den Weg gebraucht wurden. (müsste mit der Vari für die schrittzahl möglich sein). der kürzeste weg lässt sich an der vari der schrittzahl ablesen, dann durch die varis der wegbeschreibung ausführen.

[Mivey]

der hero würde unendlich mal im kreis gehen, denn was wenn das ganze weiter weg vom hero ist?. nein mit zufall sollte man da, denke ich, nichts machen.

edit: das script würde dann also herumprobieren? nein das hat nichts mit berechnen zu tun. Und der Such oder Probier prozess würde ewig lange dauern. zb. bei größeren maps

[DSA-Zocker]

höchstlimit für schritte? wenn nicht bei ziel angekommen -> alles verwerfen bis auf zufallszahlen, die schon verwendet wurden.

[Mivey]

was wenn der in wirklichkeit optimalste weg also die beste lösung mehr schritte erfordert als ich zufälligerweise als höchstlimit eingeben habe? das hat nichst mit berechen sonder mit "würfeln" und zufall zu tun. sowas such ich nicht, es sollte schon eine berechnung sein.

edit: alles andere würde 1. viel zu lange dauern und 2. mit hoher wahrscheinlichkeit würde irgendeinmüll herauskommen wenn ein paar zufällige faktoren wie npcs die sich bewegen oder kleine hindernisse innerhalb der map zusammenkommen.

Edit: noch mal etwas, nehmen wir mal an es gebe gar kein lösung sprich es gebe theoretisch keine verbindung zwischen A und B, dein zufallsscript würde in diesem fall unendlich lang suchen suchen suchen und nichts würde passieren. ein script das es allerdings berechnet und nicht ausprobiert das könnte erechen das keine lösung herauskommt

Kleine info am rande: das ganze ist als pathfinding für eine maussteuerung gedacht, also der held klickt irgendwo und schwubst er läuft dahin. das versuche ich zu realisieren. und zwar relativ perfekt dh. wenn eine verbindung zwischen held und ziel dann soll diese genutz werden allerdings brauche ich dafür ein komplexes pathfinding

[DNKpp]

boah, um die uhrzeit hab ich keinen nerv mir das jetzt alles durchzulesen, vorallem nach deinem umleitungsschild wollte ich eigentlich den thread wieder zu machen, aber was solls, schreibe ich mal eine methode, die evntl noch nich genannt wurde.
an für sich ist es ja kein problem die terrain ID auszulesen, aber was machen, wenn das hinderniss im UPPER LAYER steckt?
dieser frage habe ich mich kürzlich mal gewidmet, und kam zu dem entschluss alle bode tiles auch als nicht passierbar und mit entsprechender ID nochmals auf dem chipset zu platzieren und sie unter den nicht passierbaren dingen zu positionieren. gut, das ging ja so weit auch recht gut, nur umständlich.
da kam mir eine zweite idee, ich setze alle hindernisse im upper layer als events, sprich der upper layer wäre damit hindernis los.
so, jetzt sag man natürlich, das ist doch genau das gleiche, aber weit gefehlt.
WARNUNG: bei dieser methode werden seeeehr viele variabeln drauf gehen.
so, was habe ich eigentlich vor?
ich versuche alle meine hinderniss events in varis zu speichern. d.h. wenn die vari auf 1 steht = hinderniss, wenn auf 0 = passierbar.
dazu erstelle ich mir ein event auf autostart, das bei map betreten aufgerufen wird und mir alle events bis zu einem abbruch event callt
(ich erkläre nicht wie man das macht, sondern nur die methode. ich setze einen gewisse erfahrung einfach mal vorraus)
das abbruch event soll verhindern, das der maker ins leere greift und ein
nicht vorhandenes event aufrfen will, das endet sonst in einem bösen fehler.
jedes event auf der karte muss nun also die seite 1 zum setzen frei haben. gecallt gibt es dann die koords an, und die werden dann für die formel benutz,
die mir berechnet, in welcher vari ID ich speichern möchte.

v = s + ( y * xmax + x)

v = die vari ID
s= der startwert, also die niedrigeste vari ID in der ich speichern möchte
y = y koord des events
xmax = die maximale mapbreite, die ich mit dieser formel berechnen möchte
x = x koord des events

so, nun haben wir also praktisch alle hinderniss events in einer rekonstruirbaren formel gespeichert, und können nun jederzeit wieder darauf zugreifen.

zum pathfinding im allgemeinen kann ich nur den A* algorythmus empfehlen
http://de.wikipedia.org/wiki/A*-Algorithmus

ich wollte euch nur eine andere methode zur feststellung der hindernisse auf der map bieten. ich denke das ist so ziemlich die einfachste methode, und mit dem 500000 vari patch von iwem is das auch sicherlich kein problem xD

ich werde mich auch demnächst nochmal intensiver mit dem A* befassen müssen, dann kann ich genaueres sagen, das was ich bis jetzt beschrieben habe ist graue theorie, also nichts handfestes was ich ausprobiert hätte.
ich gebe keine garantie darauf, das der A* aufm maker umsetzbar ist xD

mfg

EDIT:
ich weiß, ich habe jetzt nicht direkt zu pathfinding beigetragen, aber ich finde das auch ein wichtiges thema.

was mir auch eingefallen ist, das es ja auch bewegliche hindernisse gibt. da würde die "ich blocke im down layer" - methode auch nicht funktionieren, von daher könnte man auch noch eine kleinere liste für die beweglichen events erstellen, und die dann vor jedem pathfinding erneuern lassen. nur eine idee xD

[Mivey]

oke dann hab ich also diese formel und was dann? ich meine ok dann hab ich eben für jedes hinderniss eine ID aber wie nützt mir das? also im prinzip müsste es also fragen (durch ein event oder bloß varis) ob zwischen mir und dem ziel ein hinderniss ist. das geht dank dieser formel. aber wie geht es dann drum herum um das hindernis? wie wird der weg berechnet? (sorry um 4 uhr morgens funktioniert mein hirn irgendwie nich)

[DNKpp]

ja das ist doch das gleiche xD
dann frägst du das feld daneben ab, ob es frei ist oder nicht.
wenn ja, versuch es da lang^^
wenn nicht, geh in die andere richtugn, falls das auch dicht ist, musste einen schritt zurück und da rum probieren^^
so im prinzip ist es ein wege wegstreichen. du hast sagen wir 1000 wege zur verfügung aber nur einer ist der richtige, du gehst die dann alle nach und nach ab.
ich würde dir für ein pathfinding empfehlen, das der bildschirm sich IMMER auf der spielfiegur befindet. somit kann man nicht so weit klicken und die rechenzeiten sind deutlich geringer. das machen auch die kommerziellen spiele so, siehe diablo und sacred und so^^

[Mivey]

das hab ich auch so
und es gibt mehr als eine lösung zb. könnte man ja auch im kreis gehen aber ich probiersmal wie du gesagts hast. nur obs dann gleich den kürzesten weg findet weißichnicht.

[DNKpp]

ließ dir mal die beschreibung zu dem A* algorythmus durch..
auf anhieb den richtigen weg zu finden ist so gut wie UNMÖGLICH!
es werden mehrere versuche gebraucht.
lies dir das mal durch und schnapp dir ein paar tuts zu dem algorythmus, und dann versuch ihn mal nachzubauen. lachsen hat es glaube ich mal gemacht, nur hab ich nie ein script gesehen xD
also wie gesagt, der algorythmus ist dazu da um zu suchen, und nicht dazu sofort den richtigen weg zu erwürfeln^^

mfg

[Mivey]

oke ich denk jetz hab ich nen einblick in das thema. naja ist wohl ziemlich kompliziert. müsste herumprobieren.
und im schlimmstem fall scheiss ich auf den ganzen müll und lass den hero einfach zum ziel teleportieren XD

[DNKpp]

lol, sicher auch ne variante, aber wie gesagt, es ist machbar, und an solchen aufgaben wächst man^^

ach ja, btw frohes neues xD