This is of course not an exact ranking, since the same game can have many (nearly identical) releases, but it roughly matches my experience
In practice graph matching can be helped by manually tagging the same nodes (labels in Ren'Py) in the two versions, but that cannot cover all the edge cases
I'm developing a VN framework for the own use of my indie VN dev group, and we mostly implemented the diff algorithm for the 'linear' part of the graphs. You can search my handle to know more
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.
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
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.
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)?
As far as competitors go, the list is not very long. Sugarcube/Twine works ok, but tends to bog down as the projects grow large because it doesn't have a good way of breaking up the core logic across different files. The save system is also a bit of a problem since the in-browser saves tend to get lost in version updates. QSP is just a buggy confusing mess every time. People try to shoehorn RPGMaker into doing the job but it is just so clunky and slow. Custom engines, typically built in Unity, are almost always massive resource hogs and lacking in one or more of the basic features Ren'Py provides by default. Plus there is just the community aspect of it, with Ren'Py having so many developers there is a lot of institutional knowledge to be had. If you run into a problem you are probably not the first, someone else has probably solved it already.