Du musst den begehbaren Bereich in konvexe Polygone aufteilen. Diese zeichnen sich dadurch aus, daß innerhalb einer solchen Fläche jeder Punkt direkt (ohne Verlassen der Polygonfläche) erreichbar ist. Ich stelle zunächst fest, in welchem Poly ich mich befinde, und in welchem der Zielpunkt ist - dies mache ich mit einer zweiten Bitmap, in der die einzelnen Polies verschiedene Farben haben, dann prüfe ich, auf welchem (virtuellen) Pixel dieser Map der Mauszeiger und der Spieler ist.
Für die einzelnen Verbindungen zwischen den Polygonen habe ich aus Geschwindigkeitsgründen zwei Tabellen, in der einen steht, über welche Umwege ich von Poly A nach Poly B komme, in der anderen, an welcher Position die jeweiligen Übergänge bei benachbarten Polygonen sind (das verhindert hackeliges Laufen).
Den Trick mit der zweiten Bitmap hab' ich mir bei Sierra abgeschaut, ist ziemlich dreckig, aber einfach und schnell.
WiDDY.
Smith & Wesson - The original Point and Click interface!
Ich kann' Dir auch 'nen C++ Source schicken, allerdings ist der für den Gameboy Advance und dank diverser Optimierungen nicht mehr wirklich hardware-unabhängig, außerdem weder kommentiert noch lesbar (Stichwort Bitshifting statt Multiplikation etc.). Gameboy halt.
WiDDY.
Smith & Wesson - The original Point and Click interface!
Au fein, Pathfinding. Ich hatte auch vor ein paar Jahren mal (ohne Tutorial, ohne sonstwas) versucht, die kürzeste Verbindung zweier Punkte in einem nichtkonvexen Polyeder zu finden (ohne den "Umweg" über konvexe). Bis auf ein paar hässliche Fälle wars mir auch einigermaßen gelungen - war aber weder schön, noch elegant, noch wirklich korrekt. Hatte ich damals aber viel Spaß mit
WiDDY hat geschrieben:(Stichwort Bitshifting statt Multiplikation etc.).
Pathfinding ist wirklich eine schöne Sache. Leider habe ich hier nur einen Delphi-Code rumliegen, aber im Web gibt es genügend Sourcen, da habe ich keine Bedenken.
Zum Thema BitShifting habe ich mal vor zehn Jahren einen Vortrag gehalten, die Gesichter waren spitze. Mittlerweile halte ich diese BitManipulationen für Zeitverschwendung. Für PDAs und so ein Zeug ist es noch 'notwendig', aber das gibt sich auch mit der Zeit. Irgendwie vermisse ich diese BitSchieberei auch nicht mehr. Kennt hier einer NANs (Not-A-Numbers) ?
Bitgeschubse ist am GBA unglaublich effektiv. Ich dachte eigentlich, daß ich seit dem C64 aus dem Alter raus bin, aber das bringt hier einfach zu viel. Zyklen zähle ich aber nicht mehr ("wenn ich jetzt anstatt 2 zu addieren 257 abziehe...")
WiDDY.
Smith & Wesson - The original Point and Click interface!
