Berechnung sichtbarer Felder

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

 

Xar

Betreff: Berechnung sichtbarer Felder

BeitragMi, Okt 14, 2009 11:53
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich benutze eigentlich BlitzMax, aber da mein Problem eher mathematischer Natur ist, kann mir hier vielleicht auch jemand einen Schubs in die richtige Richtung geben.

ich veranschauliche mein Problem mal an einem stark vereinfachten Beispiel:

Ich habe ein Spielfeld von z.B. 15 x 15 Quadraten. Somit habe ich ein Koordinatensystem mit einer x- und einer y-Achse von je 0-14.

Die Position des Spielers ist immer 7,7, also genau in der Mitte. Wenn nun das Spielfeld gezeichnet wird, haben wir vereinfacht gesagt grüne Felder (=freie Felder) und weisse Felder (=Hindernis).

Nun möchte ich aber beim Aufbau des Spielfeldes beim Setzen eines jeden Feldes (egal ob grün oder weiss) prüfen, ob die Sicht von der Mitte aus (Spieler) frei ist oder nicht. Wenn Sie nicht frei ist, setze ich ein schwarzes Feld (=nicht sichtbar). In einem einfachen Beispiel wäre das dann so, wenn gleich oberhalb des Spielers ein Hindernis wäre (bei 7,6), wäre der obere Viertel (richtung obere Spielfeld-Ecken) alles schwarz.

Ich hoffe, es ist einigermassen klar, was ich meine. Wie berechnet man das? Es ist ja auch so, dass ein Feld nicht gleich als unsichtbar gilt, sobald die Sichtline ein Hindernis nur leicht streift. Wenn man wirklich eine Linie von der Mitte am Hindernis vorbei ziehen würde, sollten nur jene Felder unsichtbar sein, welche mindestens zur Hälfte nicht gesehen werden.

Für einen Tipp bin ich sehr dankbar...

Gruss
Xar

SpionAtom

BeitragMi, Okt 14, 2009 12:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Bei einer Auflösung von gerade mal 15x15 Feldern kannst du einfach vom Mittelpunkt zum Rand hin gedanklich Linien ziehen, und jeden Punkt auf der Gedankenlinie auf Hindernis/freies Feld prüfen.
Wenn das Feld frei ist, gehe ein weiteres Feld nach außen und prüfe
Wenn das Feld nicht frei ist, ist ab da alles dunkel - dann machst du ca 10° weiter eine neue Gedankenlinie und prüfst sie.

PS: Wenn du Bilder mit uns teilen möchtest, musst du sie hochladen, zb hier ins Archiv..
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
 

Wendigo

BeitragMi, Okt 14, 2009 12:12
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich würde mit ATan2 den Winkel vom Spieler zum jeweiligen Zielfeld bestimmen und anschließend in einer Schleife den Ausgangspunkt schrittweise in Richtung Zielfeld setzen.
Wenn eine Kollision mit einem unbegehbaren Tile stattfindet setzt du eine boolsche Variable auf "True" und wertest diese am Ende aus.
Die Schrittweite müsstest du je nach Performance erhöhen oder verringern.
 

Xar

BeitragMi, Okt 14, 2009 12:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Danke für den Hinweis mit den Bilder, Spion Surprised

ich glaube, so einfach ist es leider nicht, weil diese "gedankliche Linie" nicht schön brav den Feldern entlang läuft, sofern sich das Hindernis nicht genau bei 0° oder 45° oder 90° usw befindet. Somit sind viele Felder nicht "ganz sichtbar" oder "ganz unsichtbar", sondern theoretisch nur teilweise.

das Spielfeld sieht im Moment im Prinzip so aus:

user posted image

Wenn ich nun diese gedankliche Linie (im folgenden Bild blau) ziehe, dann geht die ja durch diverse Felder. Und das nicht schön den Feld-Rändern entlang. Während beispielsweise beim Feld an der Pos 5,0 nur ein kleines Eck nicht sichtbar wäre, und das Feld somit grün bleibt, ist bei Pos 5,2 der grösste Teil des Feldes unsichtbar (wenn auch nicht das ganze Feld), und somit Feld = schwarz:

user posted image

*grübel*
 

Xar

BeitragMi, Okt 14, 2009 12:40
Antworten mit Zitat
Benutzer-Profile anzeigen
Hatte grad noch die Idee: eigentlich geht es um die genaue Mitte jeden Feldes. Befindet sich von der Mitte des roten Quadrates aus gesehen die Mitte eines Quadrates nicht in Sicht (liegt also zwischen den blauen Linien), dann muss das Feld schwarz sein.

