Hier isser, der berühmt-berüchtigte Bresenham-Algorithmus, mit dem man Line-of-Sight in einer Tile-based Umgebung berechnen kann (nützlich für Roguelikes, RPGs und Adventures) ...
Der eigentliche Code ist vom entsprechenden Wikipedia-Eintrag, ich habe ihn in PureBasic übersetzt und in eine funktionierende Umgebung eingebettet (das Original-Snippet hat nur eine einzige Linie von einem Startpunkt zu einem Endpunkt berechnet):
Funktionsweise:
Die World-Daten (Freie Felder/Mauern/Bäume, etc.) werden in eine binäre Map übersetzt, welche nur aus 0en und 1en besteht, also nur Informationen enthält ob ein Feld frei ist oder theoretisch in der Lage ist, Sichtlinie zu blocken. Diese binäre Map wird mittels der LOS-Variable (maximale Sichtweite vom Spieler = Rechteck um Spieler-Charakter herum) in der eigentlichen Bresenham-Prozedur verarbeit; Output ist eine sogenannte "bresenMap()", welche ebenfalls nur aus 0en und 1en besteht, und somit alle notwendigen Informationen liefert, welche Tiles vom Spieler aus sichtbar sind, und welche durch Hinternisse verdeckt werden.
Anschließend wird die Welt mit diesen neuen Ergebnissen gezeichnet:
Code: Alles auswählen
Global xMax = 30
Global yMax = 30
Global Dim worldMap.s(xMax,yMax)
Global Dim line$(yMax)
Global Dim binaryMap(xMax,yMax)
Global Dim bresenMap(xMax,yMax)
Global startX = 17
Global startY = 18
Global lineOfSight = 10
Restore world_data
For y = 1 To yMax
For x = 1 To xMax
Read.s worldMap(x,y)
Next
Next
Procedure buildWorld()
Define tile$
For y = 1 To yMax
line$(y) = ""
For x = 1 To xMax
tile$ = worldMap(x,y)
If x = startX And y = startY
tile$ = "@"
EndIf
line$(y) = line$(y) + tile$
Next
Next
EndProcedure
Procedure drawWorld()
ClearConsole()
For y = 1 To yMax
PrintN(line$(y))
Next
EndProcedure
Procedure translateWorld()
Dim binaryMap(xMax,yMax)
For y = 1 To yMax
For x = 1 To xMax
Select worldMap(x,y)
Case "." : binaryMap(x,y) = 1 ;Freies Feld
Case "#" : binaryMap(x,y) = 0 ;Mauer
EndSelect
Next
Next
EndProcedure
Procedure getBresenmap(x,y,xT,yT)
Define dX,dY ;Pixel
Define dXabs,dYabs ;Absolut-Distanzen
Define dXsgn,dYsgn ;Signum-Distanzen
Define pdX,pdY ;Parallel-Schritt
Define ddX,ddY ;Diagonal-Schritt
Define eFast,eSlow ;Fehlerschritte, schnell, langsam
Define error
dX = xT - x ;Target-Koordinaten
dY = yT - y
dXabs = Abs(dX)
dYabs = Abs(dY)
dXsgn = Sign(dX)
dYsgn = Sign(dY)
If dXabs > dYabs ; x = schnelle Richtung
pdX = dXsgn
pdY = 0
ddX = dXsgn
ddY = dYsgn
eFast = dYabs
eSlow = dXabs
Else
pdX = 0
pdY = dYsgn
ddX = dXsgn
ddY = dYsgn
eFast = dXabs
eSlow = dYabs
EndIf
error = eSlow/2
For i = 1 To eSlow
error = error - eFast
If error < 0
error = error + eSlow
x = x + ddX
y = y + ddY
Else
x = x + pdX
y = y + pdY
EndIf
bresenMap(x,y) = 1 ;Letztes Feld vor Abbruch der Funktion noch auf 1 setzen,
;da sonst blockende Mauern nicht angezeigt werden
If binaryMap(x,y) = 0
ProcedureReturn
EndIf
Next
EndProcedure
Procedure calculateLOS()
Dim bresenMap(xMax,yMax)
;lineOfSight = maximale Sichtweite in jeder orthogonalen Achse vom Spieler aus
;kann (und sollte) optimiert werden mit einem limitCheck, damit es keinen
;"Array Index -out of Bounds"-Fehler gibt, falls Distanz > Spielfeld
For y = startY-lineOfSight To startY+lineOfSight
For x = startX-lineOfSight To startX+lineOfSight
getBresenmap(startX,startY,x,y)
Next
Next
For y = 1 To yMax
For x = 1 To xMax
If bresenMap(x,y) = 0
worldMap(x,y) = " "
EndIf
Next
Next
EndProcedure
OpenConsole()
buildWorld()
drawWorld()
PrintN("Press ENTER") : Input()
translateWorld()
calculateLOS()
buildWorld()
drawWorld()
PrintN("Press ENTER") : Input()
End
DataSection
world_data:
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".","#","#","#",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".","#","#","#","#","#","#","#",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".","#",".","#","#","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".","#",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".","#",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".","#","#","#",".",".",".","#","#","#","#","#","#",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".","#",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","#","#","#","#","#",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
Data.s ".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."
EndDataSection