Hat jemand eine Ahnung von Pathfinding?

[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