Programming Open-Ended Plots In Games

[Brian]

Hi, there is a computer game that I play. It's a text-based RPG, and
you play it on the Windows Desktop. The game has an open-ended plot,
and I talked to the developer of that game, and he said the open-ended
plot means that he finitely programmed an infinite number of choices
that players can make during the main plot. He also said that nothing
is randomly generated in the main plot. I asked him how he finitely
programmed the infinite number of choices in the main plot without
anything being randomly generated, but he said that is his secret, and
he wouldn't give out his programming techniques. How do you think he
finitely programmed the infinite number of choices that you can make
during the main plot without anything being randomly generated in the
plot?

Brian

[Patricia Shanahan]

There are well known structures that can generate an infinite set from
finite information. One of the most important is a formal grammar - you
can see examples in most programming language specifications.

A compiler does not contain within it the infinite set of possible
arithmetic expressions (ignoring any limits on program size). Instead,
it has a finite set of rules about arithmetic expression structure.

Patricia

[Chris Uppal]

Patricia Shanahan wrote:
> > [...] He also said that nothing

> > is randomly generated in the main plot. I asked him how he finitely
> > programmed the infinite number of choices in the main plot without

> > anything being randomly generated, but he said that is his secret,[...]

>
> There are well known structures that can generate an infinite set from
> finite information. One of the most important is a formal grammar - you
> can see examples in most programming language specifications.

Also the code could use the system clock (current date-time, not milliseconds
since last boot) to provide "variety" without actually using a [P]RNG ;-)

Though if I were aiming for this, I'd probably use some sort of high quality
hash (SHA1 would be good enough) of the current gamestate and/or history to
provide fully determinate but not easily predicatable plot twists.

Not actually "infinite" though (except in the sense of arbitrary extensibility
that Patricia means) because a finite machine cannot provide infinite behaviour
without repeats[*].

-- chris

[*] One caveat: if you allow (unrealistically) the machine to have an
arbitrarily extensible memory, bus width, etc, and you come up with some scheme
to replace the fixed hash with hashes from an infinite family with unbounded
bit-length, and kept switching the hash as the game ran (say every 10^40 years
;-) then you might be able to make a convincing case that your game was
"potentially infinite"...

[osmium]

I think there is a needed but missing word in the English language to
classify things that are, for all practical purposes, infinite but not
infinite from the standpoint of a picky mathematician. Does any language
have such a word? Peninfinte is as good as I could come up with in
English.

And as a WAG, there are no non-picky mathematicians. In the same sense that
there are no white crows.

[Jussi Piitulainen]

osmium writes:

> I think there is a needed but missing word in the English language
> to classify things that are, for all practical purposes, infinite
> but not infinite from the standpoint of a picky mathematician. Does
> any language have such a word? Peninfinte is as good as I could
> come up with in English.

If there was a real need, there would be a word.

There are words that come close enough. Opening a large thesaurus at
"large" I find a number of candidates: one of "immense", "enormous",
"humongous", "ginormous", "superabundant" might be taken and defined
in a context to mean a number that is so large that it won't ever be
exhausted.

Another tack would be to play with "generative" and use several words
(this is often done in practice!) to convey the idea that the game
generates its plot, map, whatever as the players make choices, in a
way that won't be exhausted as long as anyone can possibly care.

> And as a WAG, there are no non-picky mathematicians. In the same
> sense that there are no white crows.

I suppose a mathematician is one who does mathematics. And mathematics
is what mathematicians do. Possibly in the same sense that there are
white crows.

[Daniel Pitts]

"Practically infinite" I think fits the bill, though it isn't a single word.

To put the numbers in perspective, a clock which keeps time in a 32bit
number-of-seconds-since-an-epoch is valid for 136 years. Adding one bit
doubles that time period. 64 bit value would store 584,554,531,341 years.

If your game state was encoded in 64bits, and changed ten times a
second, it could have enough different states that you play the game for
58 billion years and not see the same state twice.

That doesn't fit the definition of "infinite", but it is over 4 times
the age of the universe ;-)

[Charles Hottel]

"osmium" <r124c...@comcast.net> wrote in message
news:avron7...@mid.individual.net...

From Donald Knuth, The Art of Computer Programming:

An algorithm has 5 important features: (1) finiteness: i.e. terminates after
a finite number of steps (2) definiteness, (3) input, (4) output, (5)
effectiveness.

A computational method has all the characteristics of an algorithm except it
lacks finiteness.

[Brian]

Hi Patricia, you said formal grammar can generate an infinite set from
finite information. I looked up formal grammar on the Internet. How
do you use formal grammar to generate the infinite number of choices
that you want in the main plot of a game?

[Chris Uppal]

osmium wrote:

> I think there is a needed but missing word in the English language to
> classify things that are, for all practical purposes, infinite but not
> infinite from the standpoint of a picky mathematician.

"FAPP-infinite", "practically inexhaustible" (or infinite), "effectively
inexhaustible" (or infinite), "large enough" ?

But I can see problems with all of them.

-- chris

[Patricia Shanahan]

I did not intend to literally suggest using a formal grammar. Rather, a
formal grammar is an example of a finite generator whose possible output
is an infinite set of strings of unbounded length.

I do suggest thinking in terms of using generators for the game. For
example, as the player moves around generate new spaces, rather than
restricting the player to spaces that are already compiled in.

Patricia

[Brian]

Thank you everybody for the answers. I really appreciate the help.