search

klembot / twinejs

Twine, a tool for telling interactive, nonlinear stories
https://twinery.org
GNU General Public License v3.0
2k stars 295 forks source link

Advanced Passage Connectivity Testing #232

Open klembot opened 8 years ago

klembot commented 8 years ago

Originally reported by: LemonPi (Bitbucket: LemonPi, GitHub: LemonPi)

One feature that would be widely useful is telling the user what branches are reachable from a starting passage. By reachable I mean not just are there edges that can be traced back to the starting passage, but whether it's possible to have the values of state needed to use those edges to actually get there, since edges are usually conditional (e.g. a character must pass a variable test to be able to take a certain path).

What this would boil down to is the user can select any passage as the starting point, and initiate a DFS-like sort of search, where you recursively evaluate the code in every passage and then do the same for all passages that are linked into from there (as visible after evaluating the control structure). Recognizing loops (same passage and same state, note that if you end up in the same passage but with a different state that's not really a true loop) is easy by storing the hash of the state and "colorizing" each passage visited with the current state hash.

One challenge would be those infinite pseudo loops where the same passage is visited but with a slightly different state (which could change indefinitely, such as a money variable). A way to address this is to let users specify what set of variables constitute the state (each variable name is really a string that we can evaluate raw), and warn them to exclude those that could change indefinitely.

I would be willing to work on this, but I'm not sure where in the source I could start... (It also seems to be undergoing a major refactoring)

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

  1. Pressing the exploration button compiles the story and explores it inside an iframe, so the user doesn't have to do it as a separate step. I think compiling the story is linear in time (O(|V| + |E|) where |V| is #passages and |E| is #links), so it should scale all right to large stories.

  2. As you mentioned on the forums, keeping volatile story state outside of the story variables is a bad idea anyway (state restoration easily becomes out of sync), so more warning of that I think is necessary.

The prototype I posted doesn't have the user prompt for what they consider as state yet, so maybe that wasn't clear. What I plan is for the user to determine what they deem important enough to keep track of as state (a small subset of all state variables), which will limit them to choose from story variables only (actively discouraging them from using non-story variables to hold state).

The PRNG seed shouldn't be a problem since if randomness is a part of their story, then brute force exploration wouldn't find all the possible branches in one go anyway. Users will just be warned that if randomness is crucial to branching, exploring it multiple times may yield different results (exactly the same way that playing it would yield different results randomly).

klembot commented 8 years ago

Original comment by Thomas M. Edwards (Bitbucket: tmedwards, GitHub: tmedwards):

Some hurdles:

  1. Your current prototype, if resembling anything like what you posted to the Twinery forums, is going to require a compiled story to function.
  2. There may be story state which exists outside of the story variables. For example: If the seedable PRNG is enabled in SugarCube, it maintains state outside of the story variables.
klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

Ah I see, do you know when it might be stable enough to be worked off of? In particular the current code duplication is a bit concerning as I'm not sure which one I should be modifying (or all of them) to get enhanced behaviour.

klembot commented 8 years ago

Original comment by Chris Klimas (Bitbucket: klembot, GitHub: klembot):

The refactor branch is very much a WIP -- I'm keeping it public to try to cut down on potential merge conflicts on PRs.

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

I'm confused by the refactor2k15 branch. I previously modified models/storyFormat.js's publish function to add in an optional extra parameter. Inside the new branch, there seems to be 3 functions that are exact duplicates of each other - src/story-edit/view.js's publish, src/data/story-format.js's publish, and src/data/story-format/index.js's publish. Why is there so much duplication?

Also, the refactor branch is not currently buildable... All the passages gets pushed to the upper left corner and all the icons are squares.

I'll suspend any modifications until the refactor branch can be modified.

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

I'm thinking that the story formats can contribute a "navigator" component as part of the format.js file, providing the same function as the one I currently have for SugarCube. I haven't ironed out the interface yet, but it'd probably involve taking a userStateVar to initialize state variables and keep track of them, and eventually passing out an array of visited passage objects (which must have certain parameters such as parent passage and passage name). If the story format doesn't provide a "navigator", explore just won't do anything for it.

I am working on the trunk, will move to refactor2k15 and move changes over to inside a module. (where would you like that module? I'm thinking of an explore folder inside src/story-edit)

Documentation could be improved with a "How you can contribute" section in the README, where it would tell the candidate contributor where they can add features (so in this case it'd be a brief overview of the entire structure, what modules are, and how to create your own module, as that seems to be the ideal way to contribute)

klembot commented 8 years ago

Original comment by Chris Klimas (Bitbucket: klembot, GitHub: klembot):

This is a really interesting idea! I only play a computer scientist on TV, but this sounds similar to Turing's halting problem, which is to say: difficult! I'm curious to see your code. It would be nice if it were able to be agnostic about story format. The editor tries its best to do this in general, so that as story formats are developed in the future, they are first-class citizens.

If you're editing storyEditView.js, I think you are working off the trunk. That code in particular has seen heavy revision during my refactoring process (see the refactor2k15 branch), to separate it into more manageable pieces. It would be ideal if the code you're working on is its own module.

Finally -- sorry to hear the documentation was not very good. I've been working on that in particular on the refactor branch as well. Are there specific things I could do to improve things? I'm particularly interested in your point of view because you're a new contributor.

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

OK so some update - I got a fully working prototype with the help of my roommate. Another button's added to the toolbar that allows exploration of branches from that passage onwards. This is done by creating an iframe and then using the story format's specific passage and state navigation to do so (prototype implemented for SugarCube so far). The navigation code is injected into the iframe when it's created, and this code can be either supplied by the story format authors, or I can see how to get it working for the popular ones. Currently this code can be supplied as an external JSON file.

Once the navigation/DFS is complete, the iframe posts a message back, which is handled by a handleMessage function inside storyEditView.js. The message posted back consists of an array of passageNode objects, which contains their parent passage and the passage name of all reachable passages.

The only things that still have to be done is when they click the explore button on the hover toolbar, popup a modal asking users to input the names of variables that constitute the state (right now it's the passage name (a hidden state), and some hard coded variables for my test story), and to highlight the passages that are reachable, which I think can be done by iterating over the array and querying based on either passage name, or passage id (which I think is more directly in the DOM).

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

Yeah, that's what I gathered after looking at what the storyformats actually return to Twine... Just a large html. For starters, I would like to create a prototype that works with SugarCube 2.

klembot commented 8 years ago

Original comment by greyelf (Bitbucket: greyelf, GitHub: greyelf):

Because each of the different Story Formats have their own set of features related with passage traversal this functionality would need to either know about all the different ways and would need to be updated if a new method was added to a Story Format, or it would need to interact with a Story Format's engine which would require the Story Format Developers to implement said access. (eg A bit like how Twine 2's Test mode is meant to work.

klembot commented 8 years ago

Original comment by LemonPi (Bitbucket: LemonPi, GitHub: LemonPi):

I've successfully cloned and compiled the standalone version (slightly less trivial on windows). Are there any documentation on contributing to the source (grunt generated doc is useless)? For example, how can I evaluate the code in a passage and find visible outward links?

(I'm reading up Backbone's documentation)