Let's talk parsers!
Morgan Schweers
Something which never made sense to me was the dearth of good
parsers in adventure games. I've written a number of parsers over
the years, some for fun, some for more serious purposes. It's a
personal peeve of mine that most adventure games *DIDN'T* have
good parsers. (In fact, few have parsers above the level of the
tiny one that I'm about to post. That didn't take more than about
an hour to write. (I wasn't used to the language at the time.))
So, in the net.manner of wishing to help correct something,
let's have a talk on parsers.
Given an adventure game context, what sort of things are
required for a good parser. (OBTW, let's see some code as we go
along here. Maybe, just maybe, we could write a PD parser that
did things *RIGHT*.)
My personal recommendation for languages is the LEX (or Flex)
language, but let's hear your recommendations!
To start off, here's a stupid and simple parser that I threw
together many many moons ago. It *SHOULD* be pretty clear, so
convert it to your favorite language and repost it if you want!
(It's fully PD, since I don't think it's worth anything without
your input.)
----------- cut here ----------------
%{
#define TRUE 1
#define FALSE !TRUE
int already_yelled=FALSE;
main()
{
printf("What now boss?\n>");
while(yylex());
}
unrecognized_input()
{
printf("Are you being intentionally obfuscatory, or are\n");
printf("you just dense?\n");
}
/*
command_line is the text of whatever was entered at the prompt. From
here, judicious use of things like strtok, scanc/spanc, etc. should give a
reasonable parser. Here, all I do is increment command_line to avoid LINT
(or in my case, Turbo C's internal 'lint') giving me grief.
*/
analyz(char *command_line)
{
command_line++;
printf("Okay, ");
}
%}
VERB "take"|"get"|"drop"|"put"|"kill"|"read"
NOUN "gold"|"book"|"troll"|"sword"|"light"
SENTENCE {VERB}" "{NOUN}
FULLSENT {VERB}" "{NOUN}" WITH "{NOUN}
ERRORS ({VERB}" "{OTHER})|({OTHER}" "{NOUN})
IGNORE [\.\ \,]|"then"
OTHER [a-zA-Z0-9]*
%%
{IGNORE} { }
"QUIT" { printf("Bye boss!\n"); return(0); }
{VERB} { printf("Dude, you need to %s <something>!\n",yytext); }
{NOUN} { printf("What do you want to do to the %s?\n",yytext); }
{SENTENCE} { analyze(yytext); }
{FULLSENT} { analyze(yytext); }
\n { printf("What now boss?\n>"); already_yelled=FALSE; }
{ERRORS} { printf("You can't %s!\n",yytext); }
{OTHER} { if(!already_yelled) {
unrecognized_input();
already_yelled=TRUE;
}
}
%%
------------------- cut here -----------------
The above, run through FLEX, will produce a sad little parser, with
delusions of granduer. (It was based on an area off a BBS, where the
prompt was 'What now boss? >' and one would post up a message in the
form of:
">GET GOLD
There isn't any gold here to be gotten. You're in *THE WRONG GAME!*
>LOOK
Am I your personal slave? Look around for yourself!"
The messages (and the 'supposed parser') got pretty complex sometimes,
and pretty stupid sometimes. It was interesting though.
In any case, I'm interested in folks who have suggestions on improving
the parser. (No, it's *NOT* the best I've written. It's the shortest for
the level of action that it has.)
A few general comments... *YES* it probably would be a good idea to
replace the generic 'VERB' and 'NOUN' items with individual words, and use
them to match, so a specific numeric value can be evaluated immediately.
YES, it would make sense to modify it so that unrecognized values (such as
control characters) aren't just stupidly echoed to the screen. I'm posting
this exactly as it was, in the hopes that it will engender some discussions.
Anyone care to make the mods?
Basically, I'm asking what *SHOULD* be included in the parser (and methods
to do it), but I'm also asking the related question: What *SHOULDN'T* go in
the parser?
Also related issues... Should the parser be redefinable? I.e. Should I
be able to add new words as I wander through the story? (Most adventure games
say *NO!*. Why not? Why so? Why not so?)
Let's get some PROGRAMMING discussion going here.
-- Morgan Schweers
P.S. Not to be insulting, but I don't really feel like hearing from TEAM
CTHULHU unless they are interested in discussing hardcore implementation.
I've seen a lot of bluster from them, and that's all. They talk cool
stuff, but not much more. Sad, but true. No claims of 'WE HAVE THE
ULTIMATE IN PARSER TECHNOLOGY! IT'LL BE OUT REAL SOON NOW, AND YOU'LL
ALL BE DROOLING!' please.
+-----------
"Am I the only person who remembers Infocom's statement that 'We stick
our graphics where the sun don't shine!' on the same page as a blown-up
picture of a brain? Am I the only one who wishes those days were back
again? I recently had a person complain to me about the game 'Zork I',
that it didn't display the available commands so he could click on the
one he wanted. Is this what we've become? A nation of graphical interface
dweebs and unthinking slaves to the robot mouse? NO! Let us come together
and forge a newer, greater Infocom(tm)!" -- m...@netcom.com
-----------+
Stephen P Spackman
you should be using yacc and not lex (which is a lexer-generator,
after all).
But why not grit your teeth and take a shot at parsing some smallish
amount of "real" English instead? You might not be able to deliver,
but you'd surely have more fun....
Text adventures would be considerably more wonderful if they
understood a little more syntax and had large enough vocabularies that
you spent your time doing more than just typing in every word you can
think of to see which error message you got....
----------------------------------------------------------------------
stephen p spackman Center for Information and Language Studies
systems analyst University of Chicago
----------------------------------------------------------------------
Jon W{tte
in some yacc, too...
These parsers are static, though. What's hotter is dynamic parsers,
where not-presently-available words aren't recognized at all. The
parser should also analyze semantic meaning.
Build a table of words and their word classes (more than 1
allowed) and return token strings like:
"You see here a table and a shelf. There is a sword on the table.
There is a sword on the shelf."
>take the sword on the table
VERB#47 NOUN#11 PREP#13 NOUN#17
(Note: some words may be "safely" ignored, like "the")
Now, verb 47 would be sent a message to check wether there's
something matching 11 13 17 in the room. It would do so by
looking at each 11 in the room, asking it if it's 13 17. If
more than one matches, a suitable action would be taken.
Note: this assumes C++ or a similar object-oriented language,
but could easily be translated to any procedural language. A
table of "semantic functions" for the words would probably do.
This could very easily be extended to:
>take both weapons
VERB#47 FIXNUM#14 NOUN#22
Each object in the room would be sent a message asking if they
are 22 ? Since Sword inherits from Weapon, they would answer
yes, while obviously the furnitue wouldn't. Fixnum is a word
class demanding a certain number of matches. Count could be
another, so that
>take one weapon
VERB#47 COUNT#32 NOUN#22
would a) say "which wapon ?" or b) choose one randomly (I prefer
b)
The parser could allow for command-line completion, i.e. it keeps
track of what words are available at a particular moment and if
the token is a unique prefix for a word, it's assumed to be that
word.
'nuff dreaming. I'm back to the PBEM I'm writing using g++. It
will most probably never be finished, but it's fun doing it.
--
Jon W{tte
h...@nada.kth.se
- Power !
Sean Barrett
grammars you can match with regexps is pretty tiny; and besides
this, the lex program only RECOGNIZES the whole input as valid or
invalid; it doesn't help you break it into components.
The obvious alternative is yacc. I do not recommend using yacc
either. I'll herein reinvent my standard slitghly-better than
infocom grammar, and put it in yacc notation, because I can't think
of the right way to write BNF.
A quick guide to yacc notation: on the right is a rule--when a
given string matches what's on the right, then it matches what's
on the left. To match the thing on the right, it must be a sequence
of tokens such that every token/terminal (see below) is exactly
matched, and such for each nonterminal on the right, there is some
rule for that nonterminal which matches what's left; for example,
given
foo : bar BLEH bop
;
bar : HEH
;
bop : FEH
| MEH
;
then 'FEH' or 'MEH' matches bop, 'HEH' matches bar, and 'HEH BLEH FEH'
or 'HEH BLEH MEH' matches foo. Things get interesting when you make
recursive rules.
A SYNTAX-DRIVEN PARSER FOR ADVENTURE GAMES
First we need tokens, or terminals -- individual words that get
matched. I'll name these in uppercase:
NOUN (e.g. "gold", "sword", "airplane")
VERB (e.g. "take", "kill", "fly")
ADJECTIVE (e.g. "red", "sharp", "ugly")
PREPOSITION (e.g. "in", "on top of" <-- cheating, "through")
QUALIFIER one of "a", "an", "the", "all", "all of the"
CONJUCTION (comma, "and", "except")
to compress the grammar, I've cheated by making some things multi-word
tokens; this requires a bit more complicated lexical analysis.
Ok, now, the stereotypical adventure command is:
>get sword
>put sword in bag
>look in bag
>look
so we want something like
sentence : verb_phrase direct_object indirect_object
;
direct_object : noun_phrase
| /* empty */
;
indirect_object : prep_phrase
| /* empty */
;
If we might want to handle the dative shift, which transforms
>give the axe to the orc
into
>give the orc the axe
we need to change 'sentence' to
sentence : verb_phrase direct_object indirect_object
| verb_phrase noun_phrase noun_phrase
;
Ok. Now, what's a verb_phrase? Well, some verbs have "particles" or
other additions to them, and "go north" is easiest handled if we
still think of "north" as a verb, so we get
verb_phrase : prepless_verb prep_list
| prepless_verb
;
prepless_verb : VERB
| prepless_verb VERB
/* i.e. a string of at least one verb */
;
prep_list : PREPOSITION
| prep_list PREPOSITION
/* i.e. a string of at least one preposition */
;
Since we've got prep_list, I can specify a prep_phrase now:
prep_phrase : prep_list noun_phrase
;
Okey dokes. Now, what's a noun phrase? Well, the core of a noun
phrase is zero or more adjectives and a noun; many adventure games
give us the flexibility of omitting the noun itself...
noun_core : NOUN
| ADJECTIVE
| ADJECTIVE noun_core
/* i.e. a (possibly empty) string of adjectives followed */
/* by either an adjective or a noun */
;
then we can add a qualifier to the front
object : QUALIFIER noun_core
| noun_core
;
I call this 'object' because it usually picks out a particular object.
Now, the one step I go over infocom is to generalize the ability to
refer to an object by where it is.
located_object : object prep_phrase
;
We're nearly there now. We just need to relate a noun phrase
to located_object:
noun_phrase : located_object
| noun_phrase CONJUNCTION located_object
;
There, I'm done. Sort of.
First of all, don't even think about handing this to yacc. It's
amazingly ambiguous--
>put the ball in the box
might get parsed as having a direct object "the ball in the box",
where we wanted it to get parsed as having a direct object "the ball"
and an indirect object "the box". We can solve this either of two
ways -- we can have a list of "acceptable" prepositions for a given
verb, and refuse to allow those prepositions in location specifiers,
or we can get feedback from the database to find out whether there
is a "ball in the box", and if not, use backtracking. We're almost
certainly going to need backtracking for other things.
A major problem with this approach is that there may be ambiguities
in assigning token types to words--is "pilot" a noun or a verb? If
you want to allow both (and you will almost certainly encounter this),
you now have another decision to make for your backtracking procedure.
Backtracking may easily result in exponential performance--if there
are two or three choices of token names or productions for each
input word, you may have to check as many as 3^n items, where n is
the number of input words. A better approach is to use dynamic
programming. To do this, you'll have to put the grammar in chomsky
normal form (I think)--see the dragon book. Then you keep an n*n
table, in which each entry is a set of productions; the (i,j)th
entry in the table lists all productions which the substring from
word i to word j can reduce to--this technique, I suspect, runs
O(n^2*m), where m is the number of productions.
Note that the really critical part of parsing is relating it to
the database, a topic that I haven't covered here.
In the above grammar, I made the direct_object vs. indirect_object
distinction for simplicity sake. However, the dative shift rule
rather messed this up. There's another rule, particle shift, which
handles transforming sentences like
>take off armor
into
>take armor off
so if we want to parse that, we need another rule.
Here's the complete grammar again; you might want to change 'sentence'
to 'independent clause', and construct a multiple-clause parsing
grammar, although this requires multiple interpretations for the comma.
I got rid of direct_object/indirect_object and added a particle-shift
recognition production.
sentence | verb_phrase
| verb_phrase noun_phrase
| verb_phrase prep_phrase
| verb_phrase noun_phrase prep_phrase
| verb_phrase noun_phrase noun_phrase
| verb_phrase noun_phrase prep_list
;
verb_phrase : prepless_verb prep_list
| prepless_verb
;
prepless_verb : VERB
| prepless_verb VERB
;
prep_list : PREPOSITION
| prep_list PREPOSITION
;
prep_phrase : prep_list noun_phrase
;
noun_core : NOUN
| ADJECTIVE
| ADJECTIVE noun_core
;
object : QUALIFIER noun_core
| noun_core
;
located_object : object prep_phrase
;
noun_phrase : located_object
| noun_phrase CONJUNCTION located_object
;
I just made this grammar off the top of my head, so I might have
made some stupid mistakes--hopefully the intention is clear though.
I hereby formally enter this document, and especially the above
grammar, into the public domain. Go forth and multiply!
(P.S. Team Cthulhu are not more vaporcoders--they ran a mud more
than a year ago (I think) which had some of the features they've
announced.)
Mark Kantrowitz
>take the sword on the table
VERB#47 NOUN#11 PREP#13 NOUN#17
format:
(vp (verb "take")
(np (det "the")
(n' (noun "sword")
(pp (prep "on")
(np (det "the) (n' (noun "table")))))))
A grammar which can handle this is
VP -> verb NP
NP -> det N'
N' -> noun PP
N' -> noun
PP -> prep NP
In any event, doing "real" parsing is a nontrivial task (in fact, an
open research topic). Once one gets beyond a dozen or so rules in the
grammar, every new rule, unless carefully crafted, will result in
incorrect parses. One must also deal with ambiguous parses (Yacc and
Lex use LALR parsers, and do not deal with ambiguity), morphology,
and reference computation.
I'd suggest reading some of Gazdar's papers on GPSG. Allen's book on
natural language understanding makes an excellent introduction to the
subject.
--mark
Felix Lee
>understood a little more syntax and had large enough vocabularies
Dungeon (Zork) had a reasonable parser and an adequate vocabulary.
Filling in the missing pieces is a matter of getting people to play
the game and fixing every "I don't understand".
The real problems are in the model of the world. Text adventures make
poor virtual realities. Here are some of the problems.
* Objects.
It's easy enough to parse "pour some water", but you can't implement
it in Zork, because "water" is an indivisible object.
Objects in text adventures tend to be simple, immutable things.
Swords never break. Clothing never gets wet. You never disassemble
an engine for parts. You can't build a tent out of sticks and cloth.
The objects might as well be playing cards. Collect them all! And
you should collect them all, because anything that is an object (as
opposed to something in the background description) is probably
something significant in the game.
* Perception.
Adventures don't have a good model of perception. What the player
perceives is a simple, immutable text description.
In real life, identical objects are rare. If you have two similar
objects and you need to distinguish between the two, you will find
differences. With practice, people can distinguish one red-crested
heron from another. It's only machined, mass-produced items that have
a uniform, indistinguishable quality. Text adventures are filled with
machined, mass-produced objects.
Perception is a filter. Adventures give you no control over the
filter. How do you track someone through the woods? You have to
perceive small traces of passage, but you don't want to perceive
everything all the time, or else you become mired in a swamp of
useless detail.
Descriptions in adventures are heavily biased towards visual
perception. This is reasonable, given that "look" is a reasonable
command. But "listen" and "smell" are also reasonable, and they're
rarely useful in adventures. An interesting exercise would be an
adventure where the player is a person blind from birth.
* Space.
Doesn't anyone feel that the "rooms with exits" model has been
explored to death? Isn't it silly that crossing the Sistine Chapel is
no more and no less than crossing a living room?
Mazes in text adventures tend to be complex connected graphs of rooms
with identical descriptions (see Perception above). You won't find
anything resembling a real hedge maze.
Some graphic adventures at least have the notion of space within a
room, position and obstacles, but you still have rooms with exits.
Without a more sophisticated model of space you cannot give players
bazookas and let them blow holes in walls. People might rappel down
the side of a building, but you have to explicitly create all the
exits, which is tedious and error-prone.
* Actions.
Actions are as simple and immutable as objects. Most adventures do
not understand any adverbs. You cannot "tiptoe quietly past the
sleeping troll" or "slowly pour the nitroglycerine". Adverbs require
a more sophisticated model of actions.
If I've been to the throne room before, I shouldn't have to describe
every step of the way. It's like saying "raise right foot, place
right foot on third step, raise left foot, put left foot on fourth
step" rather than saying "climb stairs".
I think that's enough for now.
--
Felix Lee fl...@cs.psu.edu
Paul Crowley
to be talking to is not sci.lang but comp.ai, saying "Anyone out there
got any pointers to powerful knowledge representation systems?" Don't
look at me, I'm a Prolog programmer...
____
\/ o\ Paul Crowley ai...@castle.ed.ac.uk \ /
/\__/ Part straight. Part gay. All queer. \/
PS: I'm working on a powerful ambiguity-resolving parser based on an
LALR-style algorithm developed by a Japanese guy whose name I forget...
Terry Spurling
Anyone know of any ftp sites with docs on parsing and the like.
--terry spurling--
a babe in a world of giants.
Stephen P Spackman
In article <D88-JWA.91...@byse.nada.kth.se> d88...@byse.nada.kth.se (Jon W{tte) writes:
These parsers are static, though. What's hotter is dynamic parsers,
where not-presently-available words aren't recognized at all. The
parser should also analyze semantic meaning.
Better yet is static vocabulary, dynamic behaviour. "There's no sword
here!" is better than "I don't understand when you say 'sword'!"; and
better still is "There's not one here! Did you mean the one you left
in the hallway?"
In any case, even in the dynamic lexicon version you can still use
yacc, of course: using yacc deson't _condemn_ you to using lex, and
using lex doesn't _condemn_ you to using context-independent token
codes!
Build a table of words and their word classes (more than 1
allowed) and return token strings like:
"You see here a table and a shelf. There is a sword on the table.
There is a sword on the shelf."
>take the sword on the table
VERB#47 NOUN#11 PREP#13 NOUN#17
There's an important peripheral point to be made here: your input
parser should ideally be able to handle at least basic uses of *every
word that appears in the output*. It is a convention of human
interaction that if someone uses a word you can assume that they know
it and can use it back. The single most frustrating thing (IMHO) about
text adventures is their poor input vocabulary (I'm adapatble about
syntax, as a programmer, but remembering which words are "magic" is a
BITCH).
(Note: some words may be "safely" ignored, like "the")
(-: If this were true it wouldn't be there in speech :-)
The parser could allow for command-line completion, i.e. it keeps
track of what words are available at a particular moment and if
the token is a unique prefix for a word, it's assumed to be that
word.
Hm. Allowing more complex commands with several steps would probably
speed up input more.
Hey! Why not have a hypertext input scheme (I know this isn't what we
were talking about, but...): you select a grammatical template from a
list, and then fill in the arguments by pointing to words in the
description.... It'd be kinda slow but rather slick, I think....
Stephen P Spackman
In any event, doing "real" parsing is a nontrivial task (in fact, an
open research topic). Once one gets beyond a dozen or so rules in the
grammar, every new rule, unless carefully crafted, will result in
incorrect parses. One must also deal with ambiguous parses (Yacc and
Lex use LALR parsers, and do not deal with ambiguity), morphology,
and reference computation.
I'd suggest reading some of Gazdar's papers on GPSG. Allen's book on
natural language understanding makes an excellent introduction to the
subject.
If you already know some linguistics (quick check: X-bar, linear
precedence rules, autosegmentalism, did you blink? :-), look also at
Jerry Sadock's new book, _Autolexical Syntax_. It's not quite right
even desriptively (I'm convinced that there's a bug in the [-LC]
feature for nonlinear enclitics, for instance), but it's utterly cool,
direction-wise. We're getting close....
Anyone want to get serious enough about this that we can cross-post to
sci.lang without driving everyone batty?
Colin Adams
>In article <1991Apr29....@marlin.jcu.edu.au> cp...@marlin.jcu.edu.au (Colin Adams) writes:
>
>|Well, things get slower if you have dynamic object creation or creation
>|of rooms. There's no reason it can't be done, just you'll find it
>
>If the rooms aren't created dynamically, there's not much point in
>playing twice! The only difficulty with doing this is that now your
>gae has to synthesise descriptions (another unsolved problem...).
You can make a game worth playing more than once by using random
events and random characters (such as a murder mystery where a
different person is killed each game by a different killer with
different clues). But this is difficult to program so the gameplay
is good. Dynamic room creation is better for games you can
play > once, but I've never seen an adventure that does this.
>|whereas most adventure games
>|parser's (mine included) are based on verbs (commands), with lists
>|of relevant nouns passed to a separate routine to handle each command.
>|Naturally you can get the parser to do some general pre-processing.
>
>Wouldn't it be more straightforward to have the parser translate into
>a logical form, and use interpreter technology thereafter?
Could you elaborate on this point? I'm not sure exactly what you
mean.
>
>|2) make it easy to add synonym's (sp?) (like get=take=pick up)
>
>Buzz! Sorry. "Get the water" vs "Pick up the water" (only the first
>should work, water isn't solid). "Get the elf", vs "Pick up the elf",
>vs "Take the elf" which imply *very different degrees* of intimacy
>:-).
Ahhh. Yes a lot of people on this group are getting into real
natural language recognition. Fine if you are doing it on a mainframe,
or a machine with heap of memory. You really only have 512k for a PC
game and in that you have to fit pictures, sound, large amounts of
text and gameplay. It is very difficult to fit a complex parser in
as well. Look at magnetic scrolls, the game ignores the word "my"
totally. Although what I suggested above was a bad example, you
really do have to make some words mean the same thing (and hope
people don't type them in and think they got a wierd response) if
you want to save memory. Nowdays, animation is the big thing, which
means lots of ram...
If we still had all the memory to do a text only adventure in, 512k
would be great! Why doesn't everybody only have a vt100 terminal
at home ? :-)
>----------------------------------------------------------------------
>stephen p spackman Center for Information and Language Studies
>systems analyst University of Chicago
>----------------------------------------------------------------------
>consulting analyst Strategy First Software
>----------------------------------------------------------------------
--
Colin Adams
Computer Science Department James Cook University
Internet : cp...@marlin.jcu.edu.au North Queensland
'And on the eight day, God created Manchester'
Colin Adams
>Greetings,
> Something which never made sense to me was the dearth of good
>parsers in adventure games. I've written a number of parsers over
>the years, some for fun, some for more serious purposes. It's a
>personal peeve of mine that most adventure games *DIDN'T* have
>good parsers. (In fact, few have parsers above the level of the
>tiny one that I'm about to post. That didn't take more than about
>an hour to write. (I wasn't used to the language at the time.))
The death of parsers in adventure games is related to the death
of text based adventure games!!
> My personal recommendation for languages is the LEX (or Flex)
>language, but let's hear your recommendations!
I find using LEX too constricting for my purposes. Syntax alone
is not enough to solve complex problems, so you may as well write
your own system for speed and flexibility.
[simple parser deleted]
> Anyone care to make the mods?
Not me, I'm too busy on my own parser in C.
> Basically, I'm asking what *SHOULD* be included in the parser (and methods
>to do it), but I'm also asking the related question: What *SHOULDN'T* go in
>the parser?
You should have recursive reference to objects anywhere in command line,
maybe possession, adjectives (depending on how many you have you might
just make them two+ word names which reduce to 1 word when typed after
each other) and noun exclusion (get all except XX and XX).
The recursive reference to objects (put the gun in the box on the table
into my pocket) doesn't take too long to program, the way I've done it
is only about a hundred lines of code.
> Also related issues... Should the parser be redefinable? I.e. Should I
>be able to add new words as I wander through the story? (Most adventure games
>say *NO!*. Why not? Why so? Why not so?)
Well, things get slower if you have dynamic object creation or creation
of rooms. There's no reason it can't be done, just you'll find it
harder to use arrays etc. (though one could use hash tables etc. to
get the speed back). MUDS all have dynamic object creation as the
systems I've seen are based on objects, whereas most adventure games
parser's (mine included) are based on verbs (commands), with lists
of relevant nouns passed to a separate routine to handle each command.
Naturally you can get the parser to do some general pre-processing.
> Let's get some PROGRAMMING discussion going here.
Well, I think you underestimate the difficulting of writing a TOP CLASS
text adventure which caters for vitually everything most people will
type in and is relatively bug free. The things playtesters think
of is incredible and they come up with logical solutions to puzzles
that you'd never think of yourself. And to sell a game you have to
hard lots of graphics and sound today as well! The parser itself has
to understand lots of variations of the same command more importantly
than other advanced features, or players spend most of the time
annoyed with the syntax.
As for designing a parser things to remember are:
1) make it portable
2) make it easy to add synonym's (sp?) (like get=take=pick up)
3) make it easy to add commands which mean the same thing without
much extra code. eg.
extinguish fire
pour water from bucket on fire
> -- Morgan Schweers
>P.S. Not to be insulting, but I don't really feel like hearing from TEAM
> CTHULHU unless they are interested in discussing hardcore implementation.
[who are TEAM CTHULHU???]
Stephen P Spackman
(P.S. Team Cthulhu are not more vaporcoders--they ran a mud more
than a year ago (I think) which had some of the features they've
announced.)
I can't personally vouch for their ability to deliver, but last year I
wrote a commercial poposal that looked quite a bit like their
description (they have us beat on a few points; and vice-versa). I'd
judge the technology to be real enough, modulo the needs of exciting
announcement texts, anyway.
Thomas M. Breuel
English, I strongly recommend that you consider using Lisp, Scheme, or
Prolog. There are, in fact, a number of good, free, and small Scheme
implementations around that can be interfaced easily with C and will
_not_ require enormous amounts of resources.
As for how to go about it, Winston's books on AI and Lisp programming
are a good starting point. And, there are a number of books on natural
language processing in Lisp or Lisp-like languages out there now.
Thomas.
Stephen P Spackman
|> Also related issues... Should the parser be redefinable? I.e. Should I
|>be able to add new words as I wander through the story? (Most adventure games
|>say *NO!*. Why not? Why so? Why not so?)
Well, it's hard to imagine it being an improvement to change the
vocabulary of the *parser* rather than just chagning the world model.
|Well, things get slower if you have dynamic object creation or creation
|of rooms. There's no reason it can't be done, just you'll find it
If the rooms aren't created dynamically, there's not much point in
playing twice! The only difficulty with doing this is that now your
gae has to synthesise descriptions (another unsolved problem...).
|harder to use arrays etc. (though one could use hash tables etc. to
|get the speed back). MUDS all have dynamic object creation as the
|systems I've seen are based on objects, whereas most adventure games
|parser's (mine included) are based on verbs (commands), with lists
|of relevant nouns passed to a separate routine to handle each command.
|Naturally you can get the parser to do some general pre-processing.
Wouldn't it be more straightforward to have the parser translate into
a logical form, and use interpreter technology thereafter?
|As for designing a parser things to remember are:
|
|1) make it portable
-> use tables, which is only sensible. Hardcoding is just not
appropriate for this task, IMO.
|2) make it easy to add synonym's (sp?) (like get=take=pick up)
Buzz! Sorry. "Get the water" vs "Pick up the water" (only the first
should work, water isn't solid). "Get the elf", vs "Pick up the elf",
vs "Take the elf" which imply *very different degrees* of intimacy
:-).
|3) make it easy to add commands which mean the same thing without
much extra code. eg.
extinguish fire
pour water from bucket on fire
Actually, there's no reason not to allow runtime code additions, if
you've got a fast interpreter in there. This can be useful if you
have a complex worldmodel.
----------------------------------------------------------------------
stephen p spackman Center for Information and Language Studies
systems analyst University of Chicago
----------------------------------------------------------------------
Stephen P Spackman
>|whereas most adventure games
>|parser's (mine included) are based on verbs (commands), with lists
>|of relevant nouns passed to a separate routine to handle each command.
>|Naturally you can get the parser to do some general pre-processing.
>
>Wouldn't it be more straightforward to have the parser translate into
>a logical form, and use interpreter technology thereafter?
Could you elaborate on this point? I'm not sure exactly what you
mean.
Well, the structure of language is not transparent. Even in compilers
we use intermediate codes that bring out the underlying semantics of
the language. It seems only reasonable that you'd want to translate
the input text into some nice tree-structured representation, screw
around with that a bit (depending on how transformational your
religion is and how much you want to get into pragmatics :-) and then
interpret the output as a command in some abstract programming
language. No?
Nicklas Ungman
important as the parser, is the Inverse Parser. The inverse parser
generates text of a language from a specific event.
Using an inverse parser will make the output from the computer more
dynamic and natural. The output can also be fed to the parser, so
that non-human characters have exactly the same set of commands as
the human characters.
Another usefull thing is that the parser fills in with obvios actions.
The following coversation can drive anyone crazy:
> Go thru the door.
You can't, the door is closed.
> Open the door.
You can't, the door is locked.
> Unlock the door.
The door is now unlocked.
> Open the door.
The door is now open.
> Go thru the door.
etc., instead of the following:
> Go thru door.
The door is closed and locked, so you unlock it with your key,
and open it and then goes thru it.
or:
The door is closed and locked, and you don't have any key.
This may seem difficult to do, and I actually don't know how.
Any ideas?
/Nixxon
David Daniel
[]These parsers are static, though. What's hotter is dynamic parsers,
[]where not-presently-available words aren't recognized at all. The
[]parser should also analyze semantic meaning.
[]
[]Build a table of words and their word classes (more than 1
[]allowed) and return token strings like:
[]
[]"You see here a table and a shelf. There is a sword on the table.
[]There is a sword on the shelf."
[]
[]>take the sword on the table
[]
[]VERB#47 NOUN#11 PREP#13 NOUN#17
[]
[](Note: some words may be "safely" ignored, like "the")
A parser like this was written about five years ago. It appeared in a game
called THE PAWN, by Magnetic Scrolls and distrubuted by Firebird Software.
It was written for the 6502 chip (gasp!) in assembly (double gasp!!).
It would do nifty things like:
Drop all, except the pouch and the rake, get the bottle, go north
Would return:
Hammer dropped
Hoe dropped
Knife dropped
You now have the bottle
You are in the....
It allowed a player to "speak" English to a game and not distract you with
syntactic demands.
[]Note: this assumes C++ or a similar object-oriented language,
[]but could easily be translated to any procedural language. A
[]table of "semantic functions" for the words would probably do.
C++ would probably be a good choice (I assume it would be fast enough to
handle huge arrays of nouns, verbs, pronouns, prepsositions, etc.)
[]This could very easily be extended to:
[]
[]>take both weapons
[]Each object in the room would be sent a message asking if they
[]are 22 ? Since Sword inherits from Weapon, they would answer
[]yes, while obviously the furnitue wouldn't. Fixnum is a word
[]class demanding a certain number of matches. Count could be
[]another, so that
[]
[]>take one weapon
[]
[]VERB#47 COUNT#32 NOUN#22
[]
[]would a) say "which wapon ?" or b) choose one randomly (I prefer
[]b)
The other feature onTHE PAWN parser allowed you to use pronouns:
There is a horse here.
>Put the book and bottle on him, mount him, go east
The book is on the horse
The bottle is on the horse
You're now on the horse
You're in the ....
As for mutliple choices as outlined above: THE PAWN parser would ask you to
specify which item you wanted. This makes sense since making the program decide
what item is logical to take would
necessitate 'mapping' the player into each location or using a random number
generator to decide which value to transfer to the player's possesion.
If you're standing in a room with two items, you're going to make some kind
of choice for some kind of reason about which one to take. This forces the
player to THINK about what he's doing.
Another nice feature of the game is that it let you put things inside things.
When you looked in the pouch it told you what was there. It also assigned
some kind of size value to each item so that some would fit it the pouch but
not in your pocket. Also note the following scenario:
>get rake
You're carrying too much to get the rake
>Put coin and key in pocket, put prism in pouch, get rake
The coin...
The key...
The prism...
You now have the rake
So the program subtracted from your (carrying) value as you placed things
inside other things. Handy and realistic.
[]The parser could allow for command-line completion, i.e. it keeps
[]track of what words are available at a particular moment and if
[]the token is a unique prefix for a word, it's assumed to be that
[]word.
[]
Right!
[]'nuff dreaming. I'm back to the PBEM I'm writing using g++. It
[]will most probably never be finished, but it's fun doing it.
[]
What's a PBEM?
[]--
[] Jon W{tte
[] h...@nada.kth.se
[] - Power !
--
David Daniel (The man with no disclaimer) tro...@polari.UUCP
IN CASE OF HEADER MUNGING USE: uw-beaver!sumax!polari!tronix
Verus amicus est tamquam alter Idem.
David Graves
I was sad to see them "fall from grace" in recent years, because it meant
that my investment was wasted (mostly). However, there are several very
good reasons why parsers make a lousy user interface. Here are a few:
Parsers give the impression of allowing greater freedom of expression to
the player. After all, he can type *any* command, right? Well, he can
type any command that is recognizable by the parser. This is still more
than what you get with a graphical user interface, isn't it? No, it's not!
When you design a parser, all you are doing is hiding the limitations of
your user interface. This means that the user gets to learn how to use
your interface by trail and error. Trial and error is not fun. A graphical
user interface shows the user what he can do, right there on the screen.
This leads us to the next reason why parsers are a lousy interface: during
all this trail and error, the poor user makes alot of mistakes. This
provides the programmer with the opportunity to provide insults. This
is hard to resist -- I noticed that you couldn't. (printf("Are you being
intentionally obfuscatory, or are you just dense?\n"); Even if you decide
to guide the player towards correct input in a non-insulting way, the
poor user is still in the role of being the dunderhead. Compuers already
are too intimidating for a tremendous segment of the population. Let's
not make it worse.
Parsers make you type. You and I can type. Most everyone reading this
note can type reasonably. You think we are in a majority? Programmers
and writers think typing is as natural as can be. The typical consumer
does not agree. If you can allow the user to express all the commands
that your interface accepts *without*typing*, then you have added tremendous
value to your product.
Not that I want to burst your bubble. If you would like to build a good
parser, go to it! Just be aware that it won't be embraced by the majority
of interactive fiction enthusiasts.
You suggested "Let's get some PROGRAMMING discussion going here." Well,
it turns out that this group is focused on the *artistic* aspects of
interactive fiction. We discuss the application of technology to the
creation of IF, we discuss IF theory, and we challenge each other with
thoughts on where this genre is going or could go. It seems, however,
that there are alot of readers of this group that are *really* interested
in talking about programming. I'm willing to support that, but suggest
that we focus on design rather than coding. Those who are dying to
talk bits and bytes can do so in several other notes groups which focus
on programming, but there is only one notes group that focuses on IF.
I wrote an article on adventure game technology several years ago. The
information is still reasonably up to date. Here is the section of that
article which talks about parsers, along with some related sections. I
included the section on text generation because it's somewhat related to
parsing (just going the opposite direction).
-------------------------------------------------------------------------
ATTRIBUTES OF OBJECTS
All objects have characteristics or "attributes" that define that object's
limitations. Some attributes are boolean (stating whether this object is
flammable or immovable for example) and some may have a numeric value
associated with them, such as the weight and volume of an object. Some
attributes are unchangeable (such as flammability and mass) and some are
variable, describing only the current state of an object (i.e. closed, locked,
and burning).
Using attributes to define how an object may be manipulated within the model
world allows the programmer to define a much more consistent and dynamic
world. Consider the case where the programmer creates a fireplace and some
logs. He adds some special case logic to his program that will support
burning the logs with the expectation that the player will attempt to burn the
logs in the fireplace. However, if the player tries burning a chair in the
fireplace, nothing happens because the luckless programmer didn't think of the
player trying that.
This mess can be avoided by building the game's verb routines around a system
of attributes. By defining the attribute "flammable" and making the Burn verb
check for the presence of this attribute, the programmer allows the player to
burn down anything flammable, such as furniture, papers, doors, and fireplace
logs. Thus, he defines the generalized phenomenon of "burning" rather than
coding individual cases.
Once the programmer has decided on the set of attributes he wishes to support,
he need only write individual action routines that manipulate those
attributes, then decide which attributes apply to each of his objects. Thus,
some whiskey could be defined as having the attributes liquid, edible, and
flammable. Groups of attributes can work together in subtle and wonderful
ways, allowing the player to perform activities in ways not even considered by
the programmer. Would you think of putting moonshine whiskey in a lantern if
you had no kerosene?
RECOGNIZING NATURAL LANGUAGE
Understanding natural language has proven to be a difficult problem in AI, but
much can be accomplished in a participant novel by recognizing relatively
simple statements in the following syntactic form:
[Subject] VerbClause [DirectObject] [Preposition IndirectObject]
Optional sections of the syntax are enclosed in brackets. Each word in a
command typed by the player is looked up by a dictionary routine and is
identified as a verb, noun, adjective, or whatever. The most simple command
or "statement of intent" is simply a verb. Instructions to another person are
indicated by using that person's name as the subject of the sentence, as in
"Sam, run!". Omitting the subject of the sentence implies that the player
himself is the actor. Direct and indirect objects are noun clauses, which
consist of some optional adjectives followed by a noun. Prepositions like
"at," "in," and "on" separate a direct object from an indirect object.
Conjunctions (such as "and"), punctuation, and articles (such as "a" and
"the") can be tossed out by the parser as "noise", or verified to appear in
the expected positions.
This syntax will accept input strings such as "Put the gray stone into the
large oak chest". By further extending the parser to allow a list of objects
as a direct object and allowing sentences to be strung together, the program
can recognize statements like "Open the chest, take the lamp, the knife, and
the long rope, then climb the stairs". Since everyone has a slightly
different way of saying what they mean, the program must have a very large
dictionary with links between synonyms. Thus, "Set the lamp on the table" and
"Place the lantern onto the table" could be recognized as having the same
meaning.
Travel is something that happens frequently in this type of game, so it should
be very easy for the player to express what is desired. The parsing scheme
above will recognize travel syntax such as "Climb the tree" or "Enter the
cottage," but not "Go east" or its abbreviated forms, "East" and "e".
Recognition of these few irregular forms can be added to the parser as a
special case.
The parser should be able to recognize modifiers for verbs. The simple case
is the use of an adverb, as in "Carefully open the door". A more complex case
is where the player uses a verb and a preposition together in a way that
changes the meaning of the verb. For example "put down" means drop, "put out"
means extinguish, and "put on" means wear. This can be implemented by
creating a table with verb/preposition pairs followed by the resulting verb.
When a verb/preposition pair in the command string matches an entry in the
table, it can be replaced with the resulting verb. Parsing then continues as
if no preposition has been seen yet. This technique also allows recognizing a
command with a dangling preposition such as "Take the cloak off" which would
otherwise be rejected by the parser as an incomplete sentence.
We are all accustomed to using pronouns (such as "it") and expecting our
listener to resolve what we mean by reviewing the preceding context. A
natural language parser might be expected to do the same. A simple rule for
implementing parsing of "it" could be "Replace the 'it' with the last direct
object named". This allows proper parsing of "Put the lamp on the table and
light it," but not "Put the lamp into the chest, then close it". In the
second statement, the player probably meant to close the chest, not the lamp.
Changing the rule to use the last direct or indirect object in place of "it"
won't work in all cases either. The effect of this rule on the command "Put
the lamp on the table and light it" would be to set the table on fire. While
it is possible to define the semantics of "it" for each of these cases through
complex programming, it might make more sense to choose a simple rule, such as
"use the last direct object in place of 'it' in all cases," then inform the
user of the limitations of the parser through the game documentation.
The parser could be expanded to allow words such as "everything" or "all" in
place of a direct object. This lets the player make statements like "Drop
everything into the chest". Note that the semantics of "everything" change
with the verb used. In "Drop everything," "everything" really means
"everything that I'm holding," while in "Get everything," it means "everything
that I'm not holding". For some verbs, such as "Examine," the scope of the
word "everything" is "all visible objects, whether held or not". The player
may also wish to set the scope of "everything" to a limited domain, as in
"Look at everything on the table". Regardless of how "everything" is used in
a sentence, it can be implemented by simply calling the verb action routine
once for every object within the the command's scope.
GENERATING ENGLISH
While interacting with a participant novel, the player is going to read vast
quantities of text. Some of this may be "canned text" and some will need to
be generated. The constant attributes of a location could be described with
fixed text, but certainly not the descriptions of the objects there. Since
most objects can be moved around, placed in and on each other, and change
state, the program must be capable of dynamically producing the text to
describe them. The key to generating interesting text is to vary the length
of the sentences generated, vary the sentence structure, and use different
synonyms whenever possible. For example, to describe the "children" of a
table the program might generate: "There is a knife, some bread, and a key on
the table," or "A knife, some bread, and a key are on the table," or "Resting
on the table are a knife, some bread, and a key". The description generator
would have a list of synonymous phrases such as "resting on," "lying on," and
"sitting on".
A text generator must pay careful attention to the issue of grammar. When a
sentence contains a list of objects, the objects must be counted so that the
conjunction "and" can be inserted before the last object. Lists containing
more than one object will use "is" instead of "are" (except when using the
form "There is a <list>...."). Each object in a list should be followed by a
comma (except the last two) and preceded by a the appropriate article ("a,"
"the" or "some"). Selecting the article for an object depends on the
attributes of the object and the type of sentence. When introducing an
ordinary object, the article is "a" or "an". An object that has the attribute
of being "a quantity" (bread, wine, cheese) the article would be "some".
Familiar people would be mentioned by name, without any preceding article.
Objects that were mentioned recently would have the article "the". The
attributes of an object will also dictate the type of preposition used in the
generated text. For instance, describing the children of a surface (such as a
table) would dictate the use of "on," while containers would have things "in"
them.
The result of the player's actions can be reported via a text generation
facility as well. When the player enters a vague command such as "Drink," the
program would give all the details of what happened, like "You drink some cool
water from the stream," thus informing the player that his canteen has not
been taxed. This reporting mechanism should make use of pronouns (like "he,"
"she," or "it") when an object is mentioned more than once in a sentence, to
avoid generating text that sounds too mechanical. An example of this would be
"You give the bowling ball to Sam, but he drops it". As before, the
attributes of an object will aid in selecting the appropriate pronoun.
[end]
Philip J Stephens
>
>Another usefull thing is that the parser fills in with obvious actions.
>> Go thru door.
>The door is closed and locked, so you unlock it with your key,
>or:
>The door is closed and locked, and you don't have any key.
>
>This may seem difficult to do, and I actually don't know how.
>Any ideas?
Actually, it is very easy to do. If you've got a procedure that
handles the sentence "Go through <object>", then all that procedure needs
to do is check the status of the <object> to see if it's closed and/or
locked. If it's locked, it then calls the procedure that performs
"Unlock <object>", and if it's closed, it calls the procedure that
performs "Open <object>". Having done this, the procedure can move
the player through the door as required.
Thus you might end up with the response:
>Go through door.
You unlock the door.
You open the door.
You walk through the door.
If this is not what you want, you send a flag to the procedures
"Unlock <object>" and "Open <object>" that tells them not to print any
message, and get the "Go through <object>" procedure to print the
compound message itself.
In other words, getting an adventure game to act smart is merely a
case of writing smart procedures that check for all the possible
conditions and perform the unstated actions on behalf of the player.
In fact, now that you've pointed it out to me, the first text
adventure I write in ADL will have this feature :-)
<\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/><\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\>
< Philip J. Stephens >< "Many views yield the truth." >
< Hons. student, Computer Science >< "Therefore, be not alone." >
< La Trobe University, Melbourne >< - Prime Song of the viggies, from >
< AUSTRALIA >< THE ENGIMA SCORE by Sheri S Tepper >
</\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\></\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/>
G. Maddog Knauss
(I did some work with parsers about a year ago, but quit when I
realized that my magnificent breakthroughs were originally done in
1963.) Are there any games in existance that use all these funky
things that have been talked about here? Any place I can actually
see them in action?
--
-------------------------------------------------------------------------------
Greg "Maddog" Knauss "Aiee!" gkn...@sdcc13.ucsd.edu
-------------------------------------------------------------------------------
Morgan Schweers
Okay, a lot of folks dropped me lines on my message about
parsers. The honest answer here, folks, is *YES* THAT PARSER
WAS BRAIN DAMAGED. In fact, using [f]lex alone would be silly.
Yes, YACC is *VERY* useful in association with it.
The point was that I wrote that, having *VERY* little
experience with the language. It was also written in a very
short amount of time.
Some of my favorite stuff has been done in C++, in which I
can literally have my code *ASK* item <X> whether it has property
<Y>. (That's the effect, from my jaded eyes.)
I'm glad it engendered some discussion, too!
The discussion also branched onto rec.games.mud, to my suprise.
This brings up an interesting feature which I've run into on MUDs...
In some muds, every 'command' given is handed to every item in the
room (including the room) to determine if that item is interested
in handling the command. If it is, then it is passed to that item
and the item proceeds to do whatever with it. The last thing
'queried' is the universe. The universe has certain default actions
that it can take, such as getting/putting, etc. It seems that this
would be a good way to write a standalone adventure game as well.
It makes for 'intelligent' items, rooms, monsters, etc. This is
pretty clearly in the field of OOP. Does anyone actually use OOP
in writing adventure games? (*FLAME ON* Does anyone actually write
adventure games anymore, or do they just draw them? *FLAME OFF*)
Here are some comments I have on comments that have hit the news.
>From: ste...@estragon.uchicago.edu (Stephen P Spackman)
>If the rooms aren't created dynamically, there's not much point in
>playing twice! The only difficulty with doing this is that now your
>game has to synthesise descriptions (another unsolved problem...).
Aye, and a righteous idea this is too! Mayhap not a fully 'generated'
world, but one in which descriptions varied. A kind of merge between
Zork/Dungeon and Rogue/Hack. It's doable, but usually within a limited
scope. However, it would be easy to ascertain that all possible words
of description (for an object) are contained in the list for the object.
>From: cp...@marlin.jcu.edu.au (Colin Adams)
>Ahhh. Yes a lot of people on this group are getting into real
>natural language recognition. Fine if you are doing it on a mainframe,
>or a machine with heap of memory. You really only have 512k for a PC
>game and in that you have to fit pictures, sound, large amounts of
>text and gameplay. It is very difficult to fit a complex parser in
>as well. Look at magnetic scrolls, the game ignores the word "my"
>totally. Although what I suggested above was a bad example, you
>really do have to make some words mean the same thing (and hope
>people don't type them in and think they got a wierd response) if
>you want to save memory. Nowdays, animation is the big thing, which
>means lots of ram...
>
>If we still had all the memory to do a text only adventure in, 512k
>would be great! Why doesn't everybody only have a vt100 terminal
>at home ? :-)
ARGH! I *HATE* VIDEO GAME-ADVENTURES! I *despise* graphical
interfaces to my adventure games. If I can't *TALK* to the adventure
game, and *IMAGINE* what it's saying, then I DON'T WANT TO PLAY IT!
In all seriousness, the quality of text adventure games is *FAR*
superior to that of graphical adventure games. My imagination is
far more vivid and lucid than 800x600x256 graphics. My mind has a
far greater bandwidth than an RGB monitor.
Text adventures are, bar none, my favorite games. I've written
a few measly ones (even a few decent ones). The *ONLY* graphics I
ever used in an adventure game was the intro.
Now. Stating that memory is a problem is simply a cop-out
nowadays. If you are going to go all out on graphics, why not go
all out on the parser as well? You don't have to fit video, sound,
text, and gameplay all in 512K. What do you think a disk is for?
If you're going to distribute your game on ten floppies, why
would you have a poor parser? So it takes up an extra disk.
Oopsie. Seriously, some people *DON'T EVEN HAVE GRAPHICS* on their
machines. Why cut them out? Make your program text as well as
graphical. Seperate installation disks, maybe. (I'm the kind of
person who liked Lesiure Suit Larry when it was Softporn. It was
*COOL* back then. It needed a good parser, but...)
<Sigh> Sorry folks, tending towards flaming there... Back to
reality.
If you are interested in writing an adventure game, and not really
into all the marketing, etc., why not make it Shareware? There's a
reasonable amount of money in Shareware. Perhaps even a postcard from
folks who like your game! (Let me tell you, it'll make you feel *GREAT*!)
Now, let me go into some real-life examples... We'll start with
the greatest game company ever to exist, IMHO. Infocom. "We stick our
graphics where the sun don't shine." Great job guys! Their parsers still
rank as some of the best ever produced for gaming. $VERFY, I love ya!
<Grin>
Next, Steve Adams. They get the purple star for *WORST* parsers ever
created. Some neat game ideas, but *GOD* were they annoying! Two words,
in classic VERB NOUN format, *NOTHING ELSE*. They sold well, too. Scary.
The other company on my mental list is the company who makes the Ultima
series. (Don't remember their names...) They have an interesting
conversational parser. I recall hearing that the early versions were based
on key words, but it's been claimed that the later ones had reasonable
parsing. Anyone care to agree/disagree?
In any case, my point is that if Steve Adams games sold well with only
mediocre storylines, poor (if existant) graphics, and bottom-of-the-barrel
parsers, wouldn't a good story with a good parser do reasonably well?
This brings forth the question: What caused the death of text
adventure games. Frankly, I *DON'T* think it was Infocom's own internal
decision to release a graphics adventure game. I may be WRONG, but it
just doesn't jibe. Anyone know *WHY* they did? (Are there any ex-
Infocom programmers out there interested in talking about it?)
>From: step...@latcs2.lat.oz.au (Philip J Stephens)
> If this is not what you want, you send a flag to the procedures
>"Unlock <object>" and "Open <object>" that tells them not to print any
>message, and get the "Go through <object>" procedure to print the
>compound message itself.
>
> In other words, getting an adventure game to act smart is merely a
>case of writing smart procedures that check for all the possible
>conditions and perform the unstated actions on behalf of the player.
>In fact, now that you've pointed it out to me, the first text
>adventure I write in ADL will have this feature :-)
Yay! Nice to know that one good thing, at least, has happened so far.
Yes, this is an easy feature to implement. It *DOES* however point out
a feature that should be in the games. It's somewhat part of the parser.
That's what I'd like to hear... Implementation ideas. Stuff that can be
done, preferably with suggestions on how!
My first thought was: (In a horrid mixture of Lisp, C, and psudeocode.)
>Go through door
Door has problems: ((locked unlock) (closed open)).
While((CAR problems) != NIL)
Can_player_solve((CAR problems))?
Yes? Solve(noun, (CAR problems)), Set Problems=CDR problems
No? Error("<noun> is <problem>, and you can't <solution> it.",
noun,(CAR (CAR problems)),(CDR (CAR problems)))
These are things I'm especially interested in. I've noticed a few others,
so here are a few other questions...
Would it be appropriate for an adventure to allow sentences like:
take means get.
Which would make the word 'take' a synonym for 'get'. Is this something
that people see a use for in adventure games? How about an ability to travel
from point A to point B easily if one has already been that way, and nothing
has changed in the interim. Is that a useful feature? What if it were
disallowed through certain areas?
I noticed a serious branch in the discussion towards *REAL* language
parsing... Let's hear more about that! Especially references. I'd like
to know where I can learn about serious lexical handling, preferrably with
some real-world and sensible examples. (I don't know math, and I don't know
language wonderfully. I'm looking for things that will improve my ability
to write Parsers. Basically, anyone who is intelligent can write an Infocom
quality parser. That's why I have *NO* respect for companies that don't.
-- Morgan Schweers
+--------
These opinions are only mine. If you want them, take them. They are
hereby dedicated into the public domain, as well as any code I place here.
The only thing I request is that you not patent or copyright any code or
ideas that come from them. -- m...@netcom.com
--------+
Duane D Morin
) I never bothered to learn lex and yacc. I like to write all my own tools,
so I know how they work and can change the littlest details if necessary.
) I just finished (well, technically) a fairly large natural language parser
that uses a very traditional 'tree' format for its parser. Namely, you
start at the root node, and, depending on the "peek" at the next word, you
advance down levels of the tree until you can reach one that is qualified
as the end. Since this is implemented in C (over my preferred LisP), I have
not included any sort of subroutine handling, which tends to be a problem.
) Functionality of the words in the dictionary are bound somehow to the words
themselves. If its one thing I cant stand, its big switch statements or
huge if elses....its so much easier to say (*word[1].func)() and be done
with it.
) While the current parser doesnt do this, Im thinking about implementing the
following:
Instead of binding actions to the first word in a command (i.e.
if the first word is open, go to function open()...) bind the actions
to the LAST word in a trail of nodes that was traversed. Say, for
an easy example, that you can either just run, or you can run
<direction>. Using the traditional method, one would have to move to
a function for running, and then check for the existence of a
direction. But, if you bound a function to run AND one to
run <direction>, then you would already know that information and save
yourself trouble.
) This above method also allows you to set up various paths to get to the
same result (i.e. go <direction> can have the same results as walk
<direction> but go <in or out> can be mapped to enter or exit.
I'm not sure if anything Im babbling is of interest to anyone here, but it
was a nice chance to see some of my ideas posted. If they are of interest,
by all means someone let me know and I'll go about posting some code.
Duane Morin
Worcester Polytechnic Institute
Worcester, MA 01609
David Daniel
[]The real problems are in the model of the world. Text adventures make
[]poor virtual realities. Here are some of the problems.
[]
[]* Objects.
[]
[]It's easy enough to parse "pour some water", but you can't implement
[]it in Zork, because "water" is an indivisible object.
That's the programmer's fault. It's not too diffficult to have this scenario:
>Pour water
You pour the water from the bottle onto the floor making a large puddle.
Or....
>Pour water on plant
The plant absorbs the water and begins growing at a wild pace!
You would be left with an empty container in either case. I recall the
second scenario from one of the first adventures I ever played on a CPM
machine in '79 or '80.
[]Objects in text adventures tend to be simple, immutable things.
[]Swords never break. Clothing never gets wet. You never disassemble
[]an engine for parts. You can't build a tent out of sticks and cloth.
[]The objects might as well be playing cards. Collect them all! And
[]you should collect them all, because anything that is an object (as
[]opposed to something in the background description) is probably
[]something significant in the game.
Once again, you're describing programmer laziness as opposed to any CPU
deficiencies or lack of RAM. In THE PAWN, you could taste, smell, drink, eat,
wear things (armour, hats, shirts, etc.) use various tools and destroy various
items.
[]* Perception.
[]
[]Adventures don't have a good model of perception. What the player
[]perceives is a simple, immutable text description.
That's one of the reasons that graphics were adopted for AD games. It was an
easy way to fill the gap and make an expensive computer act like a TV set.
One of the things that AD games (and the next generation: IF) is missing is
good writers. Ones that can plot as well as write superb descriptions could
transform the genre.
[]Perception is a filter. Adventures give you no control over the
[]filter. How do you track someone through the woods? You have to
[]perceive small traces of passage, but you don't want to perceive
[]everything all the time, or else you become mired in a swamp of
[]useless detail.
[]
[]Descriptions in adventures are heavily biased towards visual
[]perception. This is reasonable, given that "look" is a reasonable
[]command. But "listen" and "smell" are also reasonable, and they're
[]rarely useful in adventures. An interesting exercise would be an
[]adventure where the player is a person blind from birth.
Yes, except that the majority of folks are sighted and we receive 90% of our
"input" via our eyes. A blind AD game would not be too playable, IMHO unless
the story was geared for it.
[]* Space.
[]
[]Doesn't anyone feel that the "rooms with exits" model has been
[]explored to death? Isn't it silly that crossing the Sistine Chapel is
[]no more and no less than crossing a living room?
[]
[]Mazes in text adventures tend to be complex connected graphs of rooms
[]with identical descriptions (see Perception above). You won't find
[]anything resembling a real hedge maze.
Sierra Online deserves credit for the Larry and Police series that incorporated
contemporary themes and environments.
[]
[]Some graphic adventures at least have the notion of space within a
[]room, position and obstacles, but you still have rooms with exits.
[]
[]Without a more sophisticated model of space you cannot give players
[]bazookas and let them blow holes in walls. People might rappel down
[]the side of a building, but you have to explicitly create all the
[]exits, which is tedious and error-prone.
However, real life contains many environments with walls and specific exits
at specific places. The need is for balance in IF applications that portray
reality instead of the convenience of the code writer.
[]* Actions.
[]
[]Actions are as simple and immutable as objects. Most adventures do
[]not understand any adverbs. You cannot "tiptoe quietly past the
[]sleeping troll" or "slowly pour the nitroglycerine". Adverbs require
[]a more sophisticated model of actions.
That statement is generally true, but some companies have forged a somewhat
abandoned trail past that limitation.
[]
[]If I've been to the throne room before, I shouldn't have to describe
[]every step of the way. It's like saying "raise right foot, place
[]right foot on third step, raise left foot, put left foot on fourth
[]step" rather than saying "climb stairs".
The reasons for this are primarily twofold:
1. Many (if not most or all) AD games were conceived and written by
programmers within companies that wanted a product ready to ship in X weeks.
One would tend to fudge a bit in order to satisfy the more pressing demands
and perhaps get on to a more interesting hack.
2. Writers, when confronted with the demands of mastering yet another language,
C or C++ or yacc or blac or yuk, tended to shy away from their grand intentions
of writing an IF masterpiece.
What's needed is a very friendly specialized language with good docs that
would allow anyone with a writing talent but not alot of programing savvy
to make good if not excellent IF. Yeah I know, good luck.
[]I think that's enough for now.
ditto
Stephen P Spackman
|One thing I haven't seen in adventure games, which IMHO is at least as
|important as the parser, is the Inverse Parser. The inverse parser
|generates text of a language from a specific event.
Text generation is another Unsolved Problem in AI. Theoretically (if
you think like a computer scientist) it should be easier than parsing,
but if wyou care about stylistics, it isn't (and believe me, you DO
care about stylistics. Computer generated text is generally TEDIOUS).
|Using an inverse parser will make the output from the computer more
|dynamic and natural. The output can also be fed to the parser, so
|that non-human characters have exactly the same set of commands as
|the human characters.
This is not a smart thing to do. The performance hit is going to be
unspeakable. Your entire game is going to run between three and six
orders of magnitude slower... :-).
|Another usefull thing is that the parser fills in with obvios actions.
|The following coversation can drive anyone crazy:
|> Go thru the door.
|You can't, the door is closed.
|> Open the door.
|You can't, the door is locked.
|> Unlock the door.
|The door is now unlocked.
|> Open the door.
|The door is now open.
|> Go thru the door.
|etc., instead of the following:
|> Go thru door.
|The door is closed and locked, so you unlock it with your key,
|and open it and then goes thru it.
|or:
|The door is closed and locked, and you don't have any key.
|
|This may seem difficult to do, and I actually don't know how.
|Any ideas?
In general you're going to have to do some fairly heavy pragmatic
analysis: to resolve ambiguities in a natural way you have to worry
about WHY the user issued the command. (For instance, in this case,
should you use the key or chop the door down?)
Once again, doing it some could be easy, doing it at all *right* is an
amusing challenge....
Joseph Allen
>Greetings,
Cool, a talk about parsers!
All of the game parsers I've seen are closed. WHat I mean is, the parser
ignores the environment almost completely (it context free..). So what I'd
like to see is a parser which takes into account the current context as much
as possible and I have some ideas on how to do it.
First, obviously, the english should be limited to commands and maybe
questions. It might be neat to have statements to add information to the
game... but that's a different problem.
So you have commands. To parse the command,
ignore the articles
find the verb
attach a list of found adverbs to it
adverbs are the only type of word that can preceed the
verb- so you know that in the case of verbs which can also
be nouns, if it's at the beginning of the sentaince, its
a verb.
find noun phrases. There are two types, the direct object (has
no preposition) and prepositional phrases (which do).
Now we start to take into account the current context. When you parse
a noun phrase, you might find an adjective. The adjective can be
used to distinguish which particular object you're refering to.
I.E., the blue ball, the smelly room, etc.
Now for the tricky part- prepositional phrases. There are two types.
Prepositional phrases which are really just more arguments for the
verb are easy (put the ball on the couch). But also we can have
prepositional phrases which help select the direct object or argument
prepositional phrases or even other selection prepositional phrases.
For example, "put the ball on the couch under the window"
requires the parser the know that there's a couch under the window.
Also, "put the pot on [the] top of the stove", the "of the stove"
selects which "top"
Also remember that there are multi-word prepositions. "in to"
"outside of", etc.
I think it's neat. The objects in the game universe can have all
kinds of relationships with each other and you can use these while
giving commands.
Now to make everything doubly complicated and possibly ambiguous, add
"and" to the system. And can be used all over the place. First,
it can seperate verb phrases "get the thing and and put it in the
box". It can also seperate adverbs "clip the blue and green wire"
And it can seperate multiple direct objects. "Clip the blue and
green wires" :-) I'm not sure how easy it would be implement all
these cases.
Next there's pronoun handling. Most systems just have "it" refer to
the previous direct object. What would be cool is to have it instead
refer to the last appropriate direct object (and query you before
doing anything to make sure). "Lift the stove. Fold the letter.
Put it under the stove. Put it (the stove) down."
A place where this type of parser would fit in well is MUSHi.
It would also be nice to have the programming language be in real
english:
Spell to light the lamp:
if the lamp is not lit then
get the matchbook,
rip out a match,
strike the match,
light the lamp with the match and
blow the match out
otherwise
say "The lamp is already lit you fool"
Now that would be interesting. "is" for checking states (of being)
--
#define h 23 /* Height */ /* jal...@ic.sunysb.edu (129.49.12.74) */
#define w 79 /* Width */ /* Amazing */
int i,r,b[]={-w,w,1,-1},d,a[w*h];m(p){a[p]=2;while(d=(p>2*w?!a[p-w-w]?1:0:0)|(
p<w*(h-2)?!a[p+w+w]?2:0:0)|(p%w!=w-2?!a[p+2]?4:0:0)|(p%w!=1?!a[p-2]?8:0:0)){do
i=3&(r=(r*57+1))/d;while(!(d&(1<<i)));a[p+b[i]]=2;m(p+2*b[i]);}}main(){r=time(
0L);m(w+1);for(i=0;i%w?0:printf("\n"),i!=w*h;i++)printf("#\0 "+a[i]);}
Ed Almasy
Does anyone know where I can get my paws on (C or C++) parser code to fool
around with?
Tim Brengle
stacks of goals for each character or player. Then change almost all
occurrences of error messages to push goals onto that stack instead.
drink( thing )
{
if ( !available( thing ) )
error( "You haven't got it yet." );
if ( !drinkable( thing ) )
error( "You can't drink that." );
if ( !open( thing ) )
error( "It is not open." );
consume( thing );
}
becomes
drink( thing )
{
if ( !available( thing ) )
push_goal( "get", thing );
if ( !drinkable( thing ) )
error( "You can't drink that." );
if ( !open( thing ) )
push_goal( "open", thing );
...
}
You get the idea.
Tim Brengle
Fantasy Architect
Interactive Fantasies
Steven Grady
>VERB#47 NOUN#11 PREP#13 NOUN#17
>(Note: some words may be "safely" ignored, like "the")
Articles can be useful. I was just talking to my brother, who is a
linguistics doctoral student at Berkeley, and he implied that articles
can be used to distinguish parts of speech. Briefly, there is a concept
of a "maximal" noun phrase (I think this is only in construction grammar),
which is a phrase which could be used as a subject. Thus "dog" is not
maximal, but "the dog" is. Well, my brother proposed that a prepositional
phrase must be followed by a maximal noun phrase. Thus:
"on top of the chair"
has the prepositional phrase "on top of", with "the chair" being the object,
but
"on the top of the chair"
has the preposition "on", with "the top of the chair" being the object.
The only distinction is the presence of "the". So don't be too quick to
"safely" ignore articles..
Of course, this assumes you want to parse "normal" English, as it is
actually spoken. It's convenient for a user to leave out articles,
however. But if you want to handle both verbose and terse (eg no
articles) language, you may have to deal with some ambiguities (where
the terse interpretation is different from the verbose interpretation).
--
Steven
gr...@fx.com
"To me it is like a mountain.. a vast BOWL of PUS!"
Stephen P Spackman
| The discussion also branched onto rec.games.mud, to my suprise.
|This brings up an interesting feature which I've run into on MUDs...
|In some muds, every 'command' given is handed to every item in the
|room (including the room) to determine if that item is interested
|in handling the command. If it is, then it is passed to that item
|and the item proceeds to do whatever with it. The last thing
|'queried' is the universe. The universe has certain default actions
|that it can take, such as getting/putting, etc. It seems that this
|would be a good way to write a standalone adventure game as well.
|It makes for 'intelligent' items, rooms, monsters, etc. This is
|pretty clearly in the field of OOP. Does anyone actually use OOP
|in writing adventure games? (*FLAME ON* Does anyone actually write
|adventure games anymore, or do they just draw them? *FLAME OFF*)
A game pretty much has to be written in an OO style, it seems to me,
but querying everything rather than using a parser that feeds into
some kind of physics module seems pretty braindead to me. I'd rather
use all those cycles for a REAL parser :-).
| Here are some comments I have on comments that have hit the news.
|>From: ste...@estragon.uchicago.edu (Stephen P Spackman)
|>If the rooms aren't created dynamically, there's not much point in
|>playing twice! The only difficulty with doing this is that now your
|>game has to synthesise descriptions (another unsolved problem...).
|
| Aye, and a righteous idea this is too! Mayhap not a fully 'generated'
|world, but one in which descriptions varied. A kind of merge between
|Zork/Dungeon and Rogue/Hack. It's doable, but usually within a limited
|scope. However, it would be easy to ascertain that all possible words
|of description (for an object) are contained in the list for the object.
Hm. Not sure what you mean. The problem is to produce adequately
varied and non-stilted descriptions of scenes, with no coldtext at
all. Doable, but *T*O*U*G*H*.
| In all seriousness, the quality of text adventure games is *FAR*
|superior to that of graphical adventure games. My imagination is
|far more vivid and lucid than 800x600x256 graphics. My mind has a
|far greater bandwidth than an RGB monitor.
Yeah, but using the monitor ain't inherently bad. It's good for maps,
at any rate, which ARE hard to give verbally (many novels have maps
for just this reason...).
| Text adventures are, bar none, my favorite games. I've written
|a few measly ones (even a few decent ones). The *ONLY* graphics I
|ever used in an adventure game was the intro.
| Now. Stating that memory is a problem is simply a cop-out
|nowadays. If you are going to go all out on graphics, why not go
|all out on the parser as well? You don't have to fit video, sound,
|text, and gameplay all in 512K. What do you think a disk is for?
|
| If you're going to distribute your game on ten floppies, why
|would you have a poor parser? So it takes up an extra disk.
|Oopsie. Seriously, some people *DON'T EVEN HAVE GRAPHICS* on their
|machines. Why cut them out? Make your program text as well as
|graphical. Seperate installation disks, maybe. (I'm the kind of
|person who liked Lesiure Suit Larry when it was Softporn. It was
|*COOL* back then. It needed a good parser, but...)
Hell, I've got a Sun 3 on one desk, a Sparc SLC in front of me, A
SparcStation1 that I'm actually running my newsreader on, and another
sparc and a next sitting idle in this room. And we're gonna be getting
in some new compute power in a few weeks. Then there're several more
offices on this hall. I wouldn't mind flattening the LOT of them if I
could get a good game out of it :-).
And I could probably soak up 200-300 meg of disk without anyone REALLY
getting upset - if other folks on the local net got to play. What's
the big deal? :-) :-)
| If you are interested in writing an adventure game, and not really
|into all the marketing, etc., why not make it Shareware? There's a
|reasonable amount of money in Shareware. Perhaps even a postcard from
|folks who like your game! (Let me tell you, it'll make you feel *GREAT*!)
Enough to eat?
| Would it be appropriate for an adventure to allow sentences like:
|
|take means get.
This would be pretty dangerous, since there's a great deal of evidence
that people don't have great insight into their own command of the
language :-). Macro processing does not a lexicon make....
| Which would make the word 'take' a synonym for 'get'. Is this something
|that people see a use for in adventure games? How about an ability to travel
|from point A to point B easily if one has already been that way, and nothing
|has changed in the interim. Is that a useful feature? What if it were
|disallowed through certain areas?
Like the door opening, this requires some pragmatics model and perhaps
a "guardian angle" player-surrogate. But honestly I nearly implemented
something like this for NetHack.
| I noticed a serious branch in the discussion towards *REAL* language
|parsing... Let's hear more about that! Especially references. I'd like
|to know where I can learn about serious lexical handling, preferrably with
|some real-world and sensible examples. (I don't know math, and I don't know
|language wonderfully. I'm looking for things that will improve my ability
|to write Parsers. Basically, anyone who is intelligent can write an Infocom
|quality parser. That's why I have *NO* respect for companies that don't.
Well, I've been talking about the real thing, and I'm interested in
Sadock grammars. Someone at the place, what is it, IIT? down the road
implemented a Sadock parser, but... I wasn't impressed (I went to the
thesis defense, don't have hardcopy yet). But that's like the real
real thing - the theory was only published last year and it's in heavy
linguist (and honestly are you really interested in the subtleties of
west greenlandic? :-).
stephen
Stefan Sortland
>
>adventure games. Frankly, I *DON'T* think it was Infocom's own internal
>decision to release a graphics adventure game. I may be WRONG, but it
>just doesn't jibe. Anyone know *WHY* they did? (Are there any ex-
>Infocom programmers out there interested in talking about it?)
>
> These opinions are only mine. If you want them, take them. They are
>hereby dedicated into the public domain, as well as any code I place here.
>The only thing I request is that you not patent or copyright any code or
>ideas that come from them. -- m...@netcom.com
>--------+
Well, I used to be a BIG Infocom fan, but over the years it just
lost something for me. Seemed like every game was just another treasure-hunt
with a few fun puzzles mixed in. The goals were very limited, and linear.
I'd like to see a goal-oriented game where all NPC''s have some goals, most
monsters goal would be to just find food, intelligent monsters would
have more complex and involved goals, splittable into managable sub-goals.
With some simple behaviour modeling, and the unpredictable interaction
between various persons goals, the game could became very interesting.
just a thought
Stefan
A. David Havill
> Next, Steve Adams. They get the purple star for *WORST* parsers ever
>created.
Do you mean Scott Adams?
>In any case, my point is that if Steve Adams games sold well with only
>mediocre storylines, poor (if existant) graphics, and bottom-of-the-barrel
>parsers, wouldn't a good story with a good parser do reasonably well?
I don't think so. If the person you're talking about is Scott Adams, then I
can say that the reason his adventures did well is because they ran on the
personal computers of the time-- which usually consisted of 16K and a lone
audio cassette recorder as the secondary storage medium.
Infocom's Zork was another breakthough. I thought it was a miracle that it
ran on my system at the time. The local Radio Shack advertised it as running
under a TRS Model I with 32K (!) of RAM and one single sided, single density
minidiskette drive. (Their terminalology for a non 8" drive) I believe Personal
Software was marketing it at the time. (The people that brought ya VisiCalc)
Infocom's "...we stick the graphics..." slogan lost ground when very good
graphics and large storage medium became available to the PC market. Perhaps
they felt they needed to keep up with the technology. It is no doubt that when
Activision bought them a few years back their graphics work rubbed off on
Infocom.
Perhaps a day and age will come when the computer generation seeks more than
the immediate material gratification that comes from 1024x768x256 graphics and
24 voice, digitized, stereo sound adventure games with a "point-and-click"
command interface. (Sierra, LucasFilm, a la others)
I like to think of the difference between the two as the difference between a
movie and a book. The both are respected works. Books certainly haven't died
in todays world-- although with the current illiteracy and education level
meters being at what they are, it's a bit astonishing! I have purchased both
the Infocom and Sierra games, although I don't own any graphic Infocom games.
The graphic games are having their day right now due to the computer media
breakthough. But don't count interactive fiction out forever.
--
+--------------------------------------------------+ Adrian "David" Havill
| "I have no meaningful quotes." -- me. | dha...@rucs2-gw.runet.edu
+--------------------------------------------------+ my opinions are not RU's
Felix Lee
No, no. I meant "pour some water", as in, don't pour all the water
from my canteen as I intend to use some of it later.
Yes, this is easy enough to special-case. "water" could be modeled as
a reproducible object with an amount attached, but my point is that
water is not a special case. Real objects are both divisible and
composable in arbitrary ways.
>In THE PAWN, you could taste, smell, drink, eat, wear things (armour,
>hats, shirts, etc.) use various tools and destroy various items.
Do you get debris when you destroy objects? I don't really need an
empty bottle, but I could use a sharp piece of glass.
The problem is you run into combinatorial explosion. Given N verbs
and M objects, you have NxM sensible actions. More if you have direct
and indirect objects. And still more if you can compose and decompose
objects. Granted, most of the actions fall into simple general cases
("you can't wear that"), but there are still a large number of
meaningful actions.
Let's take a simple object, a candle. The candle has a wick, wax, and
a brass candleholder. You can light it and extinguish it; that's as
far as most adventures go. Some adventures also model lifetime,
luminosity, and breezes that extinguish it. Here are things that
adventures do not model. A candle when lit is more cumbersome to
carry than a candle that's not. Travelling too quickly may extinguish
a lit candle. As wax gets consumed, the candle gets smaller and
lighter, but no less cumbersome to carry when lit. When the candle is
consumed, you're usually out of wick but not out of wax. A candle can
be carried lit without the candleholder (as long as it hasn't been
consumed too much), but it may not stay lit when set down, unless you
take the time to affix the candle upright (perhaps by dripping wax).
A candle can be cut into smaller candles, which will increase light
but decrease duration. You can extract the wick if you ever need a
small piece of string. The candle is a source of wax, if you ever
need wax. The candleholder is a useful object in itself; it can be
thrown to good effect, it will hold a small amount of liquid, etc.
You say none of this is useful and pertinent to the adventure? I can
use wax drippings to mark passages and intersections, helpful in
navigating mazes. I can throw a candle in hand at an enemy, maybe
blinding him, maybe hurting him, and maybe dousing the light so I can
sneak away in the dark.
Adventures do not encourage creative problem solving. Adventures pose
the question, "Can you discover the script? Can you find the key?"
So, okay. You've modelled a useful candle. Now can you model
burning? Nearly anything can be burned or heated. Temperature of the
flame is also an issue. Candles are unlikely to melt metals, but
sizable fires may melt gold. Adventures tend to model naive burning:
an object is either unaffected or completely consumed. You don't have
partially burnt books, clothing, plants, fur.
What I'm saying is, introducing a new object in your world may affect
every object and action that already exists. Most adventures cheat by
making objects less real than they should be. The objects are only
modelled enough to act as keys to particular puzzle locks.
Well-modelled objects can be done. Perhaps it's tedious to do. It
would be nice to have a language that easily supported well-modelled
objects, and a large library of general objects.
>However, real life contains many environments with walls and specific exits
>at specific places.
You've spent too much time in your office. Rooms are not real life!
"Rooms with exits" may be fine for caves, but it's merely adequate for
buildings, and inadequate for anything else.
You don't need a bazooka to punch through most interior house walls.
A good fist is enough. If I ever really need to get in the computer
room without a key, I could kick the door in, smash a window with a
convenient fire extinguisher, or crawl in through the ceiling tiles.
Forests, parks, golf courses, cities, streets, playgrounds, beaches,
lakes, rivers, mountains, cliffs, all of these are awkward when
squeezed into the "rooms with exits" model.
Ever accumulate two hundred objects in one "room"? Where do they all
fit? Are they in a heap or scattered about? Does it matter what the
"room" is? Broom closets and forest glades are similar, aren't they?
I guess I'm looking for the next step in adventure authoring
languages. Things like ADL and ADVSYS are adequate for adventures in
the classical sense, but they're inadequate for modelling anything
approaching reality.
Virtual reality isn't that hard to model, is it?
--
Felix Lee fl...@cs.psu.edu
David Graves
having the system fill in obvious actions, which Stephen Spackman noted
as being too difficult to be practical, or too demanding to get decent
performance.
I'd like to propose counter arguments to Stephen's. I can speak with some
authority, having completed code which performs all of these operations.
My software platform for interactive fiction can detect when a prerequisite
state attribute is not met, and push a goal onto a goal stack to resolve the
situation. Goals can give rise to sub-goals, which are resolved in reverse
sequence. Thus, when you give the command "drink the beer", the system
fills in the implied actions (get it and open it). The result of your
actions is reported by a text generation routine, with text such as "You
take the beer from the table, open it, and drink from it." [exact quote]
Stephen felt that in order to "resolve ambiguities in a natural way you
have to worry about WHY the user issued the command. (For instance, in
this case [a locked door], should you use the key or chop the door down?)"
I don't agree. The natural action is the common, obvious one. I have a
single rule in my rule base for this case: "When attempting to open a
object, and you discover it to be locked, call the unlock routine".
Breaking down a door is an uncommon solution to a common problem, so the
system should never "fill in the blank" with "break down the door".
My basic rule of thumb in designing rules for resolving unspoken commands
is: push goals on the stack which could correct a problem with *variable*
state. A door, for example, can be open or closed. These are examples
of variable state. It might be made of wood or stone. These are examples
of fixed state. You can't push a goal which will fix a problem with fixed
state (for example, the "burn" routine doesn't push a goal to make a rock
become flammable). Sometimes, you can't correct variable state either.
This means that the keyless user is likely to see messages like, "You can't
open the door, because it is locked".
Stephen states that "Text generation is another Unsolved Problem in AI."
This is not true. Currently, text generation has limited results, but that
is not the same as an "Unsolved Problem". There are papers readily available
which describe the current state of the art in text generation.
Stephen points out that "Computer generated text is generally TEDIOUS."
We can agree on this point! However, there are ways by which an author's
well-crafted text can be woven with computer generated text, so that the
text which must be generated "on the fly" is not too tedious. My system
does this at the level of the paragraph, the sentence, and even the sentence
fragment. You would have a difficult time identifying which words came from
the author and which ones were generated to match the particular situation.
Nicklas goes on to say:
The output can also be fed to the parser, so that non-human characters
have exactly the same set of commands as the human characters."
To which Stephen replies:
This is not a smart thing to do. The performance hit is going to be
unspeakable. Your entire game is going to run between three and six
orders of magnitude slower... :-).
Again, I disagree. My system uses parsed text as input and generated text
as output, with parse trees as the common intermediate representation.
The sematic routines are shared by human and automated characters, so that
ficticious characters can do anything that a person in that simulated world
can do. All this runs with quite reasonable performance on a bottom-of-the-
line personal computer. The key is careful design. The fact that I have
been working on this system for over seven years might have something to do
with it....
David Graves IF Platform Architect d...@hpsemc.cup.hp.com
Stephen P Spackman
interface and the need to make some commands terse. This has been
partly resolved in most games just by making the NL interface BAD -
commands like "north" or even "n" are accepted, even in contexts where
a human couldn't have recovered the implicit verb "walk". In fact
there's conceptually an NL parser and a unixoid command-line parser
COMPETING for the same input.
In NetHack on the other hand, the interface is vi-esque: you type a
letter and it happens (actually there IS the # command which COULD
have been used to introduce text commands except that the completion
logic took over and made it into an escape for a meta-shift key).
Now there are a number of things that could be done to make a clean
merger here. One is to say that commands take effect immediately
EXCEPT that, say, ' starts an NL command, and " means "say...". A
second would be that there's still a formal language competing
directly with NL but that they are distinguished by starting with
nonalphabetics; so "take a swig of rum" could be abbreviated (by
public convention) to !rum.... The final obvious possiblity is to go
like Emacs, and have non-printable characters name commands of
immediate effect....
The difference between these could be quite important for the process
of identification with your character. If you have to "speak"
instructions you get the feeling of a surrogate in the game world, I
find, whereas NetHack for all its shortcomings does seem to have a
sense of physical immediacy to it, as if that @-sign is YOU....
Philip J Stephens
>
>How about an ability to travel
>from point A to point B easily if one has already been that way, and nothing
>has changed in the interim. Is that a useful feature? What if it were
>disallowed through certain areas?
This is a feature that I have always wanted in an adventure; typing
in 'n','s','s','e,'w' etc. is very tiresome and a real distraction.
I always thought it would be nice to refer to locations by their
names, so that typing the name of a room would take you there by the
shortest route (provided you've visited it before). It is pretty easy
to implement: all you need to do is to create a single looped path
that passes through every single location (even if it means creating
local loops to get out of a dead-end); then a simple search of this
loop (removing the local loops) will give you the required path to the
room you desire. The game would then step you automatically through
each room, opening or unlocking exits as it went (so that you wouldn't
have to solve all the puzzles you did originally to get from point A
to point B).
This is a feature that I'd love to implement in an adventure, but
I'm not sure how well it would go down in ADL (this is a pretty good
parser and lisp-like language for writing text adventure games, if you
don't already know), considering global variable space is at a premium
in this language.
Felix Lee
> The door is closed and locked, so you unlock it with your key,
> and open it and then goes thru it.
> or:
> The door is closed and locked, and you don't have any key.
This is "basic competency": something that your simulation assumes the
player-character (PC) knows how to do.
The interesting problem is modelling "acquired compentency": something
that the player successfully steps through can become part of the PC's
repertoire of actions. This is probably most useful in navigation.
If I've been to the throne room before, I should be able to say "go to
throne room" from any part of the castle, assuming that I'm not lost.
--
Felix Lee fl...@cs.psu.edu
Stephen P Spackman
tractable. One of the things *I* like in a game is that the
restrictions that are placed on the player to make this true are
somehow "natural" *to the game physics*. For me, at least, that's more
important than faithfulness to the real world.
For instance, I like NetHack, and I hated the hitch-hiker's guide to
the galaxy game. One is consistent, if limited; the other is merely
random.
If the game model says that breaking something doesn't leave bits,
that's fine. If it says that it does leave bits, but the BITS can't be
broken ("they're too small!") that's fine. Telling me that only
watches and hedgehogs break, everything else is atomic, may fit the
plot but it SUCKS as a user interface decision!
Do others agree with me on this? If so, how do we manipulate the game
world to make these things feel right?
Andrew John Williams
>User interface question: there's a tension between having an NL
>interface and the need to make some commands terse. This has been
>partly resolved in most games just by making the NL interface BAD -
>commands like "north" or even "n" are accepted, even in contexts where
>a human couldn't have recovered the implicit verb "walk". In fact
>there's conceptually an NL parser and a unixoid command-line parser
>COMPETING for the same input.
My rather sick and twisted solution is this :
Everything in the game is an 'physical object', like the key, the sword,
the player, the rooms, the exits...
The exits - thats the important bit. All objects have a class (or
actually several classes). Exits belong to the 'Exit' class. Classes
have an implied verb associated with them, that the game is to use if
the player fails to give one. For exits this is 'Go' or 'Enter' or some
such. So if the player enters
> N
The game will look for an object called 'N', look at its class, and
since its an exit, give it to the 'Enter' verb. This will move the
player inside the exit. Now whenever something interesting happens, any
object that has expressed an interest in this even will be told about
it. Exits are interested in having other objects placed inside them. The
game will call the exit's 'something has been put inside you' routine,
which will dump the player into the room the exit leads to.
No, I haven't implemented any of this yet - I'm still looking for a
decent language. Turbo Pascal 6 just isn't up to it. Call that
polymorphism? I might have to write my own. Life is so sad
John West (stealing Andrew's account)
Eric the fish swings his sword and kills the giant
Felix Lee
>the galaxy game. One is consistent, if limited; the other is merely
>random.
Let's call it "orthogonality", rather than "consistency".
NetHack pretends to be orthogonal, but it fails in a number of ways.
One basic flaw (which it inherited from Rogue) is that the player is
something very different from a monster. For example, polymorphing
yourself is temporary, but polymorphing a monster is permanent.
The reason NetHack appears mostly orthogonal is a lot of people spent
a lot of time writing a lot of special-cased code. If it had a better
world model, it wouldn't need all that special-cased code.
>Telling me that only watches and hedgehogs break, everything else is
>atomic, may fit the plot but it SUCKS as a user interface decision!
This is why I want to model the real world. A game where nothing is
allowed to break is fine, but as soon as you introduce one thing that
can be broken usefully, you have to let everything break, potentially
usefully. It's not enough to say that everything except watches and
hedgehogs leaves "useless fragments" when broken.
You could program it case by case, object by object, but I think it's
better to try to model reality, or a subset of reality.
The real difference between NetHack and HHGTTG is that HHGTTG, and all
adventure games, are essentially long, complicated riddles. Your task
is to discover the answer the author intended. You cannot come up
with solutions like "drop the barometer".
NetHack, though it has its share of riddles, is dominated by problems.
The game poses a problem, like "get past a horde of orcs", and
challenges you to find any solution. It's not "find the fleece to
give to the witch to show you the cave with the magic lamp so you can
ask the genie to give you the magic flute to put the orcs to sleep."
Riddles can get tiresome after a while.
--
Felix Lee fl...@cs.psu.edu
Felix Lee
>when "n" is not an English word?
Consider "n" to be an idiom, useful in communicating in a limited
context (i.e., typing at adventure games).
--
Felix Lee fl...@cs.psu.edu
Stephen P Spackman
|Everything in the game is an 'physical object', like the key, the sword,
|the player, the rooms, the exits...
|The exits - thats the important bit. All objects have a class (or
|actually several classes). Exits belong to the 'Exit' class. Classes
|have an implied verb associated with them, that the game is to use if
|the player fails to give one. For exits this is 'Go' or 'Enter' or some
|such. So if the player enters
|
|> N
|
|The game will look for an object called 'N', look at its class, and
|since its an exit, give it to the 'Enter' verb. This will move the
|player inside the exit. Now whenever something interesting happens, any
|object that has expressed an interest in this even will be told about
|it. Exits are interested in having other objects placed inside them. The
|game will call the exit's 'something has been put inside you' routine,
|which will dump the player into the room the exit leads to.
Not a solution from my perspective, for a number of reasons....
Lessee. First of all, I wasn't meaning to how you'd IMPLEMENT it -
I'm definitely thinking about using NL parsing technology anyway. I
was meaning to ask a question about UI design, not code structure.
Secondly, er, I don't have rooms or exits, because I want a map....
And if I did have rooms, North would still be the name of a direction,
not an exit, I think.
And I'm really confused about things being placed inside doors. If
something is placed in a doorway, don't you want a message "there's a
rocking horse blocking your way", not "you are now inside the rocking
horse"? :-)
I can't overload geography on containment, because I want a theory of
containment (so the contents of a room are the contents of the room,
for instance :-).
But what I meant to ask was: how can commands like "n" be justified
when "n" is not an English word? Wouldn't ^N be better? or up-arrow?
Stephen P Spackman
|>For instance, I like NetHack, and I hated the hitch-hiker's guide to
|>the galaxy game. One is consistent, if limited; the other is merely
|>random.
|
|Let's call it "orthogonality", rather than "consistency".
I think these are separate issues. I'd say that NetHack was reasonably
consistent, but terribly inorthogonal (I said I liked NetHack.
Actually, despite having worked on it for a couple of years, I rarely
actually *played* it, it wasn't *that* good :-).
|NetHack pretends to be orthogonal, but it fails in a number of ways.
|One basic flaw (which it inherited from Rogue) is that the player is
|something very different from a monster. For example, polymorphing
|yourself is temporary, but polymorphing a monster is permanent.
Of course, this is steadily improving.
|The reason NetHack appears mostly orthogonal is a lot of people spent
|a lot of time writing a lot of special-cased code. If it had a better
|world model, it wouldn't need all that special-cased code.
Ain't that the truth.
|>Telling me that only watches and hedgehogs break, everything else is
|>atomic, may fit the plot but it SUCKS as a user interface decision!
|
|This is why I want to model the real world. A game where nothing is
|allowed to break is fine, but as soon as you introduce one thing that
|can be broken usefully, you have to let everything break, potentially
|usefully. It's not enough to say that everything except watches and
|hedgehogs leaves "useless fragments" when broken.
It's still better. Modelling the real world CANNOT BE DONE. We want to
look for things that CAN be done but are fun anyway (as a friend of
mine recently said to me: occasional lapses of omniscience are the
price I pay for being implementable :-).
|You could program it case by case, object by object, but I think it's
|better to try to model reality, or a subset of reality.
Or a reality, another reality. Of course.
|The real difference between NetHack and HHGTTG is that HHGTTG, and all
|adventure games, are essentially long, complicated riddles. Your task
|is to discover the answer the author intended. You cannot come up
|with solutions like "drop the barometer".
Quite.
|NetHack, though it has its share of riddles, is dominated by problems.
|The game poses a problem, like "get past a horde of orcs", and
|challenges you to find any solution. It's not "find the fleece to
|give to the witch to show you the cave with the magic lamp so you can
|ask the genie to give you the magic flute to put the orcs to sleep."
Any reason that can't be there in an adventure?
|Riddles can get tiresome after a while.
"A frog in a blender".
Sean Barrett
David Graves has made, but they are only minor problems; Mr.
Graves is certainly "on the right track", and pretty far down
it too.
So dag@hP emc.cup.hp.com (David Graves) says:
>Stephen felt that in order to "resolve ambiguities in a natural way you
>have to worry about WHY the user issued the command. (For instance, in
>this case [a locked door], should you use the key or chop the door down?)"
>I don't agree. The natural action is the common, obvious one.
The "correct" interpretation of the users input is, literally,
whatever-she-meant-by-it. I doubt, even if you've created true AI,
you can always determine what was meant. It *may* be that you
can be sensitive to the borderline cases and prompt for more information
in those cases.
There are two basic pitfalls here:
1) Doing something besides what the user meant
2) Doing something that the user didn't know how to do
The second may seem like a more mundane implementation problem,
but it's also unsolvable [that is, impossible to do "correctly"
according to a strict definition of correct as above], as I'm
about to illustrate, and it's also a trap which Mr. Graves *appears*
to have fallen into:
>single rule in my rule base for this case: "When attempting to open a
>object, and you discover it to be locked, call the unlock routine".
The trap of the second pitfall is that the user may be carrying
twenty keys, and not know which is the correct one, and as the
following message suggests, the way to determine if the player
can unlock the door is if he has the right key:
>This means that the keyless user is likely to see messages like, "You can't
>open the door, because it is locked".
Worse yet, the "key" might not be a key at all; it might be something
unobvious. You said above that you would never allow an automatic
solve that's unobvious; but you have to be careful about how you decide
whether something is obvious. If the player has done this before,
then it *is* obvious. If she's done it with another door/pseudo-key
combination, whose key looks mighty similar to this one, then it
might well be obvious. Worse yet, if I was just playing the game
at my friend's house, and we figured out about this unobvious key,
when I go back to my copy of the game, it *is* obvious to me what
the key is, but there's no way for the game to know this--this is
why the second pitfall is impossible to solve correctly--the parser
is an interface between the *player* and the game, not between the
character and the game, but the game can only determine the obviousness
of a solution to the character, not the player.
>Breaking down a door is an uncommon solution to a common problem, so the
>system should never "fill in the blank" with "break down the door".
If this is a dungeon filled with locked doors and no keys, it
is of course the common solution. Perhaps you think you can at least
determine what the common solution is for one fixed game, but perhaps
two different players will approach it differently--one likes to try
to find keys, the other to bash the doors down. What qualifies as
"a common solution" is to be found in how the game is actually played--
it may well be possible to have the game learn what the player
considers as the "common" or "obvious" solution.
Consider another example of yours:
[scenario 1]
You are thirsty.
> drink water
You drink deeply from the cool, fresh stream.
[not from the canteen, since that's got a finite amount of water:
but note that it's the programmer who has pre-established this
priority]
[scenario 2]
You are thirsty.
> drink water
You drink deeply from the cool, fresh stream.
This water leaves a funny aftertaste in your mouth.
You've been poisoned!
You die.
[scenario 3]
You are thirsty.
> drink water
You test the water from the stream.
This water leaves a funny aftertaste in your mouth.
You take a big gulp from your canteen instead.
If the programmer hasn't properly anticipated what the player's
priorities are, the programmer may cause the player to do something
the player didn't want to do. As Mr. Graves described it, scenario
1 & 2 are what would occur, if the character has no evidence that
the stream could be poisoned. This problem seems intractable too,
simply because it's underdetermined in the game, simply because
different players could intend different things by the same input,
and it may well be impossible to determine what they did mean.
Again, though, some sort of learning from past occurrences seems like
it would be a good idea.
And, in another post, he writes:
> Regardless of how "everything" is used in
>a sentence, it can be implemented by simply calling the verb action routine
>once for every object within the the command's scope.
This is an assumption, and probably not a very wise one. While, admittedly,
no examples come to mind of verbs that wouldn't like this, it seems to me
that it would make more sense to pass an array of objects to the verb
action routine instead of _assuming_ that the action operates on the
objects independently. A really wimpy example for which this wouldn't
work, although I'm sure someone can think of a better real-game one:
"draw everything on the table."
fra...@zaphod.uchicago.edu
>In article <1991May1.0...@netcom.COM> m...@netcom.COM (Morgan Schweers) writes:
>|This brings up an interesting feature which I've run into on MUDs...
>|In some muds, every 'command' given is handed to every item in the
>|room (including the room) to determine if that item is interested
>|in handling the command. If it is, then it is passed to that item
[...]
>|pretty clearly in the field of OOP. Does anyone actually use OOP
>|in writing adventure games? (*FLAME ON* Does anyone actually write
>A game pretty much has to be written in an OO style, it seems to me,
>but querying everything rather than using a parser that feeds into
>some kind of physics module seems pretty braindead to me. I'd rather
>use all those cycles for a REAL parser :-).
MUDs can't really do that, since they're extendible by users (in most
cases, by all players). You *could*, but it'd be pretty clumsy, esp.
since objects get moved around. (Of course, what he's talking about,
MUSH, is a pretty ugly language anyway....)
There's a MUD released recently, called LambdaMOO, which is OOP. (Or
so it's touted; I haven't looked at it.)
--
/============================================================================\
| Francis Stracke | My opinions are my own. I don't steal them.|
| Department of Mathematics |=============================================|
| University of Chicago | Earth: Love it or leave it. |
| fra...@zaphod.uchicago.edu | |
\============================================================================/
Stephen P Spackman
[...Interpreting commands by offering them to everything in sight...]
|>A game pretty much has to be written in an OO style, it seems to me,
|>but querying everything rather than using a parser that feeds into
|>some kind of physics module seems pretty braindead to me. I'd rather
|>use all those cycles for a REAL parser :-).
|
|MUDs can't really do that, since they're extendible by users (in most
|cases, by all players). You *could*, but it'd be pretty clumsy, esp.
|since objects get moved around. (Of course, what he's talking about,
|MUSH, is a pretty ugly language anyway....)
Why not? An object's description and properties can be determined by
examining its data structure; objects will have code-valued fields,
for sure, but I should think that they would largely be used for
initialisation and computation of physical interactions, no?
Certainly the lexicon (and ideally the grammar) should be independent
of the game code and sufficiently modular....
So, no, I still don't see any need to do anything this inefficient....
And you CERTAINLY can't use this approach in a roomless world....
BTW, does anyone know why it is traditional to write adventures in the
second person? I personally believe that it is *possible* to write
good 2s prose, but it's certainly a major technical challenge in its
own right!
Felix Lee
I never really meant we should model exact reality; a virtual reality
will do. But I've been thinking about this statement, and I don't
really see why you cannot create a convincing semblance of reality.
Certainly, inferring the taste of a cheese danish starting from QCD is
intractible, but you don't need QCD to eat a danish.
Why can't you model things from the top down rather than from the
bottom up? You don't need to keep track of every leaf in a forest as
long as you can produce leaves on demand. You just need a schema for
forests, trees, and leaves. The leaves don't exist until you look at
them closely. The tree falling in the forest with noone to hear it
doesn't make a sound---it doesn't even exist. But a character might
still stumble across fallen trees if they're part of the forest
schema, and you can back-fill history to when the tree fell if needed.
This is lazy modeling. Model things at the highest level you can get
away with, at the lowest level that matters. GMs for role-playing
games do this sort of thing all the time. They sketch a broad outline
of a scenario and invent specific details as players need or want.
--
Felix Lee fl...@cs.psu.edu
Johan Andersson
>Why not? An object's description and properties can be determined by
>examining its data structure; objects will have code-valued fields,
>for sure, but I should think that they would largely be used for
>initialisation and computation of physical interactions, no?
>
>Certainly the lexicon (and ideally the grammar) should be independent
>of the game code and sufficiently modular....
>
independant of the game code. ONLY the object knows what could be done with
and to it, ONLY the object knows what commands applies to it and what the
semantics of those commands are.
Exporting those characteristics to a central parser would be a severe break
with the OO design of the game. It would also impose unwanted standards and
limitations on the objects. The hole idea with an OO design is that the objects
can be and do ANYTHING.
>So, no, I still don't see any need to do anything this inefficient....
>
Inefficient? This approach is highly adapted for parallell processing. Ideally
you would have all the objects process the command simultaneously and that is
extremely efficient as I see it.
>And you CERTAINLY can't use this approach in a roomless world....
>
Why ever not? Just choose another way than rooms to keep track of what objects
are accessible. Rooms are not a very good criteria anyway.
>BTW, does anyone know why it is traditional to write adventures in the
>second person? I personally believe that it is *possible* to write
>good 2s prose, but it's certainly a major technical challenge in its
>own right!
>
I guess its done this way to get the player as close to the game as possible.
You could have a 'looking over the shoulder' 1s prose but that might distance
the player from the game.
/Johan
--
Johan Andersson | "You don`t have conversations with microprocessors
Chalmers, Sweden | you tell them what to do, and then you helplessly
Email: | watch the disaster when they take you literally."
d8a...@dtek.chalmers.se | Sah`ot in David Brins "Startide Rising"
Stephen P Spackman
|In article <STEPHEN.91...@estragon.uchicago.edu> ste...@estragon.uchicago.edu (Stephen P Spackman) writes:
|>Why not? An object's description and properties can be determined by
|>examining its data structure; objects will have code-valued fields,
|>for sure, but I should think that they would largely be used for
|>initialisation and computation of physical interactions, no?
|>
|>Certainly the lexicon (and ideally the grammar) should be independent
|>of the game code and sufficiently modular....
|>
|This is just the point, in an OO MUD neither the lexicon nor the grammar are
|independant of the game code. ONLY the object knows what could be done with
|and to it, ONLY the object knows what commands applies to it and what the
|semantics of those commands are.
Just as in the real world the word "cat" is inherent to a furry
animate object and has no connection to your mind, I take it. :-)
|Exporting those characteristics to a central parser would be a severe break
|with the OO design of the game. It would also impose unwanted standards and
|limitations on the objects. The hole idea with an OO design is that the objects
|can be and do ANYTHING.
True religion is no substitute for sound design. Philosophy is no
substitute for science. From an engineering standpoint you are IMHO
wrong.
OO is one tool in the arsenal; it cannot be allowed to take over the
whole enterprise (look at the Smalltalk80 system. Would you want to
maintain one? And that was executed by some really GOOD people...).
|>So, no, I still don't see any need to do anything this inefficient....
|>
|Inefficient? This approach is highly adapted for parallell processing. Ideally
|you would have all the objects process the command simultaneously and that is
|extremely efficient as I see it.
And of course this is precisely the kind of hardware we're
implementing on, is it? Cubes with millions of processors? Hm, and I
thought *I* was doing well here with several sparcs at my disposal.
|>And you CERTAINLY can't use this approach in a roomless world....
|>
|Why ever not? Just choose another way than rooms to keep track of what objects
|are accessible. Rooms are not a very good criteria anyway.
The algorithm you described was to ask everything in sight. Unless
you're planning to back down on this, I think I'm right. If you *are*
planning to change your position, what are you changing it to?
Probably you'll end up describing something with a centralised
interaction manager, and a centralised parser/interpreter.... But if
I'm wrong, I'm interested in knowing of alternatives....
Stephen P Spackman
|>Modelling the real world CANNOT BE DONE.
|
|I never really meant we should model exact reality; a virtual reality
|will do. But I've been thinking about this statement, and I don't
|really see why you cannot create a convincing semblance of reality.
|
|Why can't you model things from the top down rather than from the
|bottom up? You don't need to keep track of every leaf in a forest as
|long as you can produce leaves on demand. You just need a schema for
|forests, trees, and leaves. The leaves don't exist until you look at
|them closely. The tree falling in the forest with noone to hear it
|doesn't make a sound---it doesn't even exist. But a character might
|still stumble across fallen trees if they're part of the forest
|schema, and you can back-fill history to when the tree fell if needed.
This is certainly the way to make an excellent game; in fact at this
point I don't think I'd attempt it any other way. But the structure
you get is very different from actual reality, because in actual
reality lots of stuff IS going on in parallel, autonomously. I was
once told by a weather researcher (I don't know if this is literally
true) that the reason long distance weather forecasts are so bad is
that if you walk across the room, five weeks later the air currents
could end up as a hurricane on the other side of the planet... or else
not.
And back-filling history is the hardest single entry on the "things I
want to try but don't know how" list - I personally rate it harder
than free text language interface (though easier to fudge, perhaps).
Randolph Fritz
fiction issue.]
stephen --
Just a brief note -- yes, it is literally true: the air currents your
walk produces may be amplified to become a full-scale storm . . . but
probably won't be. This is the famous butterfly-wing effect --
somewhere, some tiny little disturbance is going to be the next
tropical storm. And you never know which one.
This is called chaotic behavior, and most non-linear systems do it.
Anyone know if there are simulation games that incorporate chaotic
systems?
If you'd like to learn more about chaos, read any of the numerous
books on chaotic systems that have been published in the past few
years; Gleick is pretty good and easy to find. And (related, because
chaotic systems often produce fractal paths and objects) there's
always Mandelbrot.
nd t
ou ui
R Press T __Randolph Fritz sun!cognito.eng!randolph || rand...@eng.sun.com
ou ui Mountain View, California, North America, Earth
nd t
Felix Lee
>literally true) that the reason long distance weather forecasts are
>so bad is that if you walk across the room, five weeks later the air
>currents could end up as a hurricane on the other side of the
>planet... or else not.
Yes, this is almost literally true. Weather is a chaotic system. A
miniscule difference in the state of the system can cause a huge
difference in the future of the system.
This actually makes it easier to generate weather, not harder. Since
chaotic systems are unpredictable by nature, you do not have to create
predictable weather. A suitably constrained random system will
generate plausible weather.
>And back-filling history is the hardest single entry on the "things I
>want to try but don't know how" list
Yes. This could be quite a project. I was thinking it would be
interesting to have a maze game where corridors, objects, and
creatures are only created when you encounter them, but all with a
consistent history. (One of the unanswered questions in NetHack is,
where do all those monsters and objects come from?)
The known maze and the known history form the known space-time
continuum. The known continuum contrains the generation of the
unknown parts.
--
Felix Lee fl...@cs.psu.edu
Johan Andersson
>Just as in the real world the word "cat" is inherent to a furry
>animate object and has no connection to your mind, I take it. :-)
>
Ahh, no. 'cat' is my label on the furry animate object. It is not necessarily
yours or your german friend's. So 'cat' has nothing at all to do with cat :-)
This is not my point at all though, my point here is interaction between
objects, specifically between the 'player'-object, and say the 'cat'-object.
The fact that you can 'pat the cat' or 'kick the cat' is likely dependant
on the state of the two mentioned objects. I still think it would be extremely
complex to export these states to a central parser. It seems much simpler
just to let the two objects decide what can an can't be done at the moment.
>True religion is no substitute for sound design. Philosophy is no
>substitute for science. From an engineering standpoint you are IMHO
>wrong.
>
If you knew all my ugly patches to LPmud, you'd know I'm no fanatic :-)
I still think a central parser is wrong, not only because it would break
an otherwise decentralised OO design, but mostly because the unnecassary
flow of information to and from it. Why must all the objects export all that
is possible to do with them by different other objects, to a central parser,
over and over again as their states changes? That seems very inefficient to me.
>OO is one tool in the arsenal [...]
>
Naturally, please design a VR without OO as a tool. I don't think its possible.
>And of course this is precisely the kind of hardware we're
>implementing on, is it? Cubes with millions of processors? Hm, and I
>thought *I* was doing well here with several sparcs at my disposal.
>
Well we are running 8000+ objects(40 players) on a PC/RT 16Mbyte and we'll be
able to emigrate to parallell hardware with a bit of effort, when that comes
along. If we were doing this commercially, I would have strongly recommended
this type of design, rewriting software can be very expensive.
>The algorithm you described was to ask everything in sight. Unless
>you're planning to back down on this, I think I'm right. If you *are*
>planning to change your position, what are you changing it to?
>
The point here is: What's in 'sight'?
LPmud currently makes an 'ad hoc' assumption that what you carry and
what is around you in the 'room' is in 'sight'. This is not very good but
it is very simple and efficient.
What I mean is that you need some other criteria for deciding what is
in 'sight'. The brute approach is of course to have all objects confer
with eachother to decide which of them is in 'sight' of the other. This is
of course not possible, at least not with the hardware we have today.
>Probably you'll end up describing something with a centralised
>interaction manager, and a centralised parser/interpreter.... But if
>I'm wrong, I'm interested in knowing of alternatives....
>
No, maybe a central something to keep track of what's 'in sight' of what,
but the actual interaction, never. I would prefer some form of distributed
algorithm over network connected objects. I have no easy and simple solution
though, I wish I did.
Stephen P Spackman
|In <STEPHEN.91...@estragon.uchicago.edu> ste...@estragon.uchicago.edu (Stephen P Spackman) writes:
|
|>Just as in the real world the word "cat" is inherent to a furry
|>animate object and has no connection to your mind, I take it. :-)
|>
|Ahh, no. 'cat' is my label on the furry animate object. It is not necessarily
|yours or your german friend's. So 'cat' has nothing at all to do with cat :-)
Quite.
|This is not my point at all though, my point here is interaction between
|objects, specifically between the 'player'-object, and say the 'cat'-object.
|The fact that you can 'pat the cat' or 'kick the cat' is likely dependant
|on the state of the two mentioned objects. I still think it would be extremely
|complex to export these states to a central parser. It seems much simpler
|just to let the two objects decide what can an can't be done at the moment.
I think you are confusing the parser with the world model! The cat
might know that it is KICKABLE but that doesn NOT mean that it should
know the word "kick" - or "cat" for that matter - what it needs to
respond to is the PHYSICAL (not even semantic!)
attack-by-foot(velocity, precision) token!
The parser is concerned with what can and can't be understood.
The pragmatics module is concerned with what can and can't be
intended/attempted.
The physics module is concerned with what will and will not work.
The cat is part of the physics module. Your idea of the cat is part of
the pragmatics module. The word "cat" is part of the parser module,
and in particular is part of the data structure for your character's
use of lanaguge (not part of the cat's).
|I still think a central parser is wrong, not only because it would break
|an otherwise decentralised OO design, but mostly because the unnecassary
|flow of information to and from it. Why must all the objects export all that
|is possible to do with them by different other objects, to a central parser,
|over and over again as their states changes? That seems very inefficient to me.
It works the other way around. It is the PHYSICS module that mediates
most interaction between objects, the parser is only involved in
language use. When you issue a command, it is interpreted, and then
the physics module is invoked. The physics module tracks which objects
could plausibly influence each other at any moment....
|>OO is one tool in the arsenal [...]
|>
|Naturally, please design a VR without OO as a tool. I don't think its possible.
But saying that OO is more important than modularity is insane!
|>And of course this is precisely the kind of hardware we're
|>implementing on, is it? Cubes with millions of processors? Hm, and I
|>thought *I* was doing well here with several sparcs at my disposal.
|>
|Well we are running 8000+ objects(40 players) on a PC/RT 16Mbyte and we'll be
|able to emigrate to parallell hardware with a bit of effort, when that comes
|along. If we were doing this commercially, I would have strongly recommended
|this type of design, rewriting software can be very expensive.
Hm. While I'm working in an environment with a sparc on every desk,
and I'm interested in very different models of parallelism. Ok.
|>The algorithm you described was to ask everything in sight. Unless
|>you're planning to back down on this, I think I'm right. If you *are*
|>planning to change your position, what are you changing it to?
|>
|The point here is: What's in 'sight'?
Determined by the physics module. That's what it's FOR (among other things).
|LPmud currently makes an 'ad hoc' assumption that what you carry and
|what is around you in the 'room' is in 'sight'. This is not very good but
|it is very simple and efficient.
Fails in the absence of rooms, of course.
|What I mean is that you need some other criteria for deciding what is
|in 'sight'. The brute approach is of course to have all objects confer
|with eachother to decide which of them is in 'sight' of the other. This is
|of course not possible, at least not with the hardware we have today.
Which is why it seemed extremely bizarre when (above) you appeared to
be advocating this approach!
|>Probably you'll end up describing something with a centralised
|>interaction manager, and a centralised parser/interpreter.... But if
|>I'm wrong, I'm interested in knowing of alternatives....
|>
|No, maybe a central something to keep track of what's 'in sight' of what,
|but the actual interaction, never. I would prefer some form of distributed
|algorithm over network connected objects. I have no easy and simple solution
|though, I wish I did.
I said "manager", not "evaluator". Fucntional programming goes without
saying for me; I'm not interested in passivce data structures. OF
COURSE objects will have semantic routines attatched to them, in OO
style. But this does NOT mean that you can practically avoid having
explicitly management of locality and causality. Otherwise you'll
never be able to get much beyond that 8000 object scale (myself I'm
thinking, perhaps unrealistically, about 10^28 or so "objects" with
perhaps a gigabyte of state actually instantiated, for a "full size"
game running across several workstations.... And I do NOT plan to
invoke more than 10^3 objects per player per tick!).
With your arrangement, what can you do about scale?
Andrew John Williams
>This is just the point, in an OO MUD neither the lexicon nor the grammar are
>independant of the game code. ONLY the object knows what could be done with
>and to it, ONLY the object knows what commands applies to it and what the
>semantics of those commands are.
Not a good way of doing things... How are we supposed to write decent
NPCs if the only way they can know what they can do with an object is to
try EVERYTHING and see what works?
Actions should be defined separately to objects, in terms of some
suitably general set of primatives, with objects handling the results f
the primatives.
John West (stealing Andrew's account)
Are all fish?
Felix Lee
>connected objects.
I don't see how this is feasible. Who keeps track of time? What
makes objects fall? How do objects collide? Each of these seems hard
to do with autonomous objects alone. You need mediators of some sort.
Collision could be decentralized, but things like gravity and time are
universal and affect all objects at once.
--
Felix Lee fl...@cs.psu.edu
Johan Andersson
>
> d8a...@dtek.chalmers.se (Johan Andersson) writes:
>
> >This is just the point, in an OO MUD neither the lexicon nor the grammar are
> >independant of the game code. ONLY the object knows what could be done with
> >and to it, ONLY the object knows what commands applies to it and what the
> >semantics of those commands are.
>
> Not a good way of doing things... How are we supposed to write decent
> NPCs if the only way they can know what they can do with an object is to
> try EVERYTHING and see what works?
>
Although other people (parents, teachers, friends) tells us what we can
and can't do too. Maybe your NPC's should sit down an talk to each other now
and then, to share information. :-)
Seriously though, my approach would be to preprogram my NPC's knowledgebase to
include a number of standard commands applicable to most objects, like 'get',
'drop', 'eat' and so forth.
> Actions should be defined separately to objects, in terms of some
> suitably general set of primatives, with objects handling the results f
> the primatives.
>
I strongly disagree, why must there be central entitities storing abstract
primitives like 'actions', 'intentions' and the like. There is no such entities
in the 'real world', why do you want to introduce them in a virtual world?
One might want to introduce a central entity keeping track of what is possible
corresponding to the real world's 'laws of nature', but making a large
data base with primitives like 'take_with_hand', 'kick_with_foot',
'insert_in', I just won't buy it.
In a MUD with 200+ people making objects, decentralisation is the key to
making things work. If you introduce central entitites that everyone should
update, the game stops functioning, if you centrally decide the entire action
database, you severly limit the freedom of creation.
Furthermore, I never advocated that the objects should be secretive with what
can be done to them. One object (an NPC) should of course be able to query
another object (a table) what can be done with it, without actually 'trying' to
do it.
In LPmud this is solved by letting the objects export the first word of all
commands that are applicable to it, to all objects that are 'living' and in
the vicinity of the object. Not at all a philosophically neat solution, but it
works surprisingly well.
ste...@estragon.uchicago.edu (Stephen P Spackman) writes:
> The parser is concerned with what can and can't be understood.
> The pragmatics module is concerned with what can and can't be
> intended/attempted.
> The physics module is concerned with what will and will not work.
>
This is definitely philosophically very neat. What worries me is how it is to
be implemented. This approach relies heavily on abstract concepts without
counterparts in the real world. What are intentions? Ok, intentions
can be defined as 'intended actions' but what then are actions?
> I think you are confusing the parser with the world model! The cat
> might know that it is KICKABLE but that doesn NOT mean that it should
> know the word "kick" - or "cat" for that matter - what it needs to
> respond to is the PHYSICAL (not even semantic!)
> attack-by-foot(velocity, precision) token!
>
To me your concept of 'actions' or 'physical tokens', is a long list
of all the possible interactions between objects. When new objects are
introduced they must then have the possibility of adding to that list if they
want to introduce an entirely new form of interaction. Or do you propose to
make the list static and once and for all decide all possible interactions?
Another problem with this approach is, it at least seems so to me, that the
game has to 'understand' a lot of what goes on. It must be capable of, through
a parser, translate commands into intentions and check them against a
pragmatics module. It must then, in cooperation with objects?, manage the
action and the outcome of the action.
LPmud has a much more 'direct' approach, the object driver is really little
more than a C(++) interpreter. There is no highly advanced AI features
involved, it simply lets the objects interact with each other without caring,
trying to mediate or understand what happens.
What this boils down to, I guess, is that I can't make myself believe in your
approach until I see a version of it implemented. I still like many of your
concepts and ideas though, its just that you seem to want to grasp the entire
VR in the moment of creation and I'm very doubtfull about that. A VR must
IMHO evolve gradually, probably into something that we can not grasp today.
Therefore it must be designed with evolution in mind, not as a fulfilled
creation.
Terrence M McNamara
I have been working on paper at designing such a beast. Unfortunately,
my graphics work is still in the learning stages, and I have never
programmed for multiuser systems. My approach assumes modem communications
between two computers.
Here are the generals for what I've come up with:
Computer 1: (preferably the fastest of all the machines)
Time share two seperate processes. The first is the game controller.
On each "turn" it receives updates of information from both (or
presumably all) machines. It then resolves any and all conflicts.
If the game is a combat one, this would mean who has moved, who has
been hit, what the new scores are, etc. If the game is a speed game,
something like Qix is what I have been thinking about, decide who
has moved and affect the playing board appropriately. Then release
a packet of information containing this information in some simple
format. This packet is then sent to the second process, and all other
machines.
The second process simply corrects the output based on
the packet of information received from the first process and returns
a packet of information identifying itself and informing the first
process of any new moves. It should be fairly easy to handle the
graphics for this single program with a sprite-type package that would
resolve collisions.
Computer 2 through Computer n:
Run the program being used as process two above.
I am just a novice. What do the experts think on this one?
Les Hill
|> In article <m$4Ho...@cs.psu.edu>, fl...@cs.psu.edu (Felix Lee) writes...
|> >>I would prefer some form of distributed algorithm over network
|> >>connected objects.
|> >I don't see how this is feasible. Who keeps track of time? What
|> >makes objects fall? How do objects collide? Each of these seems hard
|> >to do with autonomous objects alone. You need mediators of some sort.
|> >Collision could be decentralized, but things like gravity and time are
|> >universal and affect all objects at once.
...deleted stuff here...
|> programmed for multiuser systems. My approach assumes modem communications
|> between two computers.
|> Here are the generals for what I've come up with:
|> Computer 1: (preferably the fastest of all the machines)
|> Time share two seperate processes. The first is the game controller.
|> On each "turn" it receives updates of information from both (or
|> presumably all) machines. It then resolves any and all conflicts.
|> If the game is a combat one, this would mean who has moved, who has
|> been hit, what the new scores are, etc. If the game is a speed game,
|> something like Qix is what I have been thinking about, decide who
|> has moved and affect the playing board appropriately. Then release
|> a packet of information containing this information in some simple
|> format. This packet is then sent to the second process, and all other
|> machines.
|> The second process simply corrects the output based on
|> the packet of information received from the first process and returns
|> a packet of information identifying itself and informing the first
|> process of any new moves. It should be fairly easy to handle the
|> graphics for this single program with a sprite-type package that would
|> resolve collisions.
|> Computer 2 through Computer n:
|> Run the program being used as process two above.
|> I am just a novice. What do the experts think on this one?
What you have described above is called the "client-server" model and is
in use WIDELY for multi-player internet games (MUDs, xtank, empires, et al.)
A different approach is what I call the "distributed-server" model; at the moment
I have a socket library (99% finished :) that implements such a model for
connection management -- the major drawback is that I have introduced a protocol
layer between the application and the socket (and terminal :)
The basic idea behind the "distrubuted-server" is that at any moment ANY "client"
can become the next "server" (while still being a "client".) This eliminates
single points of failure and static addressing problems.
Les
--
Extraordinary crimes against the people and the state have to be avenged by
agents extraordinary. Two such people are John Steed -- top professional, and
his partner, Emma Peel -- talented amateur; otherwise known as "The Avengers."
INTERNET: l...@ufl.edu UUCP: ...!gatech!uflorida!leh BITNET: vishnu@UFPINE
Frobozz
>Here are the generals for what I've come up with:
>Computer 1: (preferably the fastest of all the machines)
>Time share two seperate processes. The first is the game controller.
>On each "turn" it receives updates of information from both (or
>presumably all) machines. It then resolves any and all conflicts.
>If the game is a combat one, this would mean who has moved, who has
>been hit, what the new scores are, etc. If the game is a speed game,
>something like Qix is what I have been thinking about, decide who
>has moved and affect the playing board appropriately. Then release
>a packet of information containing this information in some simple
>format. This packet is then sent to the second process, and all other
>machines.
The presence of this process stops the game from being distributed. This
process is the sole moderator of the entire game. Your second processes just
sit there displaying the information given to them by the first. You
might as well make the seconds really dumb display daemons and let the
first do everything.
To create a distributed system, it would be better to have every machine
running a single program and these programs cooperate to achieve whatever
goals they are supposed to. This has all kinds of advantages over the above
case, if a host crashes (for any reason), the rest of the system need only
be minimally disturbed. The amount of processing available in a system of
this kind is far greater than any single host could be (thus your virtual
reality could be more complicated).
I've got a few ideas about how to write a distributed mud, but I suspect
that even that would be aproaching the too difficut area.
Pauli
seeya
Paul Dale | Internet/CSnet: gr...@cs.uq.oz.au
Dept of Computer Science| Bitnet: grue%cs.uq...@uunet.uu.net
Uni of Qld | JANET: grue%cs.uq...@uk.ac.ukc
Australia, 4072 | EAN: gr...@cs.uq.oz
| UUCP: uunet!munnari!cs.uq.oz!grue
f4e6g4Qh4++ | JUNET: gr...@cs.uq.oz.au
--
Felix Lee
>possible corresponding to the real world's 'laws of nature', but
>making a large data base with primitives like 'take_with_hand',
>'kick_with_foot', 'insert_in', I just won't buy it.
Well, knowledge-representation people believe that nearly every action
can be represented by a small number of primitives, like "ptrans",
physical transfer, which represents any sort of motion. But anyway.
What happens when I throw a ball? If the ball is modelling its own
motion, how does it know when it hits something?
The basic problem is, given a location (x,y,z,t), how do you determine
what object occupies that location if the universe is distributed and
all objects are autonomous?
Querying every object in the universe is expensive. I don't see how
you can avoid having a space-time mediator. The mediator knows the
position and motion of every object in the universe.
If you don't like the idea of a central space-time mediator, then you
might slice the universe into pieces. Have several mediators, each
responsible for a sector of the universe. Each sector is responsible
for modeling position and motion of objects within it.
Every sector should be functionally identical (since they're all
modeling the same universe). Every sector has to know its neighbors.
Every motion of an object has to be mediated by every sector that it
moves in. So dividing the universe into sectors is useful only if
actions are mostly confined to one sector.
Okay. This is fine, if perhaps a little heavy on the message-passing.
So now, how do you keep things synchronized? Presumably, every sector
keeps track of its own time, so you only need to synchronize a sector
with adjacent sectors. This is somewhat complex. A sector cannot
advance its clock to time t1 until it knows that its neighbors will
not give it any events that occur before t1. How does it find this
out? I have no idea. (One alternative is to advance the clock
regardless, and revise history when past events catch up with you.
This has strange consequences for the user interface.)
How do you deal with field effects? Gravity is a field effect. This
is easy enough if you let each sector model gravity on its own. Well,
this works only if the gravitational force exerted by objects is
negligible. You run into problems if you have objects on the
planetary scale.
And light is a field effect. Every light source can potentially
illuminate the entire universe. Unless sectors are walled off from
each other, every sector has to pass its light sources to all its
neighbors. This violates the locality principle and argues for large
sectors, perhaps a single central mediator.
--
Felix Lee fl...@cs.psu.edu
Joseph Allen
>I never really meant we should model exact reality; a virtual reality
>will do. But I've been thinking about this statement, and I don't
>really see why you cannot create a convincing semblance of reality.
>Certainly, inferring the taste of a cheese danish starting from QCD is
>intractible, but you don't need QCD to eat a danish.
>Why can't you model things from the top down rather than from the
>bottom up? You don't need to keep track of every leaf in a forest as
>long as you can produce leaves on demand. You just need a schema for
>forests, trees, and leaves. The leaves don't exist until you look at
>them closely. The tree falling in the forest with noone to hear it
>doesn't make a sound---it doesn't even exist. But a character might
>still stumble across fallen trees if they're part of the forest
>schema, and you can back-fill history to when the tree fell if needed.
Hell, _you_ don't even exist. An instant of your mind and life were created
so that you could exist for the few moments necessary to compose your news
article. Then when you were no longer needed for my entertainment, you were
swapped out to make space for new things. This reply will, of course, swap you
back in for a few moments.
>This is lazy modeling. Model things at the highest level you can get
>away with, at the lowest level that matters. GMs for role-playing
>games do this sort of thing all the time. They sketch a broad outline
>of a scenario and invent specific details as players need or want.
God must have been very busy this century. Inventing all that weird
physics...
The one problem is that you have to store things that were created so that
when you go back to them they're still the way they were when you left them.
(However, a lot of times you can just store the seed value for the generating
function at some specific point + whatever differences the real player
introduced)
--
/* jal...@ic.sunysb.edu */ /* Amazing */ /* Joe Allen 129.49.12.74 */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
Johan Andersson
>
>What happens when I throw a ball? If the ball is modelling its own
>motion, how does it know when it hits something?
>
>The basic problem is, given a location (x,y,z,t), how do you determine
>what object occupies that location if the universe is distributed and
>all objects are autonomous?
>
network connected objects. My idea was to let the network be the space model.
Objects in motion would then move in the network as their spatial relations
to other objects changes. If objectA and objectB is connected and we introduce
objectC between them so that they are hidden from each other, then the A-B
connection is lost and replaced by an A-C-B connection. There would be no
fixed frame (x,y,z,t) coordinates, only relative coordinates to other objects.
>
>If you don't like the idea of a central space-time mediator, then you
>might slice the universe into pieces. Have several mediators, each
>responsible for a sector of the universe. Each sector is responsible
>for modeling position and motion of objects within it.
>
I wouldn't cut it in arbitrary pieces like this. What I'd like to do is to let
some objects have an 'internal space'. This space would keep its own object
network separated from the network outside the 'container' object. The point
here would be that not all the objects in this space would have to be
connected to the 'container' object, only those on the border.
This is of course all theories, I have implemented nothing of this which makes
it somewhat speculative to argue for. I prefer advocating things I have
actually implemented, tested and that I know works.
>So now, how do you keep things synchronized? [....]
>How do you deal with field effects? Gravity is a field effect. [....]
>And light is a field effect. [....]
>
Hmmm, time, gravity, light, general force fields. We're talking 'action at a
distance' here. Some would say AAD simply doesn't exist so we could ignore it,
I'll be damned if I have to model single photons, quarks and gluons though :)
What I'm trying to say is that we could assume field effects to be macro world
manifestations of micro (quantum) world none field effects. We will however
on every scale we model, need macro world simplifications of the underlying
micro world. The question then reduces to: Can we keep the distributed model
when introducing these simplifications?
I believe we can, as long as we need not model a universe where the speed of
light is infinite. I see no reason why it wouldn't be possible to send force
field vector messages through the object network.
Time might be different though, do you know what time IS? I don't, so I have
no good ideas on how to model it. A central concept of time is my only answer,
I don't like it but I have nothing better to offer.
Richard Newsome
>I was
>once told by a weather researcher (I don't know if this is literally
>true) that the reason long distance weather forecasts are so bad is
>that if you walk across the room, five weeks later the air currents
>could end up as a hurricane on the other side of the planet... or else
>not.
Hmmm...I'm going to think twice before I do any unnecessary walking across
the room...
I have a weather researcher friend who tells me that the accuracy of weather
forecasting improved enormously when they broke the model up into tinier pieces
and introduced discrete event modelling, rather than assuming that everything
is fungible and homogeneous. For example, the droplets in a cloud are now
assigned varying sizes and shapes, rather than treating them as identical
globular drops, uniformly distributed.
rON.
>Hmmm...I'm going to think twice before I do any unnecessary walking across
>the room...
The 'walking across the room' thing is known as the 'butterfly effect'-
the original model was of a butterfly in China affecting weather patterns
in the US. The whole basis of the model is fractals and chaos- A gentleman
named Lorenz was doing weather based sinulation and discovered that even
an infinitely small change in the initial conditions presented would change
the overall weather patterns. Granted, it might take a long period of
time before those changes were recognized, but changes would occur. THe
model of this is the Lorenz Attractor, also known as the Lorenz BUtterfly.
Followup redirected to alt.fractals.
rON. (blow...@triton.unm.edu!ariel.unm.edu)
"It is only with the heart that one see rightly;
what is essential is invisible to the eye."