0 votes
by (680 points)

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 >_<

1 Answer

0 votes
by (44.7k points)

Your code would be faster and avoid that problem if you did it in JavaScript.  However, at this point, the simplest solution is probably to just increase the Config.macros.maxLoopIterations setting to something much higher than the default 1000.  That Config setting is intended to help prevent coding newbies from accidentally locking up the browser, but it can interfere if you're doing something like what you're trying to do.

Hope that helps!  :-)

by (680 points)
I don't think that's the issue sadly... there's probably some bad code in there somewhere that's causing it.  I've increased the max loop iterations to 10000 already, and in fact, the code resolves itself in less than 3 seconds (you can copy my entire passage into a twine passage and test it for yourself). And I can actually get the desired result... which is weird.  BUT, I can't progress to another passage using the "next" button (and yes the passage that it links to does indeed exist in my twine game).   But it just wont work due to  "Maximum call stack size exceeded" error message that I mentioned.
by (44.7k points)
edited by

Question: Are you compiling this using Chapel's Tweego setup?  If so, it uses Babel, and Babel has a known bug that can cause that error.

If you're using that, look in the "src/config.json" file in the Tweego directory to disable using Babel. Turn off the "transpile" option in the "javascript" setting and hopefully it should work fine after that.

 

by (680 points)
Nope.  Not using it.  :(
...