Das würde dann bedeuten, dass ich bei jedem Feld eine Linie ziehe von der Mitte des Feldes zur Mitte des roten Quadrates. Nun muss ich nur noch wissen, wie ich programmtechnisch diese "Linie" ziehe und dann vom roten Quadrat aus Pixel für Pixel der Linie entlang nach aussen gehe und prüfe, ob die Linie durch ein Hindernis-Feld geht. Wenn ja, setze ich das aktuelle feld schwarz, ansonsten grün.

SpionAtom

BeitragMi, Okt 14, 2009 12:48
Antworten mit Zitat
Benutzer-Profile anzeigen
Hier ist meine Feldweise Methode, allerdings gerade bei diagonalen Mauern noch sehr unzuverlässig:
(BlitzBasic)
BlitzBasic: [AUSKLAPPEN]
Const xr = 15, yr = 15, g = 20
Graphics xr * g, yr * g + 16, 0, 2
SetBuffer BackBuffer()

Dim feld(xr - 1, yr - 1), sichtfeld(xr - 1, yr - 1)
wsteps = 1
.dataFeld
Data " "
Data " "
Data " # # "
Data " # # "
Data " "
Data " "
Data " "
Data " "
Data " ### # "
Data " # "
Data " # "
Data " "
Data " "
Data " "
Data " "
Restore dataFeld
For y = 0 To yr - 1: Read zeile$: For x = 0 To xr - 1: feld(x, y) = (Mid(zeile$, x + 1, 1) <> " "): Next: Next



ClsColor 200, 200, 200
Repeat


posx = MouseX() / g
posy = MouseY() / g
wsteps = (360 + wsteps + MouseZSpeed()) Mod 360
Text 0, 0, wsteps: Flip()


;Sichtfeld berechnen
w = 0
Repeat
sicht = True
For r = 1 To g * Sqr(2)
px = posx - Sin(w) * r
py = posy - Cos(w) * r
If px < 0 Or py < 0 Or px > xr - 1 Or py > yr - 1 Then Exit
If feld(px, py) <> 0 Then sicht = False
sichtfeld(px, py) = sicht
Next

w = w + wsteps
Until w > 359 Or wsteps = 0



Cls

;Feld malen
For x = 0 To xr - 1
For y = 0 To yr - 1
If feld(x, y) = 1 Then
Color 200, 150, 100
Rect x * g + 1, y * g + 1, g - 2, g - 2, 1
EndIf
Color 255, 255, 255
Rect x * g, y * g, g, g, 0

If sichtfeld(x, y) = False Then
Color 100, 100, 100
Rect x * g + 3, y * g + 3, g - 6, g - 6, 1
EndIf
Next
Next

Color 100, 150, 200
Oval posx * g + 1, posy * g + 1, g - 2, g - 2, 1

Color 0, 255, 0
Text 0, yr * g, "Genauigkeit: " + wsteps

Flip()



Until KeyDown(1)
End


Dein Ansatz ist aber der bessere. Die Mauer nicht Feldweise zu betrachten, sondern start und endpunkt von einer Mauer zu Finden...


EDIT
Wenn es nur um die Darstellung geht, und du B3D hast, so gabs hier schon gute Alternativen:
https://www.blitzforum.de/foru...t=schatten
https://www.blitzforum.de/foru...t=schatten
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
 

Krischan

BeitragMi, Okt 14, 2009 13:03
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn Du die Anzahl der zu prüfenden Felder minimieren willst kannst Du auch einen Quadtree verwenden:

http://bond357.free.fr/main/fo....php?id=10
 

Xar

BeitragMi, Okt 14, 2009 13:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Ah, ich weiss jetzt wie ichs mach!!! Eigentlich ganz einfach. Mir fehlt nur noch ein kleines Stück. Das könntet ihr mir aber erklären, indem ich jetzt eine ganz anderes Beispiel bringe.

Ich habe zwei Punkte (Pixel) auf dem Bildschirm, deren Koordinaten ich kenne. Sagen wir:

Pixel1= p1x,p1y
Pixel2= p2x,p2y

So. Nun will ich eine Verbindungslinie zeichnen. Und zwar nicht mit dem DrawLine Befehl (denn es geht ja eigentlich um was ganz anderes) sondern mit Plot. Ich möchte also diese Linie mit einzelnen Punkten zeichnen. Folgende Werte sind auch bekannt bzw. weiss ich wie berechnen:

L = Länge der Verbindungslinie in Pixel (es lebe der Satz des Pythagoras)
W = Winkel

das gäbe dann vermutlich mal eine FOR Schlaufe für jeden Pixel der Verbindungslinien-Länge:

For i = 1 to L
Next

dazwischen muss ich jetzt nur noch für jeden Pixel den x,y Wert haben.

Thorsten

