Bastard Fragtura

Übersicht Kommentare Worklogs


DAK

Link zu diesem BeitragMo, Sep 09, 2013 00:20
Wenn du deinen Pathfinding-Algo richtig machst, dann braucht der für ne Map dieser Größe nicht mal eine MS für 20 NPCs, du musst ihn nur richtig anpacken.

Sonst nette Sache!
Gewinner der 6. und der 68. BlitzCodeCompo

C--

Link zu diesem BeitragDi, Sep 10, 2013 17:42
Für Pathfinding kann ich für den Anfang http://de.wikipedia.org/wiki/Dijkstra-Algorithmus empfehlen.

DAK

Link zu diesem BeitragDi, Sep 10, 2013 21:20
Der Dijkstra klingt am Anfang recht kompliziert, ist aber sehr einfach, vor allem, wenn man sich die Animation auf Wiki anschaut. Ist eigentlich wirklich ganz einfach.

Wenn du dann kein pixelgenaues Pathfinding machst, sondern in jedem Level Knoten an die wichtigen Stellen setzt, dann hat der Dijkstra einen Pathfinding-Durchlauf in ein paar duzend Nanosekunden durch, wenn überhaupt.

Es ist wirklich nicht so schwer. (Hab mich auch nie dran getraut, dann haben wir den Algo in der Uni gemacht, und ich war voll verblüfft, wie einfach der ist).
Gewinner der 6. und der 68. BlitzCodeCompo

Hubsi

Link zu diesem BeitragMi, Sep 11, 2013 14:43
In anderen Projekten habe ich mit A* gearbeitet und dieser braucht seine Zeit. Jetzt nicht wirklich lange, doch gerade bei so offenen (bzw. "leeren") Maps wie sie hier verwendet werden hat er doch zu tun. Gepaart mit dem Faktor das sich die Situation nahezu laufend ändert habe ich einen Pathfinding-Algo performancetechnisch gar nicht erst weiter in Betracht gezogen. Ich werde mir den Dijkstra und seine Arbeitsweise mal genauer ansehen, aber wenn er nicht massive Vorteile bringt wird er den Weg in dieses Projekt nicht mehr finden. Der KI-Teil hat schon einiges an Code zusammen und entsprechend tiefliegend ist das ganze in sich verbunden. Ich habe mir ehrlich gesagt noch keine Gedanken dazu gemacht, aber erfahrungsgemäß ist es nicht das angenehmste den Quatsch nochmal auseinanderzupflücken. Mal sehen wie sich das noch entwickelt und vielen Dank natürlich auch für den Link Very Happy
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

DAK

Link zu diesem BeitragDo, Sep 12, 2013 08:44
Dijkstra und A* sind sich sehr ähnlich. Der Hauptunterschied ist, dass A* von rechteckigen, gleich großen Feldern, die immer und nur mit ihren Nachbarn verbunden sein können, als Basis ausgeht, wogegen Dijkstra von Knoten, die mit Kanten verbunden sind, ausgeht.

Wenn man den A* mit Feldgröße 1x1 Pixel macht, dann hat er viel zu tun. Dann hast du nämlich schon bei 800x600 480000 Felder zu überprüfen.
Nimmt man für den A* eine Feldgröße von 16x16 Pixel hat man bei 800x600 nur noch 1875 Feder zum überprüfen. Das ist schon viel viel wengier.

Für den Dijkstra würdest du nicht alle Felder verwenden, die es gibt (wie z.B. die unerreichbare Unterseite der Decke), sondern nur Schlüsselpunkte als Knoten nehmen. Dazu habe ich hier: https://www.blitzforum.de/upload/file.php?id=12578 mal auf deinem Beispielbild mögliche Knoten draufgesetzt. Wie du siehst, sind das wirklich nicht viele. Für die ganze Map würde das ziemlich sicher <100 bleiben. Das ist für einen Pathfinding-Algo wirklich nicht schwer durchzurechnen.

Du wirst den Dijkstra aber noch etwas erweitern müssen, der kann nämlich nur ungerichtete Kanten (also welche, wo man in beide Richtungen gehen kann). Du wirst aber teilweise auch gerichtete Kanten brauchen (da du zwar wo runter springen kannst, dort aber nicht mehr wieder rauf springen kannst). Diese Erweiterung ist nicht schwer, du musst dir nur zu jeder Kante dazuspeichern, ob sie gerichtet ist, und in welche Richtung, und wenn du dann zu dieser Kante in Gegenrichtung kommst, sie einfach nicht entlang gehen.

A* vs Dijkstra: Kann jede Map so ziemlich unbehandelt ablaufen. Da musst du die Maps kaum vorbereiten dafür. Beim Dijkstra wirst du alle Knoten und Kanten manuell setzen müssen (mach dir dafür eventuell einen billigen Mapeditor). Dafür wird der Dijkstra ingame deutlich schneller und genauer ablaufen (genauer deswegen, weil der A* seine Knoten nur anhand des von dir eingestellten Rasters verteilt. Beim Dijkstra kannst du die Knoten und Kanten beliebig platzieren.) Außerdem musst du beim Dijkstra noch Kantengewichte einfügen (die sagen im Grunde aus, wie schwer es ist / wie lang es dauert, von einem Knoten zu dem nächsten zu kommen), das brauchst du beim A* nicht. Das kannst du aber von deinem Mapeditor automatisch machen lassen.
Gewinner der 6. und der 68. BlitzCodeCompo

Addi

Link zu diesem BeitragSa, Nov 23, 2013 21:38
Freue mich schon auf die Demo Very Happy
Dann kommts neben Bastard Air, welches ich übrigends für extrem gelungen finde, mit in mein Spieleordner rein Wink
BP/B3D/BMax : Lerne Java : Früher mal Lite-C : Gewinner BCC 62

Hubsi

Link zu diesem BeitragSo, Nov 24, 2013 19:59
Freut mich das Dir die Vorgängerversionen schon gefallen haben Very Happy Ich denke bis zur publikumsfähigen Version es ist nicht mehr allzu weit hin zzgl. unvorhersehbarer Bugs, Verzögerungen und anderer Fehler Smile
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...


Übersicht Kommentare Worklogs