I apologize if this is the wrong place to ask such a complex question, especially since it is more of an algorithmic optimization problem rather than an actual twine / sugarcube problem, but here goes:
Basically I'm trying to code a roguelike game in twine (using primarily sugarcube syntax no less), and I want to implement an A* pathfinding algorithm for enemies to find the player. While I was actually successful in getting the shortest path and storing it in a $path array, I ran into the issue of not being able to navigate to another passage, or even do anything else on the current page, and any attempts to do so were followed by a "Maximum call stack size exceeded" error message. I'm using the checkvars macro to debug, and clicking on checkvars results in the same error. The following code snippet is an exact copy of my actual twine passage (sorry if it's long and unoptimized):
<<set $map to [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, ],
[0, 4, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, ],
[0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, ],
[0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, ],
[0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, ],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, ],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 0, 1, 1, 0, 0, 0, ],
[0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, ],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, ],
[0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, ],
[0, 0, 1, 1, 0, 0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, ],
[0, 0, 3, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, ],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, ],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ],
]>>\
Starting point: $ map[13][2] So for an example, we will set $ monster position to this value. <<set $monster to {}>><<set $monster.x to 2>><<set $monster.y to 13>>
End point: $ map[2][1] So for an example we will set $ player position to this value. <<set $player to {}>><<set $player.x to 1>><<set $player.y to 2>>
A* algorithm: f(n) = g(n) + h(n)
Each "coordinate" point has an f value so that it can be evaluated.
g is the number of steps of the point from the starting point
h is the heuristic or the estimated distance of the point to the end point
<<set $openSet to []>>
<<set $closedSet to []>>
<<set $path_start to {x: $monster.x, y: $monster.y, f: 0, g: 0, h: 0}>>
<<set $path_goal to {x: $player.x, y: $player.y, f: 0, g: 0, h: 0}>>
<<set $openSet.push($path_start)>>
<<set $path to []>>
<<set $truePath to []>>
<<unset $path_start>>
<<silently>>
<<for _a to 0; $openSet.length > 0; _a++>>
<<set $winner to 0>>
<<for _i to 0; _i < $openSet.length; _i++>>
<<if $openSet[_i].f < $openSet[$winner].f>>
<<set $winner to _i>>
<</if>>
<</for>>
<<set $current to $openSet[$winner]>>
<<if $current.x === $path_goal.x && $current.y === $path_goal.y>>
<<set $temp to $current>>
<<for _k to 0; def $temp.prev; _k++>>
<<set $path.unshift([$temp.x, $temp.y])>>
<<set $temp to $temp.prev>>
<</for>>
<<unset $openSet>>
<<unset $closedSet>>
<<unset $temp>>
<<unset $current>>
<<set $step to "Completed">>
<<break>>
<<else>>
<<set $step to "Ongoing">>
<</if>>
// push the neighbours into the neighbours property array of current.
<<if ndef $current.neighbours>>
<<set $current.neighbours to []>>
<</if>>
<<if def $map[$current.y - 1]>>
<<if $map[$current.y - 1][$current.x] > 0>>
<<set $current.neighbours.push({x: $current.x, y: $current.y - 1, f:0, g:0, h:0})>>
<</if>>
<</if>>
<<if def $map[$current.y + 1]>>
<<if $map[$current.y + 1][$current.x] > 0>>
<<set $current.neighbours.push({x: $current.x, y: $current.y + 1, f:0, g:0, h:0})>>
<</if>>
<</if>>
<<if def $map[$current.y][$current.x - 1]>>
<<if $map[$current.y][$current.x - 1] > 0>>
<<set $current.neighbours.push({x: $current.x - 1, y: $current.y, f:0, g:0, h:0})>>
<</if>>
<</if>>
<<if def $map[$current.y][$current.x + 1]>>
<<if $map[$current.y][$current.x + 1] > 0>>
<<set $current.neighbours.push({x: $current.x + 1, y: $current.y, f:0, g:0, h:0})>>
<</if>>
<</if>>
// Only then do we push the current object into the closed set, and remove the current object from the open set.
<<set $closedSet.push($current)>>
<<for _b to $openSet.length - 1; _b >= 0; _b-->>
<<if $openSet[_b] == $current>>
<<set $openSet.splice(_b, 1)>>
<</if>>
<</for>>
<<for _j to 0; _j < $current.neighbours.length; _j++>>
<<set $neighbour to $current.neighbours[_j]>>
<<if !$closedSet.includes($neighbour)>>
<<set $tempG to $current.g + 1>>
<<if $openSet.includes($neighbour)>>
<<if $tempG < $neighbour.g>>
<<set $neighbour.g to $tempG>>
<</if>>
<<else>>
<<set $neighbour.g to $tempG>>
<<set $openSet.push($neighbour)>>
<</if>>
<<set $neighbour.h to Math.abs($neighbour.x - $path_goal.x) + Math.abs($neighbour.y - $path_goal.y)>>
<<set $neighbour.f to $neighbour.g + $neighbour.h>>
<<set $neighbour.prev to $current>>
<</if>>
<</for>>
<</for>>
<</silently>>
<<for _i to 0; _i < $path.length - 1; _i++>>
Step <<print _i>>: [<<print $path[_i][0]>>, <<print $path[_i][1]>>]
<</for>>
<<button "Next">><<goto "Next Page">><</button>>
I also noticed, in my feeble attempts to rectify the issue, that if i removed the following line of code from the above snippet, the problem gets resolved almost instantly:
<<set $neighbour.prev to $current>>
But of course, removing the above line of code prevents me from ever returning the optimized path... which is the whole point of this algorithm in the first place. So I'm inclined to believe that this is a limitation of the twine variable library store? Or is there a unoptimized bug in my code that I never noticed before? Please help >_<