I am trying to develop a pathfinding algorithm that finds the closest path to a point by tracing a line from the initial position to the final position. Then I test for intersections with obstacles ( all of them in my game are rectangular ) and then draw two new lines, one to each of the visible corners of the obstacle. Then, I draw lines from those two corners to the endpoint and repeat the intersection test for each branch of the path.
My question is this: how do I propagate my branching paths in Lua without recursion? It seems like it would be pretty easy with recursion, but I don't want to risk a stack overflow and a crash if my path gets too long.
If there is a technical term for the technique I am using, please tell me. I like to do my own research when I can.
There is recursion and iteration. Lua supports "infinite recursion" via tail calls, so if you can express your recursion in terms of tail calls there is no risk of stack overflow. Example:
function f(x)
if x==0 then return 0 end -- end recursion
.... Do stuff ...
return f(x-1)
end
Section 6.3 of Programming in Lua (available online) discusses this.
If you can't determine a way to do this with tail calls then you have to use iteration. For example start with one path, using a while loop test how many intersections (exit loop when 0); the loop calls a function that computes two new paths; each path is added to a list; the while loop is in a paths loop (since the # of paths increases); the path length can be computed simultaneously; some paths will be dead end and will be dropped; some will be cyclical and should be dropped; and the rest will arrive at destination. You then keep the one with shortest path or travel time (not necessarily the same).