8 ms·
Teeny Tiny Mansion: text adventure game formally proven to have no dead ends
- Retr0spectrum 10y agoIs this technique scalable to more complex games?
- devindotcom 10y agoIn 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.
- rcthompson 10y agoNot 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.
- jsnell 10y agoNo, 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".
- logfromblammo 10y agoPart 2 of Zork featured exactly that scenario. And you could render the room unreachable if you did things in the wrong sequence.
- CJefferson 10y agoIn 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.
- JoshTriplett 10y agoDepends 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".
- WorldMaker 10y ago> "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.
- lmm 10y ago> Tetris is an obvious example And is unwinnable.
- drdrey 10y agoI 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...)
- JoshTriplett 10y agoThis 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.
- cowardlydragon 10y agoI'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. https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- makapuf 10y agoYes but only if computed on fpga with open-source tooling. (thanks to Clifford for that also !) no this is not completely nonsensical...
- anodin3 10y agoI've never played any text adventure games, do they usually have dead ends?
- deleted 10y ago[deleted]
- throwaway7645 10y agoIt 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.
- Gracana 10y agoInfocom 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.)
- throwaway7645 10y agoYea I guess I should have specified that Infocom had them, but they weren't stupid mostly. They aren't as common in modern IF.
- LanceH 10y agoTypically they made sense in the infocom games. If you needed matches for something but had already struck and burned them all, you were stuck. Getting rid of dead ends makes some of these games feel like they are on rails. If you try enough combos of everything, eventually you'll progress.
- chme 10y agoThere 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.
- acomjean 10y agoIsn't avoiding dead ends one of the reasons you use a puzzle dependency chart? http://grumpygamer.com/puzzle_dependency_charts 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.
- Jtsummers 10y agoThat'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.
- zeta0134 10y agoThis 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. https://www.youtube.com/watch?v=6LO8Z1DkDqc&index=3&list=PLc38fcMFcV_ul4D6OChdWhsNsYY3NA5B2 https://www.youtube.com/watch?v=6LO8Z1DkDqc&index=3&list=PLc...
- mrfusion 10y agoNot to be too off topic but are there any good text adventure games for someone learning to read. 2nd grade level. I'm thinking that would be a great way to naturally practice reading comprehension since it forces you to think about what you read.
- tsomctl 10y agoDead tree version: https://www.amazon.com/R.-A.-Montgomery/e/B000APRDHS/ref=dp_byline_cont_book_1 https://www.amazon.com/R.-A.-Montgomery/e/B000APRDHS/ref=dp_... Edit: Looks like you're better off buying them used off eBay.
- cowardlydragon 10y agoDid he do all the Choose Your Own Adventures?
- lsaferite 10y agoOn an only mildly related note (as a lover of CYOA books): https://boardgamegeek.com/boardgame/169984/stowaway-52 https://boardgamegeek.com/boardgame/169984/stowaway-52 https://boardgamegeek.com/boardgame/192729/jump-ship https://boardgamegeek.com/boardgame/192729/jump-ship
- tzs 10y agoThere 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. [1] https://www.amazon.com/dp/B00S3OVV0I/ https://www.amazon.com/dp/B00S3OVV0I/ [2] https://www.amazon.com/Escape-Fire-Island-Destiny-Adventure/dp/B000HT218S/ https://www.amazon.com/Escape-Fire-Island-Destiny-Adventure/...
- komali2 10y agoNot about the game: 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?
- zellyn 10y agoIt appears to be a direct link to a README in a subversion repository. Are you arguing that all README files should be markdown or something? http://www.clifford.at/svninfo.html http://www.clifford.at/svninfo.html
- komali2 10y agoNot 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.
- forgotpwtomain 10y ago> 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.
- bluetwo 10y agoRelated question: Do you think an all text MOOC would find a following?
- wodenokoto 10y agoisn't that what Codecademy is?
- bluetwo 10y agoI actually meant to ask about MMOGs. Sorry.
- CogDisco 10y agoYou mean MUDs or MOOs?
- bluetwo 10y agoI guess I do.
- macintux 10y agoThey 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.
- deleted 10y ago[deleted]
- sblom 10y agoAndrew Plotkin (aka Zarf) wrote and published PlotEx[1] while working on Hadean Lands. [1] http://eblong.com/zarf/plotex/ http://eblong.com/zarf/plotex/
- nathan_f77 10y agoI 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? http://www.cprover.org/cbmc/ http://www.cprover.org/cbmc/
- jepler 10y agocbmc 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.
- sharpercoder 10y agoI 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 ;)
- a1studmuffin 10y agoVery novel approach! I can't see this scaling to the scope of most modern games though. Eventually it always comes back to an army of QA testers.