-
Mar 30th, 2012, 12:33 PM
#1
Fast 2D Line of Site Algorithm
Currently in my Bosskillers game I am using this formula for detecting line of site between the player and the sprite:
vb Code:
Public Function Get_Line_of_Site(Map As Map_Type, X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As Boolean
Dim DX As Single: DX = Abs(X2 - X1)
Dim DY As Single: DY = Abs(Y2 - Y1)
Dim X As Long: X = Floor(X1)
Dim Y As Long: Y = Floor(Y1)
Dim DT_DX As Single
Dim DT_DY As Single
Dim T As Single: T = 0
Dim N As Long: N = 1
Dim X_Inc As Long, Y_Inc As Long
Dim Next_Horizontal As Single, Next_Vertical As Single
If DX <> 0 Then
DT_DX = 1 / DX
Else
DT_DX = 0
End If
If DY <> 0 Then
DT_DY = 1 / DY
Else
DT_DY = 0
End If
If DX = 0 Then
X_Inc = 0
Next_Horizontal = DT_DX '// infinity
ElseIf X2 > X1 Then
X_Inc = 1
N = N + (Floor(X2) - X)
Next_Horizontal = (Floor(X1) + 1 - X1) * DT_DX
Else
X_Inc = -1
N = N + (X - Floor(X2))
Next_Horizontal = (X1 - Floor(X1)) * DT_DX
End If
If DY = 0 Then
Y_Inc = 0
Next_Vertical = DT_DY ' // infinity
ElseIf Y2 > Y1 Then
Y_Inc = 1
N = N + (Floor(Y2) - Y)
Next_Vertical = (Floor(Y1) + 1 - Y1) * DT_DY
Else
Y_Inc = -1
N = N + (Y - Floor(Y2))
Next_Vertical = (Y1 - Floor(Y1)) * DT_DY
End If
For N = N To 0 Step -1
If Next_Vertical < Next_Horizontal Then
Y = Y + Y_Inc
T = Next_Vertical
Next_Vertical = Next_Vertical + DT_DY
Else
X = X + X_Inc
T = Next_Horizontal
Next_Horizontal = Next_Horizontal + DT_DX
End If
Dim New_X As Long, New_Y As Long
New_X = Int((X - Map.Position.X) / TILE_WIDTH)
New_Y = Int((Y - Map.Position.Y) / TILE_HEIGHT)
'Draw_Pixel X, Y, D3DColorXRGB(255, 255, 255)
If New_X <= 0 Then New_X = 0
If New_Y <= 0 Then New_Y = 0
If New_X >= UBound(Map.Collision_Map.Response, 1) Then New_X = UBound(Map.Collision_Map.Response, 1)
If New_Y >= UBound(Map.Collision_Map.Response, 2) Then New_Y = UBound(Map.Collision_Map.Response, 2)
If Map.Collision_Map.Response(New_X, New_Y) = COLLISION_WALL Then
Get_Line_of_Site = False
Exit Function
End If
Next N
Get_Line_of_Site = True
End Function
The problem with this is that each iteration is per pixel test. And it only fires off when either the sprite or player moves to another tile coordinate for speed purposes cause theres no sense testing line of site if they remain within the same tile coordinates. And its ok for 20-25 sprites to test on. But once you add more and more such as 100 sprites, it bogs the game down after every tile change. So what I was thinking was would it be wiser to do the test using tiles instead of pixels? Like lets say the distance between the sprite and the player is 1000 pixels away. Instead of doing the test using a 1000 pixels I could use just a few measly tiles. But even then, are there special scenarios where this per tile line of site test would fail or would this be a nice speed boost in my RPG? Is there a way I could test if the sprites within the same room so I dont need to check every single sprite to speed it up even more? Thanks in advance.
-
Mar 30th, 2012, 01:43 PM
#2
Re: Fast 2D Line of Site Algorithm
Not sure I follow entirely. I think logic kinda like the following may help
1. You can get a list of tiles that intersect line between player & sprite?
2. If so, any tiles in that list where there is not an obstacle placed upon it can be excluded from testing
3. For tiles where obstacles do exist, you can calculate the intersection of that line and the tile's edges
Another possibility? Not sure this will speed things up dramatically. In most cases, would you agree that, if a wall/obstacle is present, the player or sprite will probably be fairly close to it. If it is agreeable, then test from the player to the sprite about 1/4 of the distances along the line. If no obstacles, check from the sprite to the player about 1/2 the line. If still no obstacles, finish by testing from the player to the sprite starting 1/4 of the line to 1/2 the line
Edited: Example to try to better visualize the line-intersection idea. The player & sprite are yellow tiles. Walls are gray & open space is white. Line of sight (LOS) is the blue line
Build a quick routine that can return tile indexes that intersect LOS. A maximum of 4 lines (4 tile edges) per tile needs to be tested for LOS intersection. You can speed this up a bit too. Divide your field into quadrants. Each quadrant has 4 edges also. Test intersection of the quadrant first. If LOS segment doesn't intersect quadrant, then it won't intersect any tiles in that quadrant. If player & sprite are in same quadrant, then obviously the other 3 quadrants don't even need to be considered. Else tiles in at least 2 quadrants will need to be tested: the one containing the player & the one containing the sprite. Only if these are diagonal quadrants, then the remaining 2 quadrants should also be checked for line intersection to exclude them if possible (notice 2nd image: 3 quadrants in play). Obviously vertically adjacent quadrants exclude the remaining two. Same is true for horizontally adjacent quadrants. Depending on size of your field, you may want to break quadrants down, into sub-quadrants -- drill down approach.
And yet, it can be optimized a bit more. Depending on the angle from player to sprite, you may be able to narrow down whether 1 or 2 tile border edges need to be tested. You shouldn't ever need to test all 4 sides of a tile. At max only two sides of any tile will be in LOS between player & tile, or between sprite & tile. Ummm, angles not necessary after some further thought. If you take any tile and draw an imaginary line diagonally from corner to corner and again between the other corners (forming an X), if LOS intersects either diagonal line, then it intersects the tile. So, instead of needing to know which 2 borders face the LOS, just do line intersection tests on the 2 imaginary lines (X) instead.
If the entire tiles are obstacles then pretty much done, if you have any intersections. However, if a tile can contain mini-tiles which can contain both free space & obstacles, then you may have to test each pixel that intersects the gray tile to see if it collides with an obstacle's pixel. However, if the obstacles' borders, in the mini-tiles, are known, then again use line intersection on the obstacles' borders.
Bottom line, this logic is more of a line intersection loop vs. a pixel by pixel collision test. And thru process of elimination (via quadrants & sub-quadrants if desired) in addition to limiting tested tile borders to just 2 vs. 4, the tests should be very, very fast indeed.
Last edited by LaVolpe; Mar 30th, 2012 at 02:50 PM.
-
Mar 31st, 2012, 10:19 AM
#3
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|