BeitragMi, Okt 14, 2009 13:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Sin und Cos sind deine Freunde Smile
Oder du berechnest die Steigung aus dem Winkel. Das geht mit Tan soweit ich weiss.

Noobody

BeitragMi, Okt 14, 2009 16:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Just vor vier Tagen bastelte ich genau so eine Routine in BMax Razz

Und zwar geht der Algorithmus dazu jedes Feld der Map durch und zieht eine Linie von Spielerposition zu diesem Feld. Und zwar benutze ich dafür nicht, wie hier oft vorgeschlagen, Winkelfunktionen, sondern den guten alten Bresenham Algorithmus; dieser geht absolut zuverlässig und rechenschonend jedes Feld zwischen zwei Punkten durch. Statt aber an jedem Feld einen Pixel zu zeichnen, prüft der Algorithmus einfach, ob dort ein die Sicht blockierendes Feld liegt.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

Xar

BeitragMi, Okt 14, 2009 20:38
Antworten mit Zitat
Benutzer-Profile anzeigen
Juhu, ich habs geschafft !! Und das ganz ohne Sinus/Cosinus oder Tangens. Oh Mann, manchmal ist die Lösung so einfach, man denkt einfach zu weit -.-

wie oben erwähnt bestimme ich den Mittelpunkt (Pixel) des roten Feldes in der Mitte, sowie den Mittelpunkt des auf die Sichtbarkeit zu prüfenden Feldes.

Nun kann ich ja Problemlos anhand das X-Abstandes (b) und des Y-Abstandes (a) den effektiven Abstand zwischen den beiden Pixeln berechnen:

c = SQR(a*a+b*b)

user posted image

Und nun die Schleife: FOR i = 1 to c

Als StartKoordinaten nehme ich den Mittelpunkt des roten Quadrats. Von diesen Koordinaten aus kann ich problemlos die Feld-Kennung berechnen, welche in einem Array abgelegt ist und anhand dessen Werts ich ja weiss, handelt es sich um ein Hindernis oder nicht. Dieses Array ist übrigens 200x200 Felder gross, die besagten 15x15 Felder sind nur der aktuell sichtabre Ausschnitt, und ich benutze deren Werte um die Landschaft aufzubauen.

Dann verschiebe ich die Koordinaten jedesmal um b/c bei der X-Koordinate und um a/c bei der Y-Koordinate. Und so lasse ich die Schleife laufen. Sollte ich bei einer Prüfung auf ein Hindernis stossen, setze ich eine Variable auf 1. Wenn alles durch ist, setze ich das eben geprüfte Feld nur, wenn diese Variable eben nicht 1 ist.

Funktioniert einwandfrei Very Happy Freude herrscht!

ich habe vor 5 Tagen mit BlitzBasic angefangen, bin also noch ziemlich laienhaft unterwegs, aber das ist jetzt mein erster grosser Erfolg für mich! danke euch vielmals für die tollen und vor allem schnellen Antworten.

Weitere Fragen folgen sicher bald *g*
 

Xar

BeitragDo, Okt 15, 2009 7:03
Antworten mit Zitat
Benutzer-Profile anzeigen
Noobody hat Folgendes geschrieben:
Just vor vier Tagen bastelte ich genau so eine Routine in BMax Razz

Und zwar geht der Algorithmus dazu jedes Feld der Map durch und zieht eine Linie von Spielerposition zu diesem Feld. Und zwar benutze ich dafür nicht, wie hier oft vorgeschlagen, Winkelfunktionen, sondern den guten alten Bresenham Algorithmus; dieser geht absolut zuverlässig und rechenschonend jedes Feld zwischen zwei Punkten durch. Statt aber an jedem Feld einen Pixel zu zeichnen, prüft der Algorithmus einfach, ob dort ein die Sicht blockierendes Feld liegt.


Ich glaube, ich habs jetzt so ziemlich ähnlich gelöst Wink

SpionAtom

BeitragDo, Okt 15, 2009 11:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Noch ein Hinweis, Xar, Doppelposts werden nicht gerne gesehen. Benutze hierfür den "Beitrag bearbeiten" Button (Der mit dem Schraubenschlüssel) bei deinem Post.
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
 

Xar

BeitragMo, Okt 19, 2009 8:29
Antworten mit Zitat
Benutzer-Profile anzeigen
@SpionAtom:

Doppelposts? uff, sorry, das wollt ich nicht. Aber das ist mir jetzt auch nicht bewusst gewesen. Ich sehe nirgends einen Doppelpost, sehe alles nur 1 mal so wie es sein sollte. Wo habe ich denn sowas gemacht?

Nachtrag:
Aso, jetzt versteh ich was du meinst, meinen Nachtrag zum einen Post. Alles klar, werde ich ab sofort berücksichtigen. Danke dir für den Hinweis!!

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group