-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathindex.html
More file actions
431 lines (328 loc) · 22 KB
/
Copy pathindex.html
File metadata and controls
431 lines (328 loc) · 22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
<!doctype HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>PlotEx: a tool for exploring puzzle plot constraints</title>
<style type="text/css">
pre { margin-left: 3em; }
p.Center { text-align: center; }
.Spell { font-variant: small-caps; }
</style>
</head>
<body>
<h2>PlotEx: a tool for exploring puzzle plot constraints</h2>
<p>
<em>(Release 1.1.1. The PlotEx script is in the public domain.)</em>
</p>
<ul>
<li><a href="docs.html">Read the PlotEx script documentation</a>
<li><a href="plotex.py">Look at the PlotEx script</a> (or, <a href="plotex3.py">Python 3</a> version)
<li>Look at the <a href="enchanter.py">Enchanter example</a> or the <a href="blank.py">blank example</a>
<li><a href="plotex.tar.gz">Download the script with all sample scenarios</a>
</ul>
<p>
Designing a large puzzle adventure game (whether text-based or graphical) requires a lot of persnickety detail work. But one also has to keep track of the underlying (or perhaps over-floating) plot; and this <em>also</em> requires a lot of annoying details. Imagine you're three-quarters of the way through building a game, and you decide one particular puzzle should have an alternate solution. Now you can get past the Guardian of Pheebor using either the potion of invisibility <em>or</em> the Rod of Lordly Tights. What does this do to your plot? Can the player save the potion for the Muffin Griffons, thus bypassing a puzzle that isn't supposed to be solvable until chapter 6?
</p>
<p>
(I'm using "plot" here to talk about the player's advancement through the game mechanics. This sort of plot may be only faintly tied to the game's <em>story</em>, but that's a digression for a different time.)
</p>
<p>
We clever designers have many tricks to deal with this. Typically we name a few critical resources, make sure each one chains neatly to the next, and then hang the rest of the game off of them. Or we might get fancy and make several plot threads available in parallel -- as long as they jump back together at a clearly-specified point.
</p>
<p>
Simple structures often come across as simplistic, however. Players can see these tricks too. (Quoting Rob Wheeler: "While playing you can start to feel the diagrams on the whiteboards that led to your experience." That's out of context, but I couldn't let that admirable distillation be lost to history.)
</p>
<p>
So what is a designer to do? One can only hold so much in one's head at a time. "Be smarter than all your players" was unlikely advice even before the Internet turned players into an unstoppable puzzle-devouring hydra.
</p>
<hr>
<p>
Game designers (the mathier ones, at least) have often talked about "plot graphs" as a way to visualize design. (See, e.g., <a href="http://www.xyzzynews.com/xyzzy.4e.html">C.E. Forman's article</a> in XYZZYNews 4. Spoilers for <em>Enchanter</em>.) A graph (directed acyclic graph, says the pedant) should be exactly the right structure for expressing puzzle requirements and how they interact. Doesn't this solve the problem?
</p>
<p>
It does, in part. You can draw a graph for your game, and it will give you a good idea of where your game is broad and where it is narrow; which plot elements must be tapped right away, and which can be deferred until the end of the game. But the graph isn't so good for finding design problems, or looking at variations. The article linked above charts <em>Enchanter</em>. However, it doesn't try to represent the fact that the <span class="Spell">kulcad</span> spell can unravel many different obstacles -- but you can only cast it once. If you choose poorly, the game becomes unwinnable. (Arguably the trickiest challenge in the game, from the player's point of view.) To add these variations to the chart would clutter it with <span class="Spell">kulcad</span> nodes, and you would have to study the result carefully to understand that there's just one way to win.
</p>
<p>
What we want, then, is a way to graph a game <em>and</em> reassure ourselves that the structure works the way we want. (And no other.) PlotEx is a simple Python tool to accomplish that.
</p>
<hr>
<p>
I'll start with a simple example:
</p>
<pre>
# Our actions
FindSword = Set(sword=True)
FindLamp = Set(lamp=True)
EnterCave = Chain(Has(lamp=True), Set(underground=True))
FeedSelf = Lose('food')
FeedCyclops = Chain(Has(underground=True), Lose('food'), Set(kitchen=True))
FeedOrc = Chain(Lose('food'), Set(pants=True))
KitchenCook = Chain(Has(kitchen=True), Set(food=True))
# Our (sole) starting state
Start = State(food=True)
</pre>
<p>
Hopefully, this is pretty clear even at first glance. (Bar some brow-wrinkling about what needs to be capitalized and why there are sometimes quote marks.)
</p>
<p>
Our notional game has seven actions. For example, <code>FindSword</code> represents the player finding a handy sword hanging above a mantel; its action is to set <code>sword</code> to <code>True</code>. Then there's <code>FindLamp</code>. Then we see <code>EnterCave</code>, which chains together two pieces: <em>if</em> the player has the <code>lamp</code>, then the player can reach <code>underground</code>. The <code>FeedSelf</code> action has the player greedily devouring <code>food</code>; it is also possible to feed an orc or (once underground) a cyclops. Finally, <code>KitchenCook</code> is a way to get <code>food</code>, if the player has reached the <code>kitchen</code>.
</p>
<p>
The last line is not an action, but the player's starting state. We will helpfully start off with some <code>food</code>, since the <code>kitchen</code> is not immediately available.
</p>
<p>
The question, then, is: can the player reach the kitchen while wearing pants? (A daily challenge for many self-employed programmers.) If you graph the story, you wind up with an unenlightening straight chain. You might add some dead-end side branches where you feed the orc too soon, or eat the food yourself, but it's awkward.
</p>
<p>
Running PlotEx displays the following:
</p>
<pre>
<em>% python plotex.py</em>
<lamp pants sword underground>
(4): FindLamp, EnterCave, FindSword, FeedOrc
<lamp sword underground>
(4): FindLamp, EnterCave, FindSword, FeedSelf
*<food kitchen lamp pants sword underground>
(7): FindLamp, EnterCave, FindSword, FeedCyclops, KitchenCook,
FeedOrc, KitchenCook
3 terminal states (1 preferred) reached
</pre>
<p>
In other words, this game has three final outcomes -- one where the player eats the food, one where the player feeds the orc first, and one with the full cyclops-kitchen-orc solution. For each case, we can see how many actions were needed, and what they were. The asterisk indicates that the third solution is better than the others.
</p>
<p>
Notice that actions aren't once-only. In the third outcome, the player does <code>KitchenCook</code> twice. The food gets used up on the orc, so the player immediately runs back to get more food! As players will.
</p>
<p>
Of course this is less enlightening than a plot diagram in some ways. It does, nonetheless, answer the question.
</p>
<p>
If you <em>do</em> want a graph, PlotEx will provide one, with the help of the <a href="http://www.graphviz.org/">GraphViz</a> application. The states are somewhat collapsed, for simplicity, but the arrows show their actions. You can see that the important three final states are highlighted. (The dotted line, we'll get to shortly.)
</p>
<p class="Center">
<img alt="Test scenario graph: five nodes" src="scen-test.png">
</p>
<p>
We can do more, though. How far can you get if you never manage to find the kitchen?
</p>
<pre>
<em>% python plotex.py --block KitchenCook</em>
*<kitchen lamp sword underground>
(4): FindLamp, EnterCave, FindSword, FeedCyclops
*<lamp pants sword underground>
(4): FindLamp, EnterCave, FindSword, FeedOrc
<lamp sword underground>
(4): FindLamp, EnterCave, FindSword, FeedSelf
3 terminal states (2 preferred) reached
</pre>
<p>
We temporarily remove the <code>KitchenCook</code> action from the scenario, and the script tells us: three final outcomes, none reaching the <code>kitchen</code>.
</p>
<pre>
<em>% python plotex.py --block FindSword</em>
<lamp pants underground>
(3): FindLamp, EnterCave, FeedOrc
<lamp underground>
(3): FindLamp, EnterCave, FeedSelf
*<food kitchen lamp pants underground>
(6): FindLamp, EnterCave, FeedCyclops, KitchenCook, FeedOrc,
KitchenCook
3 terminal states (1 preferred) reached
</pre>
<p>
Without the sword, the player does fine. (Which was obvious upon inspection of the original code; nothing depends on having the sword. Look, it's an example.)
</p>
<p>
The script allows you to display all the intermediate states, if you like, or filter the output for states including a particular quality. You can also see which actions lead into and out of each state. But I won't force more examples on you.
</p>
<hr>
<p>
At this point I should back up and explain the underlying assumptions of this model.
</p>
<p>
A state is a set of qualities. So far we've only seen boolean qualities. Qualities can also be numbers, strings, or sets. So we could set up a state like this:
<p>
<pre>
Start = State(food=True, coins=2, ally='elf', spells=['summon', 'light'])
</pre>
<p>
(A quality's type must match across the entire scenario. You can't set <code>food</code> to be <code>True</code> in one place but <code>3</code> in another.)
</p>
<p>
An action changes one state into another -- or else it fails, doing nothing. Since states are just sets of qualities, an action simply changes some qualities, perhaps after checking other qualities to see if it can succeed.
</p>
<p>
Here's the most important thing: <em>by default, all qualities are assumed to be positive.</em>
</p>
<p>
Any adventurer knows that having food is better than not having food. You might need food at some point, but (in general) you'll never need to <em>not</em> have food. And if you did, you could just throw the food away. Similarly, having three coins is better than having two coins (or no coins). Knowing "summon" and "light" is better than just knowing "summon". Being allied to the elves is better than no alliance.
</p>
<p>
This underlies my earlier claim that some game outcomes are "better than" others. Having <code><food kitchen lamp pants sword underground></code> is strictly better than having just <code><lamp pants sword underground></code>, because all those qualities are positive. PlotEx takes that for granted, which lets it optimize its computation; but it also just makes it easier to set up your scenario.
</p>
<p>
Here's the second important thing: <em>any action that strictly improves a position is "free".</em> In the example, picking up the sword and lamp are free actions -- they don't cost anything. The same goes for entering the cave and cooking food; these have <em>prerequisites</em>, but not <em>costs</em>.
</p>
<p>
PlotEx collapses free actions together, both in its text and graph output. There's never a reason not to do them, right? So we might as well do them as a group. That's why some of the arrows in the graph have multiple actions labeled.
</p>
<p>
(This also explains the dotted arrow. From PlotEx's point of view, the "start state" already includes <code>lamp</code>, <code>sword</code>, and <code>underground</code>. Those first three actions are free, and don't need to be represented separately. But it would be confusing to leave off the start state, so we include it with a dotted line.)
</p>
<p>
Notice that this is a strict, and narrow, sense of "improvement". Winning the game is of course <em>good</em>, but it is not necessarily better than every other state. If you get stuck early, you haven't won, but you still have the invisibility potion (because you never reached the point where you had to use it). As far as PlotEx is concerned, this is a valid alternate outcome. You've traded off victory for a potion. If you could walk away with both, <em>that</em> would be the better outcome, but you can't.
</p>
<p>
(In contrast, the <code>FeedSelf</code> action in the example is completely useless. The player will never want to eat the food if there's nothing to be gained in exchange.) (A hunger timer is a different kettle of so-to-speak fish. You might set that up by losing the <code>food</code> in exchange for increasing a <code>nourishment</code> quality. You <em>wouldn't</em> decrease a <code>hunger</code> quality, though -- hunger isn't a positive!)
</p>
<p>
If you really need a negative quality, use a quality name that begins with an underscore. PlotEx will presume that <code>State(_hunger=2)</code> is worse than <code>State(_hunger=1)</code>, and both are worse than having no hunger at all. But positive qualities usually make more sense.
</p>
<p>
What about genuine choices? We saw in the no-cooking example that the player could wind up in <code><lamp pants sword underground></code> or <code><kitchen lamp sword underground></code>. Each of those has a quality that the other lacks, so neither is better than the other. You can also use a string quality. <code>ally='elf'</code> is neither better nor worse than <code>ally='dwarf'</code>. (Although, again, either is preferable to no alliance.)
</p>
<hr>
<p>
With all of this noted down in our spell books, we can revisit <em>Enchanter</em>. The complete script for it is <a href="enchanter.py">here</a>. The output:
</p>
<pre>
<em>% python enchanter.py</em>
*<adventurer bread exex friendlyturtle gondar guncho incastle
incourtyard knife krebf light melbor ozmoo rezrov shredscroll
vaxum water zifmia _did_action_1 _did_action_2 _did_action_3
_did_openoven _selfglow>
(22): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, SolveTerror, SpellOpenBox
<adventurer bread exex friendlyturtle gondar guncho incastle
incourtyard knife krebf light melbor ozmoo rezrov shredscroll
vaxum water zifmia _did_action_1 _did_action_2 _did_action_3
_did_action_4 _did_openoven _selfglow>
(22): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, SpellOpenDoor, SolveTerror
*<adventurer bread exex friendlyturtle gondar incastle incourtyard
intower knife krebf krill light melbor ozmoo rezrov shredscroll
vaxum water win zifmia _did_action_1 _did_action_2 _did_action_3
_did_openoven _selfglow>
(24): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, PassStairs, MeetKrill, SolveTerror, Win
3 terminal states (2 preferred) reached
</pre>
<p>
Winning the game is the last of these outcomes. The others represent mistakes. You can use up the <span class="Spell">kulcad</span> spell on the jewelled box; you can use up <span class="Spell">kulcad</span> on the guarded door.
</p>
<p>
(The previous release of PlotEx also listed the <span class="Spell">frotz</span> mistake -- you cast <span class="Spell">frotz</span> on yourself, thus making it impossible to visit the darkened gallery and find the <span class="Spell">ozmoo</span> spell. However, that was an inadequate description of the game! You <em>can</em> cast <span class="Spell">frotz</span> on yourself, as long as you do it <em>after</em> picking up <span class="Spell">ozmoo</span>. The output above now demonstrates this.)
</p>
<p>
One more feature. The state descriptions above are dense collections of labels; it's hard to see the differences. We can have PlotEx work out the differences for us:
</p>
<pre>
<em>% python enchanter.py -d</em>
(common state: <adventurer bread exex friendlyturtle gondar incastle
incourtyard knife krebf light melbor ozmoo rezrov shredscroll vaxum
water zifmia _did_action_1 _did_action_2 _did_action_3 _did_action_4
_did_openoven _selfglow>)
*<+guncho -_did_action_4>
(22): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, SolveTerror, SpellOpenBox
<+guncho>
(22): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, SpellOpenDoor, SolveTerror
*<+intower +krill +win -_did_action_4>
(24): FillJug, FrotzItem, GetRezrov, OpenGate, ExploreCastle,
FindGondar, FindPortrait, GetKnife, CutOpenBox, OpenNorthGate,
SearchCell, SleepInBed, TalkToTurtle, FrotzSelf, GetKulcad,
OpenEgg, FixScroll, SummonAdventurer, FriendlyAdventurer,
OpenOven, PassStairs, MeetKrill, SolveTerror, Win
3 terminal states (2 preferred) reached
</pre>
<p>
These are the same three states, but now they're described in terms of their differences from the "common state" shown at the top. (The common state isn't necessarily reachable; it's just the greatest common denominator of the three listed states.)
</p>
<p>
Now we can understand what's going on. In the first two states, you wind up keeping <span class="Spell">guncho</span> (because you never have a chance to use it). In the second state, you have <code>_did_action_4</code> (note that it's marked as <em>lacking</em> in the other two outcomes); this is the flag associated with picking up the pencil (after using <span class="Spell">kulcad</span> on the guarded door). And in the third state, you win.
</p>
<p>
Here's the <a href="http://eblong.com/zarf/plotex/scen-enchanter.png">graph of Enchanter</a>. Warning: very large, confusing, and not actually useful to look at.
</p>
<p>
This all seems sufficiently interesting to justify the effort. If not, you can try blocking various actions, to see where the player winds up getting stuck.
</p>
<hr>
<p>
And what have I learned from this?
</p>
<p>
First, states explode faster than I expected. The <em>Enchanter</em> example runs to 4468 states. I thought I could cut that down using worse-better comparisons -- short-circuiting states that are strictly worse than states already found. But it turns out that's not so easy.
</p>
<p>
(You could take every new state and compare it to every existing state, to find out whether it trumps (or is trumped by) a known state. But then you can't do anything with that information. The obvious shortcuts are asymmetrical; the resulting graph depends on the order the actions are tried. I don't want that.)
</p>
<p>
Running through 4468 states is fast on my brand-new Mac (3.4 seconds). It's probably pretty painful for those of you with older computers.
</p>
<p>
This model is great at representing achievements; it's fine for representing scarce resources. (You have to remember to mark actions as once-only.) It's terrible at representing timed puzzles. I didn't try to work <em>Enchanter</em>'s hunger, thirst, and sleep timers into the example. If I had, it would be the same way as Forman's graph: a general handwave of "you have to eat and drink at least once before fighting Krill." I wouldn't even attempt to set up <em>A Change in the Weather</em>, which is all about move counting.
</p>
<p>
The model also isn't very good at math, or complex algorithmic constraints (unless they can be broken down into simple dependencies). For <em>Hadean Lands</em> I wanted to set up a bit with transitive closure: if A likes B and B likes C, then A likes C. Doing that for one trio of qualities is easy, but doing it across a whole group required me to write a custom Action.
</p>
<p>
As I said, extending the script to generate a chart would be great.
</p>
<p>
I thought it would be useful to run the scenario as far as possible without action A, then add action A into the mix and see how much farther it gets. The script lets you do this, but it's hard to display the results in an interesting way. Blocking actions turns out to be more straightforward.
</p>
<p>
Python metaclasses are confusing, but with some help from Zack Weinberg and Aahz, I got them straightened out. Thanks!
</p>
<hr>
<p>
Update for release 1.1.0: (pretend this is a blog post, I dunno.)
</p>
<p>
As you see, I got some chart capability in there. Although for any real-sized game, the charts are too large to make sense of.
</p>
<p>
I finally figured out the right way to think about improvement actions. That's the business about "improvements are free"; the original release of PlotEx didn't have that notion. To be formal: we find the closure of a state under actions that strictly improve it. Since an action available in state X is available in all states strictly better than X, we can divide all states into equivalence classes based on their maximal (most-improved) state. We can then search through equivalence classes instead of states, which is a simpler problem.
</p>
<p>
Man, I haven't had a chance to break out the equivalence classes in years.
</p>
<p>
This cuts down Enchanter from 4468 states to 96, and it runs almost forty times as fast. (I put in a few other optimizations as well.)
</p>
<p>
Mind you, it's still pretty easy to overload the system. My old <em>Hadean Lands</em> overview scenario has 506 states. My current HL scenario, including every puzzle element, is 2160 states just in the first chapter! (I have more than the first chapter represented, but it's pretty clear that I'll have to run this thing in segments if I want it to finish in my lifetime.)
</p>
<hr>
<p>
Last updated June 1, 2012.
</p>
<p>
<em><a href="docs.html">Read the PlotEx script documentation</a></em>
</p>
<p>
<em>Other IF scripts: <a href="regtest.html">RegTest</a></em>
</p>
<p>
<em><a href="../home.html">Zarfhome</a></em>
<em><a href="../sitemap.html#plotex">(map)</a></em>
<em><a href="../cave/plotex.html">(down)</a></em>
</p>
</body>
</html>