That's related, but not the same. The dependency chart isn't showing the set of all possible player actions (though it can grow to that). And then, unless it's implemented formally, as described in the article it's a design tool, and not a formal tool. So you could leave out things (unintentionally).
For instance, if you don't model that the player can drop an object after finding it, you can't guarantee that they'll have it when they need it. So, using the original post's game, Alice needs the red key to get to the red room (final goal). Let's say it was in the west room, also with the green key, where Alice begins the game. She grabs the green key, goes east, hands it to Bob who heads west. Now Alice cannot move. This particular game is solvable because Bob can grab the red key and take it to Alice, but not every game permits this recovery action. Supposing it only had the one player character, and the keys were consumable (as happens in some games). She has no way to return.
The dependency chart only shows that she can solve the puzzle, not that she can always solve the puzzle (that there exists a path, not for all paths), until it gets a lot more detail than a hand-drawn graph is likely to get.
This is an excellent thing to think about when designing dungeons or encounters in any game really. I feel the need to call out Mark Brown, who's doing an excellent analysis series on the Legend of Zelda series, breaking down the dependencies in the dungeons throughout that game and walking through some of the issues present within.
One of the more notorious dungeons in the series is the Water Temple in Ocarina of Time, which contained a sequence that would allow the player to use a small key for an optional area that, critically, did not refund the small key. This allowed the player to become permanently stuck, unable to advance through the dungeon and complete the game.
I tried to find more information on this and the best thing I could find was this blog post claiming that you can't get permanently stuck in the Water Temple (at least, by using keys in the wrong order).
It looks like the dungeon is set up with a few carefully designed chokepoints using the water level mechanics to stop players from going too far down the wrong path:
Unfortunately, the author also claims there is an alternate way to ruin your game in the water temple that they'll cover in a follow-up article, but that article doesn't exist.
> For instance, if you don't model that the player can drop an object after finding it, you can't guarantee that they'll have it when they need it
This was a problem in the original Monkey Island: you could throw some leaflets in a fire, but you needed them in order to convince a local tribe to give you a key.
I found this incredibly interesting. I need to play with CBMC [1] sometime. I've always been fascinated by the idea of perfect programs, because so much of my time is spent tracking down bugs. And because so much of my PII and finances depend on software that is decidedly not perfect.
I would like to know more about how this works:
> The formal verification tool effectively runs this function with all possible seed values and checks if the assert() is violated in any of the cases. But it uses a more much efficient method to accomplish this than running the function
2^32 (approximately 4 billion) times.
Or are the "prove_" functions some sort of DSL that don't actually get executed as ordinary C code?
cbmc doesn't execute C(++) programs, but rather it turns them into instances of the SAT problem, which it then passes off to a SAT prover to (hopefully) prove it. It's assert() (and assume() and nondet_xxx() which are not mentioned in the article) that have special powers in cbmc, but functions name prove_xxx() aren't special as far as I'm aware.
What was the point of publishing this information in such a non-functional format? Is this an example of minimalism taken too far (not even an anchor tag for the twitter link) or is this some publishing standard I'm not aware of?
I feel like the document could have benefited a great deal from some simple font color styling. I guess in its current format it can easily be copy-pasted somewhere else and still look exactly as it does?
>What was the point of publishing this information in such a non-functional format?
Apart from the links not working, that's as functional as it gets for conveying text-based information. All the rest is fluff and the bytes to information ratio gets very bad, very fast (e.g. several MB to read a 1000 word CNN.com article).
Although the question make me fell a little old. How young are you buddy, for this is a plain old textfile -- used to be a very very common way to convey information. Last generation's GitHub readme.md files so to speak.
I certainly agree that auto-play videos and analytics JS takes it too far. But a little CSS to improve readability of code, some markup that allows links to be clickable, etc, seems reasonable to me at no performance cost.
25, so I grew up reading most of my content on wikipedia or forum posts, which is about the level of markup I mean (minus the ridiculously huge banner signatures that people were so fond of on invision forums ;) )
I'm an old geezer who grew up with text terminals and I agree with you wholeheartedly. Saving a scarce resource (mental real estate) to save a near free resource (bandwidth / processor cycles) is poor tradeoff.
I just went to time.com and picked a random article. Without javascript turned on, I get the date it was published, the word "search" in the top right, a few drop shadow boxes, a black square, a hamburger menu icon and nothing else.
/That's/ a non-functional format. Given the choice of everyone being time.com or everyone being like this website, I'd happily return to the days of amazing ascii art.
The things I think would improve the functionality of the OP article would require no JS whatsoever, just a CSS file and HTML tags. Really, just HTML tags at minimum. I wasn't suggesting including a JS file.
Yep, I'd totally agree with that, I'm a big fan of HTML-only websites. As a rule of thumb when writing websites (web apps are a different matter), I'd say if your CSS or Javascript is too big to hand-write, you've probably gone too far.
It's a shame mobile browsers are so dysfunctional that they struggle to cope with plain text or minimally marked up HTML, but the blame lies with the browsers, not the content.
Not really arguing anything. Just curious if there was a specific reason to do this over maybe throwing together a basic HTML page before submitting to a news aggregator.
I'm not making a judgement call, I'm trying to learn.
> Just curious if there was a specific reason to do this over maybe throwing together a basic HTML page before submitting to a news aggregator.
Articles or links can be submitted by anyone not necessarily content authors.
Further I think a lot of people here (myself) included are quite happy with plain-text (it loads fast, it works well with various font/screen sizes) - note also that the README is in fact markdown formatted, so feel free to open it in your reader of choice.
The 40col text might be "retro", but it also makes lines wrap so soon that my eyes get tired reading it. (And yet—unlike e.g. an RFC file—I can't just plop it into a Markdown parser or what-have-you to get reflowable lines of HTML out, because 1. it's not really in any particular format, and 2. the alternating "prose text", "formatted console interaction", and "formatted ASM listing with long prose comments beside them" sections aren't demarcated or delimited in any particular way.)
When your text becomes sufficiently "simple", it can actually become an accessibility problem.
Yep. Preface: I'm a cranky minimalist who would generally prefer reading plain-text-that-happens-to-be-markdown at a 78 col wrap (syntax highlighting tends to give me a headache, and I'm happy to copy-paste URLs as the price for having a document that's lightweight and comfortable to read).
Actual point: Dear gods that 4am crack is awful to read, and I'd actually prefer github angry fruit salad in spite of mostly hating the latter.
So, yeah, there are virtues to simplification, but it can still be overdone - and while the article we're commenting on was great to me, it probably overdid it slightly - and the link you provide is an unintentional reductio ad absurdum of the approach.
(long comment written because I expected to disagree with you until I clicked and went aaaaaaaaaaaaaaaaaa)
Plain text documents don't solve the problem he's talking about, but they at least mitigate it somewhat -- WYSIWYG is preferable to a changing pseudo-standard mangling an author's intent, in my opinion.
Yeah, I don't mind it at all, besided being very far over against the left margin. I think I would find it more jarring if the paragraphs were wider, and then it suddenly shrunk back down just for the code listings.
But then again, I may be a bit warped: a while back, while stuck in bed sick for a week, I implemented chacha20 in 6502 assembler, on an Apple II emulator, on my phone.
Vehemently opposed to your other suggestions. But I'm weird and cranky, and very much miss the days of most of computing being done in plain text. It's really the first and only universal data format/API.
The place to make plaintext pretty (if you care) is in the user's editor of choice where they can customize to their hearts content.
I do know I'm in the very tiny minority with this opinion though.
Several of the early (classic) Infocom games were meant for younger players - Seastalker, Wishbringer, and Moonmist if I recall correctly.
I played these, and also Zork, Enchanter, and so forth, around that age, with my father doing most of the typing, and loved them. As I got older we moved into more (read: extremely) challenging titles like Witness and Deadline.
There are also amusing choose your adventure type books where your goal is not thrilling action, but romance. For example, "Night of a Thousand Boyfriends" [1] from the "Date with Destiny Adventure" series.
Sometimes romance and adventure are combined, such as in "Escape from Fire Island!" [2], also from the "Date with Destiny" series.
Maybe not the best for young readers, though, as it is not aimed at younger readers:
It was supposed to be a nice, relaxing
weekend—with a little swimming, a lot of
cocktails, and more hot bods than a year’s
subscription to Men’s Health magazine. But when a
vat of radioactive waste washes onto the beach,
strange things start happening—and now an army of
zombie drag queens is storming the coast! Can you
save Fire Island before it’s too late? Or will you
perish at the hands of a thousand shrieking divas?
It all depends on the choices YOU make.
If you run toward the nearest ferry terminal, turn
to page 44. If you flirt with the cute twink, turn
to page 55. If you throw caution to the wind and
join the nearest circuit party, turn to page 80.
There are adventure/romance choose your path type books that are aimed at kids, though. I've got a couple from the '80s that combined a typical fairy tale type fantasy quest (slay the dragon, defeat the evil wizard, yadda yadda) and a search for a suitable boyfriend for your character who was typically a princess.
Depends on what you mean by "more complex". This uses cbmc, a formal model checker that runs relatively fast, and that doesn't require writing excessively complex formalisms to ask "is this state reachable". The README mentions a variation on this approach that scales to larger games.
Now, if you built a game isomorphic to a traveling salesman problem, or other exponential problem, then the model checker might have a problem with that. But so would a human; such a game would get extremely tedious. So, I'd venture as far as "this should scale to adventure games that humans enjoy playing".
Even embedded exponential problems can be fine, since existing solvers in the SAT/SMT/ASP/etc. family working on finite domains like these can usually heuristically solve them in reasonable time.
I did some work on formally modeling game mechanics in answer-set programming [1] for a prototyping system a few years ago [2], and in my case model size rather than complexity was almost always the bottleneck. And the biggest model-size culprit was just numerical stuff. If you have a game with a lot of numerical state variables (e.g. health of units), you get big explosions in the size of the state space, which even when the queries are trivial, end up taking the solver longer just to construct the space than solving complex problems in smaller state spaces does. By contrast very discrete-type games (that don't involve a lot of numerical status meters) worked great, even if they have a complex logical structure and you have complex questions to ask about their possibility space. However if you do have a numerically heavy game, SMT solvers can handle that too (the "modulo" part of satisfiability modulo theories can factor out things like the "theory of integers"). In my case I used ASP, specifically the Potassco suite [3], because imo the modeling language is friendlier, especially for incremental modeling, and I was more interested in investigating expressivity than scaling at the time.
It occurs to me that there should be some kind of strategy that allows for simplified computation of numerical state variables though? Since in a lot of cases the value being within a certain range is more important than it's exact amount (e.g. HP > max damage of a single blow, or of MP is >= spell cost). Intuitively I'd probably want to try some kind probability-density function to represent numerical stats.
You can even go with something like: Can the player cast >n spells. Or Is the players Average DPS > Boss's HP regen per second. Without having to care about the exact numbers.
> "this should scale to adventure games that humans enjoy playing"
I'm not sure that premise holds. Admittedly it's a different genre, but a lot of puzzle games are in exponential/NP-Hard/NP-Complete spaces. Tetris is an obvious example as a simple reduction of the packing problem. Humans very much enjoy playing those.
Even just restricting it to the genre of "adventure games", I'd be hesitant to say that there can't be games with very complex state spaces that humans enjoy playing. Maybe especially with "adventure games" where if the story and writing are interesting enough players will put up with a very wide variety of puzzles and exploration styles.
I don't think it's fair to associate "tediousness" with the computational complexity of the underlying problem. Some games are Turing complete (Factorio, Dwarf Fortress, Minecraft, Braid...)
This wouldn't work for open-ended sandboxes like Minecraft or Dwarf Fortress, and not just because you can build a Turing machine in those.
I'm talking about adventure-style games that have a defined solution and way to "win", and the complexity of computing that solution. In that regard, games that require a full backtracking search and aren't amenable to shortcuts tend to become tedious.
As an example, it's entirely possible to build an adventure game puzzle equivalent to an arbitrary SAT problem.
> So, I'd venture as far as "this should scale to adventure games that humans enjoy playing".
I'm really not sure about this one. Consider for example a savefile in an Angband-variant and whether a character can leave the dungeon alive (that's easy to define formally '@' on tile '>' with at 1 free turn seq and hp > 0), but I imagine the backtracking is going to be a very expensive computation...
In the past I've looked at some models of games. Most human playable adventure games have a fairly small state space, unless you do something cute like embed chess in it :)
The only tricky bit is you want to avoid modelling the exact pixel location of every object / player if at all possible, but need to make sure your simplifications don't end up hiding some unsolvable corners.
In a way it's necessary already for procedural generation, right? You can't have a level where the key to open a room is inside the room itself. So these nesting dependencies have to be carefully defined.
Not necessarily. I believe a lot of games simply use a set of heuristics to check for unwinnable situations after generating a scenario. These are usually based on unwinnable states that play testers have encountered, so there is no guarantee that they are exhaustive, and most procedurally generated games have a small chance to produce an unwinnable scenario.
No, there's a difference between "this scenario is solvable with perfect play" and "it is impossible for the player to make moves that make the game unsolvable".
I'd guess the complexity is dependent on the decision graph complexity: cyclic vs acyclic, entrance/exit points...
If it gets to conditional / puzzle evaluation that starts to get Turing Complete, then it will hit the halting problem, which I believe is thought to be noncomputable for nontrivial graphs / code.
They were huge in the late 80s/early 90s (at least, huge relative to the overall Internet population).
I imagine it's harder to find an active one now, but even a "dead" one that's still online should be somewhat playable. Just harder to learn and advance without other players.
I remember trying so hard when I was a little kid to learn english and move on in any textbased game. I always failed. So I guess it's still easy to have dead ends in textbased games ;)
Sort of. Sometimes it's deliberate, but they're really just another terminal state (different win/loss conditions, like you get 10 points for getting either character to their room, but 30 for both). Often, though, it's because puzzles and such aren't well considered so players are able to do things that prevent any further progress (unintentionally). This means the game won't terminate (or will take unreasonably long, like sitting for 40 turns for a timer to finish counting down).
In the example (simple) game in the post, a player character may be able to pass into the red room and "win", but perhaps there's no condition for returning and the game only terminates when both make it to their individual rooms. If the other character lacks the keys to move through the green and blue doors, then they will be stuck and the game won't terminate. This is easy to guard against in a small game (small state space, easy to manually or mentally compute), but in larger games it's almost trivially easy to cause these sorts of dead-end states. Consider the puzzles of Sokoban, where pushing a block onto certain walls or a corner prevent further progress and require a restart. Now, that's part of the game in that case, but perhaps a designer wants to prevent (in their puzzles) this sort of situation from occurring. This sort of analysis of the game model (states and actions) will help them prevent it.
Right, in text adventure games it is very easy to code a one-way door (e.g. "your brother Ralph has been kidnapped!") and a door which requires a key (e.g. "if you have the voodoo doll you can give it to Alice, who will then open the portal to the underworld"). If the one-way doors are dynamic (e.g. "if you tell the police the secret, then you piss off the mob boss: afterwards any attempt to go into the mob lair leads to death and restarting from the last save point") and you are not paying careful attention, then that key might easily be in an unreachable part of the game ("crap, if I wait too long to get Ralph back and, before that, I piss off the mob boss, then I can never get the voodoo doll from Ralph, and so Alice will never open the door to the underworld and now there's nothing left that I can really do").
It is especially important because of how frustrating the resulting loss is; it does not even have the dignity that you get from killing Vivec in Morrowind, where the game informs you "sorry, this game just became unwinnable." You just wander around after doing a bunch of actions that made sense at the time, not realizing that your brother Ralph was twisted up in some crazy voodoo plot. "Yes, Alice, I see that you have pains in your arm that you think come from some voodoo doll, I don't see how that has any relevance to anything though: I've searched this whole damn city and there are no voodoo dolls anywhere." Until later "Oh wait... there was that one alley on the other side of the mob lair, it looked empty at the time but what if that's where Ralph is now?"
And in a bit of irony versus the particular subexample within Morrowind, it turns out you can still win if you kill Vivec... might cost you more than you'd prefer though.
See http://ifwiki.org/index.php/Cruelty_scale . Not only do they have dead-ends, but sometimes you don't realize you've hit one until long after you do the thing that set you down the unwinnable path.
It depends. It's more likely in the older ~80's games done by poor game writers. The great companies like Infocom and the modern games done by those like Emily Short are excellent works of art.
Infocom games are full of dead ends. Best to save separate files often or you could find yourself missing an important item with nothing to do but start over (and it's often the case that you don't realize you're missing something until much later in the game.)
I have plenty of bad memories of being stuck on the Vogon ship with no way that I could figure out to get the Babel Fish. I hadn't realized that I needed the junk mail from the second room in the game.
If you have all the items with you and put them in place one at a time as you discover they're needed, the Babel Fish dispenser runs out of fish right on the attempt when you've finally got them all in place and are ready to collect it for real. Evil little game.
It gets worse -- there are a bunch of tools you go by throughout the game. If you fail to pick up any of them, that one will be the one you need to open one of the final doors.
In theory, I know the solution to every puzzle in the Hitchhiker's game. In practice, I've solved every one of them that you can solve while missing others (there's a gate right at the end of the game you have to have all of the items you can possibly get to get past)... but I have never strung all these solutions together into one winning game, despite several attempts.
It's a nasty little game, really.
I guess if I were doing it again nowadays I'd be going for a tool-assisted... umm... speedrun isn't really right here, so win-at-all-run.
There is a difference between always reaching a winning state or getting stuck without any resolution.
I think its important that there is no state were you just get stuck, you should at least have a game over sequence, so that you know you have done something wrong.
Andrew Plotkin (aka "Zarf"), Emily Short, Adam Cadre and many others are great and have written awesome pieces of work for modern IF that can rightfully claim to be art, but...
...classic Infocom games had plenty of dead-ends :)
Even the great modern authors have issues dealing with dead ends (both in trying to prevent them and finding surprise dead ends they didn't anticipate in their own games). Emily Short has many blog posts on the subject. Zarf put a lot of effort into the state-space solver/prover in his most recent game Hadean Lands. (There was some very interesting Kickstarter posts on that subject.)
I thought the rare occasions in monkey island games where you could 'die' it basically rewound to an acceptable state before that? (IIRC the second one even made a joke out of this with a falling off a cliff and bouncing back up thing)
The drowning ending is more of an easter egg than something you're likely to find in normal play. There's only one item you can interact with, so even if you can't think of the solution, it's easy to brute force it before the 10 minute timer runs out.
Some do by choice, as part of the gameplay and part of the feel of the world.
Some do by accident, for example if you can proceed to the next location in the game without an object you need to solve the challenge in it and without the ability to return to the previous one.
Well, they are not supposed to, yet... One of the most notorious among gamers when I was a teenager (okaaaaay maybe not strictly a 'text' adventure game) was Delphine Software's infamous 'Operation Stealth' where if you forgot to pick up an item say, at the beginning, you could not finish the game and you could not go back. You had to do precisely what the author describes at the beginning: call saved games or start over.
... no "dead ends". I.e. all player actions will result in a state in which the game is still winnable
- then, yes, fairly common, although not always intentionally.
I think the Hitchhikers Guide to the Galaxy text adventure game had a dead end very early in the game. If you didn't solve a non-obvious puzzle you'd be off in the weeds not getting anywhere interesting.
Dead ends were sierras idea of replayablity. You could often get stuck near the end of a game and have no idea when or where you missed something. LSL games were some of the worst.
Often they do. The general computer science topic is dead locks.
A dead lock occurs when a state is reached and there is no way to exit the state. In complex state machines it is important insure they are 'deadlock free.' Sometimes people use a timeout to recover from a locked state machine, sometimes the system needs to be re-powered.
An adventure game is simply a state machine (or a collection of interlocked state machines). So proving the proving the game has no deadlocks will also prove that the state machine has no deadlocks.
http://grumpygamer.com/puzzle_dependency_charts
I always think of finite state automata, but these adventure games with all the different inventory and actions can be remarkably hard to model.