Which squares does a line intersect
Monkey Forums/Monkey Programming/Which squares does a line intersect
| ||
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 :) |
| ||
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. |
| ||
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 |
| ||
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] |
| ||
this might help you: http://monkeycoder.co.nz/Community/posts.php?topic=2157#32984 |