Line-of-sight-Algo als Tabelle
Übersicht
BlitzMax, BlitzMax NG Allgemein
|
BladeRunnerModeratorBetreff: Line-of-sight-Algo als Tabelle |
 Mi, Nov 26, 2014 14:41Antworten mit Zitat 
|
|---|---|---|
|
Hallo ihr Lieben,
folgende Problemstellung: Ich möchte béi einem tile-basierten Game einen Fog of War implementieren und benötige dafür einen LOS-Algorithmus. Es soll kreisförmig um die aktuelle Position herum auf Sichtbarkeit geprüft werden und das Flag auf der Karte für sichtbar gesetzt werden wenn das aktuelle Feld von der jetzigen Position aus sichtbar ist und innerhalb der Sichtweite liegt. Wenn ein Hindernis vorhanden ist soll der Algo möglichst alle weiter weg liegenden Felder dieser Richtung nicht weiter beachten. Problem dabei: Der Code soll möglichst schnell sein und ohne mathematisch teure Operationen wie Sinus und co. auskommen. Ich habe schon mit Bresenham gespielt, hier hat man aber ja das Problem dass wenn man nur die Linienprüfung auf die Randfelder der Sichtbarkeit anwendet es zu fehlenden Pixeln innerhalb des Kreises kommen kann (Moiree-Muster). Meine Idee wäre nun das Ganze anhand einer Tabelle durchzuführen, aber ich scheitere beim Durchdenken dieser Möglichkeit. Vielleicht hat ja auch jemand von euch einen anderen Ansatz. Das ganze MUSS mit möglichst wenig geprüften Feldern und ohne Sin etc. auskommen, da ich vorhabe den Code wenn er erst mal unter Max läuft auf einen 6502-Prozessor zu adaptieren. Hat jemand ein paar gute Ideen für mich? |
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
Tritium |
Mi, Nov 26, 2014 19:28 Antworten mit Zitat
|
|
|---|---|---|
| Hast ne PN. | ||
|
SpionAtomBetreff: Statisch oder dynamisch |
Mi, Nov 26, 2014 19:32 Antworten mit Zitat
|
|---|---|---|
|
Ist die Karte statisch? Gibt es dynamische Objekte, die sich dem Sichtbereich entgegen stellen könnten? Von welchen Größenordungen sprechen wir hier? Wieso ist das ein BMax-Problem?
http://www.redblobgames.com/articles/visibility/ Gibt einen anschaulichen Einstieg. http://www.roguebasin.com/index.php?title=FOV Und auch hier gibt es Inspiration. |
||
| os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080 | ||
|
|
BladeRunnerModerator |
Mi, Nov 26, 2014 21:39 Antworten mit Zitat
|
|---|---|---|
|
BMax nur weil die Erstimplementierung in BMax erfolgen wird. Ich arbeite da immer erst mal vor.
Danke schon für die Links, auch den per PM, ich werd mich mal reinlesen und melde mich bei Bedarf wieder. Größenordnung ist rechnerspezifisch eher klein, als Maximalradius kommen 12 Tiles in Betracht. Allerdings ist der entsprechende Rechner mit knapp einem MHz unterwegs und kennt keinen mathematischen Coprozessor. Dynamische Objekte ja, wobei ich im schlimmsten aller Fälle darauf verzichten könnte. |
||
|
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92 |
||
|
DAK |
Do, Nov 27, 2014 12:06 Antworten mit Zitat
|
|---|---|---|
|
Hmm, kniffelig.
Ich hab das nicht ausprobiert, aber schau mal, wie das klappt: Schritt eins: Connected Component Labeling für alle Hindernisse. Das geht recht einfach und lässt sich einmalig vorberechnen, Bzw. muss nur bei jeder Änderung ein Mal ausgeführt werden. Damit kriegst du jedes einzelne zusammenhängende Hindernis, egal wie viele Tiles es groß ist. Schritt zwei: Von der Sicht des Spielers aus suchst du den linkesten und rechtesten Punkt jedes Hindernisses. Schritt drei: Von diesen beiden Punkten aus malst du mittels Bresenham eine Gerade bis an den Rand des Sichtradius. Schritt vier: Mittels Floodfill malst du den Teil den Teil im Schatten aus. 
Das sollte ohne höhere mathematische Funktionen auskommen und auch halbwegs schnell sein, da (bei geringerer Hindernisdichte) nur recht wenige Felder überprüft werden müssen. Edit: Hab mir gerade das Ganze noch mal durchgedacht. Schritt 2 könnte ohne komplexere mathematische Funktionen etwas schwieriger werden. Um das einfacher zu machen (kostet dafür in Schritt 3 mehr) könntest du von jedem Hindernis-Tile eine Linie nach hinten ziehen und dann vom Spieler aus den Floodfill starten, mit dem du alles sichtbare einfärbst. Alles was der Floodfill nicht erwischt ist unsichtbar. Dann kannst du dir auch das Connected Component Labeling in Schritt 1 sparen. Edit2: Blödsinn, Schritt 2 lässt sich doch halbwegs einfach machen. Ein paar Additionen und eine Division für jedes Tile in jedem Blob. |
||
| Gewinner der 6. und der 68. BlitzCodeCompo | ||
Übersicht
BlitzMax, BlitzMax NG Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group