>The script graph can be thought as a DFA, but a 'game state' (images showing on screen, music playing...) is different from a node of the script graph, and the

>The script graph can be thought as a DFA, but a 'game state' (images showing on screen, music playing...) is different from a node of the script graph, and there is not a one-to-one mapping between them Sure. I would say it's a pretty bad idea though, and for instance in JOBifAI we manually managed savepoints in these case to stay isomorphic to a DFA anyway, because it's already hard enough to manage when the game has a big scope. >If there is no choice added/deleted, then the update can be implemented by simply re-running the nodes. However, if there are choices added/deleted, the update can be more complicated and involve graph isomorphism in the worst case Well. what you call 'global variables' is what I called 'persistent variables' above (using renPy's terminology). If you consider that they can get any value, your problem can be reduced to the halting problem. There are 2 ways you can get around that: - any use of these variables in conditional transitions segments the domain into a finite number of subdomains (in that case it's just a proxy for a long expansion into a much bigger DFA) - the variables belong to an infinite domain but are not involved into any state transition (for example, setting your name is not restricted but does not change any state transition) Since the halting problem isn't solvable, if you use these two solutions you don't need to solve the graph isomorphism problem. If you delete a node Si and your history contained Ss => Si => Se, you just need to find a path from Ss ==> Se. If you take the first in lexicographic order you even have a canonical solution.