[bb] Bresenham line tracing (2d) by Shagwana [ 1+ years ago ]

[BlitzBot]

Title : Bresenham line tracing (2d)
Author : Shagwana
Posted : 1+ years ago

Description : This is for manily use in 2d, Its a nice example of how the bresenham line can be processed outside of a closed loop . Possible uses include :- predicting the path of objects, Line-of-sight tracing, Collision prediction/detection between two or more objects or even just drawing lines like I have done here!. Code is provided as is, and maybe of use to someone!.  

Code :

Code (blitzbasic) Select Expand

;###################################################
;Stephen Greener (aka Shagwana) line trace engine
;Shagwana@sublimegames.com
;www.sublimegames.com
;###################################################
;[Inline] = best when made inline functions!
;This will trace every coord in the line apart from the starting coord
;Can be used to continue drawing line in the started direction!
;###################################################

;Used information in the algo
Type tBresenhemInfo
Field iX1,iY1,iX2,iY2 ;Coords of the line in question (from 1->2)
Field iX,iY ;Current location in the line!
Field iDeltaX,iDeltaY ;Distance to travel
Field iAbsDeltaX,iAbsDeltaY ;Postive version of the number above (for speed)
Field iIncX,iIncY ;What to increase by
Field iIncOne,iIncTwo
Field iBuffer ;Counting buffer
Field iXY ;Working buffer
Field iType ;What type of line this is (X over Y or Y over Z)
Field iStepsNeeded ;How many iterations this line will take
Field iCurrentStep ;Current stop out of the needed steps!
End Type

;Spawn a line to trace
Function SpawnTrace.tBresenhemInfo(iX1,iY1,iX2,iY2)
Local tTrace.tBresenhemInfo=New tBresenhemInfo
;Store the coords for the trace
tTraceiX1=iX1
tTraceiY1=iY1
tTraceiX2=iX2
tTraceiY2=iY2
;Current postion
tTraceiX=iX1
tTraceiY=iY1
;Calculate distance to travel (delta)
tTraceiDeltaX=iX1-iX2 ;Distance to travel
tTraceiDeltaY=iY1-iY2
tTraceiAbsDeltaX=Abs(tTraceiDeltaX) ;Postive versions
tTraceiAbsDeltaY=Abs(tTraceiDeltaY)
;Set direction of the add in bresenhem line algo
If tTraceiDeltaX<0
tTraceiIncX=1
Else
tTraceiIncX=-1
EndIf
If tTraceiDeltaY<0
tTraceiIncY=1
Else
tTraceiIncY=-1
EndIf
;Setup the start of the algo loop
If tTraceiAbsDeltaX>tTraceiAbsDeltaY
tTraceiType=0
tTraceiStepsNeeded=tTraceiAbsDeltaX
tTraceiIncOne=2*tTraceiAbsDeltaY
tTraceiIncTwo=2*(tTraceiAbsDeltaY-tTraceiAbsDeltaX)
tTraceiBuffer=tTraceiIncOne-tTraceiAbsDeltaX
tTraceiXY=iY1
Else
tTraceiType=1
tTraceiStepsNeeded=tTraceiAbsDeltaY
tTraceiIncOne=2*tTraceiAbsDeltaX
tTraceiIncTwo=2*(tTraceiAbsDeltaX-tTraceiAbsDeltaY)
tTraceiBuffer=tTraceiIncOne-tTraceiAbsDeltaY
tTraceiXY=iX1
EndIf
tTraceiCurrentStep=0
Return tTrace.tBresenhemInfo
End Function

;Returns the number of steps needed to complete the trace!
Function TraceStepsNeeded(tTrace.tBresenhemInfo) ;[Inline]
If tTrace.tBresenhemInfo<>Null
Return tTraceiStepsNeeded
EndIf
End Function

;Will trace one along the given line, calculates the next coord towards the end coords
Function ProcessTrace(tTrace.tBresenhemInfo) ;[Inline]
If tTrace.tBresenhemInfo<>Null
Local bDone=False
If tTraceiCurrentStep>=tTraceiStepsNeeded
bDone=True
EndIf
tTraceiCurrentStep=tTraceiCurrentStep+1
If tTraceiType=0
If tTraceiBuffer<0
tTraceiBuffer=tTraceiBuffer+tTraceiIncOne
Else
tTraceiBuffer=tTraceiBuffer+tTraceiIncTwo
tTraceiXY=tTraceiXY+tTraceiIncY
EndIf
tTraceiX=tTraceiX1+(tTraceiCurrentStep*tTraceiIncX)
tTraceiY=tTraceiXY
Else
If tTraceiBuffer<0
tTraceiBuffer=tTraceiBuffer+tTraceiIncOne
Else
tTraceiBuffer=tTraceiBuffer+tTraceiIncTwo
tTraceiXY=tTraceiXY+tTraceiIncX
EndIf
tTraceiX=tTraceiXY
tTraceiY=tTraceiY1+(tTraceiCurrentStep*tTraceiIncY)
EndIf
Return bDone
Else
Return True
EndIf
End Function


;Return the current location in the trace!
Function TraceXPos(tTrace.tBresenhemInfo) ;[Inline]
If tTrace.tBresenhemInfo<>Null
Return tTraceiX
EndIf
End Function
Function TraceYPos(tTrace.tBresenhemInfo) ;[Inline]
If tTrace.tBresenhemInfo<>Null
Return tTraceiY
EndIf
End Function

;Free used resources - can be used to stop a trace early :)
Function KillTrace(tTrace.tBresenhemInfo)
If tTrace.tBresenhemInfo<>Null
Delete tTrace.tBresenhemInfo
tTrace.tBresenhemInfo=Null
EndIf
End Function

;###################################################
;A example of using the functions above ...

Graphics 640,480,16,1
SetBuffer FrontBuffer()

SeedRnd(MilliSecs())

Const TraceAmount=50

Dim Traces.tBresenhemInfo(TraceAmount)
Dim TraceCounts(TraceAmount)
For N=0 To TraceAmount-1
Traces.tBresenhemInfo(N)=SpawnTrace(Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17,Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17)
TraceCounts(N)=TraceStepsNeeded(Traces.tBresenhemInfo(N))

Color 255,0,0 ;Big red rect at the start of a trace
Rect Traces(N)iX1-1,Traces(N)iY1-1,3,3,False
Rect Traces(N)iX1-2,Traces(N)iY1-2,5,5,False
Color 0,255,0 ;Big green rect at the end of the trace
Rect Traces(N)iX2-1,Traces(N)iY2-1,3,3,False

Next



;Just to slow down the drawing of the line
T=CreateTimer(30)

iLoop=0 ;Will count the steps in the line drawing also
Repeat

VWait ;Comment out to see the speed :-)
WaitTimer(T) ;Comment out to see the speed :-)
SetBuffer FrontBuffer()

bDone=True
For tTrace.tBresenhemInfo =  Each tBresenhemInfo
If ProcessTrace(tTrace.tBresenhemInfo)=False
bDone=False
Color 128,128,128
Plot tTraceiX,tTraceiY
Else
KillTrace(tTrace.tBresenhemInfo)
EndIf
Next

Color 0,0,0
Rect 0,0,GraphicsWidth(),16
Color 255,255,255
If bDone=True
Text 0,0,"Lines all drawn [biggest was "+iLoop+" steps]"
VWait
Else
iLoop=iLoop+1
Text 0,0,"Processing step ("+iLoop+")"
EndIf

Until KeyDown(1)
End

Comments : none...