Godot Version
4.6
Question
Good afternoon! I’ve been trying to implement recursive shadowcasting for line of sight in my game and its been taking an embarrassingly long amount of time 
func recursive_shadowcasting(start : Vector2i):
for i in range(rows):
for j in range(columns):
if Vector2i(i,j) != start:board[i][j].blocked = true
for i in range(8):
recursive(i, -1,1,1, start,ret)
func transform(octant:int, c:Vector2):
match octant:
0: return Vector2(-c.x, c.y)
1: return Vector2(c.y, -c.x)
2: return Vector2( c.y, c.x)
3: return Vector2( c.x, c.y)
4: return Vector2( c.x, -c.y)
5: return Vector2(-c.y, c.x)
6: return Vector2(-c.y, -c.x)
7: return Vector2(-c.x, -c.y)
##you must assume that a spot has a center at (.5,.5) and that (0,0) represents
##the topleft corner
func recursive(octant : int, start_slope : float,end_slope : float,depth : int,start_position : Vector2i, array = []):
var start = start_position+get_octant(octant)*depth
var end = start_position+get_octant((octant+1)%8)*depth
var dir = (end-start).sign()
var curr = start
if !get_tile(start) and !get_tile(end):
return
var first = true
var curr_as_tile : Spot
var prev_as_tile : Spot
while curr != end:
curr_as_tile = get_tile(curr)
##standardize so that curr-start_position is always the positive distance
##between the two
var local = transform(octant, curr-start_position)
##the top left
var l_slope = float(local.y)/ float(local.x)
##the bottom right
var r_slope = float(local.y+1)/ float(local.x+1)
if curr_as_tile:
if l_slope >= start_slope and r_slope <= end_slope:
if !curr_as_tile.blocker():
curr_as_tile.blocked = false
if !first:
if !prev_as_tile.blocker() and curr_as_tile.blocker():
recursive(octant,start_slope,l_slope, depth+1, start_position)
elif prev_as_tile.blocker() and !curr_as_tile.blocker():
var l = transform(octant, get_coordinates_by_tile(prev_as_tile)-start_position)
##new start is the previous ones bottom right
start_slope = float(l.y+1)/ float(l.x+1)
else:
first = false
else:
curr_as_tile.disabled=true
prev_as_tile = curr_as_tile
curr+=dir
##if the last one at this depth is a blocker,
##that means we sent a new recursive call.
##let that handle further action instead,
##since it has the updated end slope
if (prev_as_tile and !prev_as_tile.blocker()):
recursive(octant,start_slope,end_slope, depth+1, start_position,array)
the issues I’m facing almost certainly have to do with how I’m calculating slopes, or the transform() being wrong (however on a blank field it seems to hit all of the spots in each octant just fine..). Here are the results for the 2 main cases of the algorithm:
I know this is a pretty niche topic, but any help would be greatly appreciated! Thank you.
