If you take the graph of the game, you basically have a DFA (deterministic finite automaton), so the problem is purely a reachability one which is trivial. In renPy, you have arbitrary variables that can be used to define the possible transitions. So reachability becomes a problem depending on the automaton state X persistent variables. Unfortunately, that means that now reachability is now Turing-complete, since you need to analyze the code that interacts with all variables. So say you have a transition tau from state Si to Sj, you need to make sure the labels contain any persistent variable that is used to trigger tau.

You can make sure to be forward compatible by (1) never removing states, and (2) making sure that any state x (value of persistent variables) has a transition.

Of course, that condition (2) is often violated by assuming that if you are in state Si, you must have gone through state Sk which sets a given variable to x, and fail to realize that there is another path to Si that does not go through Sk and you are stuck. If you add new states or new variables to your game, you are effectively creating this situation for all states. Reachability is a trivial problem, but checking the values all variables can take is kind of famously Turing-complete. So if you want to be able to do that, you need your use of variables so that basically you could eliminate them by replacing them by having more states.

Btw, the problem you mention is a notoriously painful one (https://en.wikipedia.org/wiki/Graph_isomorphism_problem), but with VNs you have labels so I think the issue is not to produce a diff but make it useful enough to check all game conditions.

Let me know if something is unclear.

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

For example, if the script loops through a node (and there is a choice to go out of the loop), and the node moves a character on screen to the left by 5 pixels each time, then there can be different game states with the same node. It happens in a common trope of VNs when the story lets you explore different places and go back to the original place each time

In the design of our VN framework, the game state is determined not by the current node, but by the node history (and other things like 'global variables'). If the author changes some script in the new version, then all saved data with the affected node history need to get updated

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

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

Hey, thanks for the context in this thread; I've been working on a project in I7 because I love the form factor of parser &choice-based IF. I'm looking to release the project like a webcomic, with monthly/quarterly chapters, but the backwards compatibility issue in I7 has been a blocker.

In your indie VN dev group, are there any devs working on cross-platform, parser & choice-based VNs (ie I can read a work on mobile as choice-based, but if I want to continue that same save on my computer/ enter commands, I can do that)?

We use Unity so it's cross-platform, including mobile. But we never implemented a server for cloud saves, so you need to sync the saves using other tools

I think you can accommodate most changes by storing ordered list of IDs of visited nodes as well as variables set by choices. This way if you'll delete or replace some nodes or branches you can walk back to still existing parts.