Which squares does a line intersect

Monkey Forums/Monkey Programming/Which squares does a line intersect

Raz(Posted 2012) [#1]
I have a 2d array of blocks, they have a bool stating isObstacle:Bool.
I would like to be able to check if a line between two points over this 2d grid intersects with a block that is an obstacle.

Ideally I would like to check as few blocks as possible and I believe the image below indicates the blocks that would need checking.



Is there an elegant way of doing this if it's at all possible?

Ta :)


Gerry Quinn(Posted 2012) [#2]
Look up the Bresenham Algorithm for drawing lines. It gives the pixels a line will be drawn on. You can use the same method to test the intersections if you pretend your blocks are the pixels.


DruggedBunny(Posted 2012) [#3]
Exactly what I was going to say! This example should port with almost no changes -- the points where it draws are where your line hits a square:

http://www.blitzbasic.com/codearcs/codearcs.php?code=1465


Raz(Posted 2012) [#4]
Thanks you two :) Couldn't get on to the forum to say that the Bresenham Algorithm is exactly what I found in the end.

It's a bit crude, but this works for my code.

[monkeycode]

Function CheckLineOfSight:Bool(X1:Int, Y1:Int, X2:Int, Y2:Int)

Local CX:Float = X1
Local CY:Float = Y1

' Using 8 because it's half of the tile size
Local CStep:Float = 8
Local D:Float = DirectionBetweenPoints(X1, Y1, X2, Y2)

Local XStep:Float = Sin(D) * CStep
Local YStep:Float = Cos(D) * CStep


Local LastCheckedX:Int = - 1
Local lastCheckedY:Int = - 1

While DistanceBetweenPoints(CX, CY, X2, Y2) > CStep

Local TileX:Int = (CX - (CX Mod 16)) / 16
Local TileY:Int = (CY - (CY Mod 16)) / 16

' Only check if we've moved to a new tile
If TileX <> LastCheckedX Or TileY <> lastCheckedY

' Only check if we are in the level
If PointInRect(TileX, TileY, 0, 0, MapWidth * 2, MapHeight * 2)
If NMData[TileY][TileX].IsObstacle
Return False
EndIf
Else
Return False
End

LastCheckedX = TileX
lastCheckedY = TileY

EndIf

CX += XStep
CY += YStep

Wend

Return True


End
[/monkeycode]


NoOdle(Posted 2012) [#5]
this might help you: http://monkeycoder.co.nz/Community/posts.php?topic=2157#32984