path-finding
Jacek Pudlo
There is a hallway to the south.
>s
HALLWAY
There is a living room to the west and a bathroom the north.
>w
LIVING ROOM
There is hallway to the east and a kitchen to the west.
>w
KITCHEN
The only exit is to the east.
You see a bowl of plums.
>eat plums
Yummie yummie in my tummie!
You suddenly feel an urge to go to the bathroom.
>go bathroom
You see no bathroom here.
Oops, it's too late!
---------------------------------------------------
Wouldn't it be neat if one could simply type "go <any known location>" and
the game would try to find the shortest path to that location? After all,
finding an allready known location is a rather tedious and mechanical task
that could be just as well acomplished by the computer instead of burdening
the player. Has this been implemented in any IF-game you know of? Is it
possible to write a path-finding alg in any of the major IF-languages? Has
this been done? Is there some kind of library extension that could deal with
that? Is it only I who find the lack of path-finding abilities in most
(all?) IF-games annoying?
Magnus Olsson
Jacek Pudlo <pudlo...@hotmail.com> wrote:
>Wouldn't it be neat if one could simply type "go <any known location>" and
>the game would try to find the shortest path to that location? After all,
>finding an allready known location is a rather tedious and mechanical task
>that could be just as well acomplished by the computer instead of burdening
>the player. Has this been implemented in any IF-game you know of?
There are IF games where you can just, e.g., "go to bathroom" and the
game will take you theren, but I don't know if this is done by
actually searching for a path or if the game "cheats" and just moves
you there.
>Is it
>possible to write a path-finding alg in any of the major IF-languages?
Yes. There's one problem, though: the algorithm must be able to find
all the exits from any room, and where they will take you. This is not
always trivial; for example, going north may run a routine that checks
what you're carrying, only lets you through if you're carrying a live
chicekn, and then it will randomly take you to one of five different
destinations. If anohter room (which you will have to pass through
earlier) has the annoying property that entering it will kill all
poultry carried on your person, things are getting a bit complicated
:-).
But provided every room has a fixed list of exits, there exist a
number of path-finding algorithms - check any computer scienec
textbook. Handling the simpler cases of exit routines (such as locked
doors) shouldn't be too complicated - it's when you get to cases like
the chicken-sensitive door above that you run into trouble.
>Is it only I who find the lack of path-finding abilities in most
>(all?) IF-games annoying?
No.
--
Magnus Olsson (m...@df.lth.se, m...@pobox.com)
------ http://www.pobox.com/~mol ------
Jacek Pudlo
Magnus Olsson <m...@pobox.com> skrev i
diskussionsgruppsmeddelandet:8vjodv$t$1...@news.lth.se...
> In article <EMcT5.132$O%.24847@newsc.telia.net>,
> Jacek Pudlo <pudlo...@hotmail.com> wrote:
> >Wouldn't it be neat if one could simply type "go <any known location>"
and
> >the game would try to find the shortest path to that location? After all,
> >finding an allready known location is a rather tedious and mechanical
task
> >that could be just as well acomplished by the computer instead of
burdening
> >the player. Has this been implemented in any IF-game you know of?
>
> There are IF games where you can just, e.g., "go to bathroom" and the
> game will take you theren, but I don't know if this is done by
> actually searching for a path or if the game "cheats" and just moves
> you there.
It should be fairly easy to separate the wheat from the 'cheat'. The games
that implement 'true' path-finding could display the route;
KITCHEN
->go bathroom
LIVING ROOM
HALLWAY
BATHROOM
You arrived safely at the bathroom.
> >Is it
> >possible to write a path-finding alg in any of the major IF-languages?
>
> Yes. There's one problem, though: the algorithm must be able to find
> all the exits from any room, and where they will take you. This is not
> always trivial; for example, going north may run a routine that checks
> what you're carrying, only lets you through if you're carrying a live
> chicekn, and then it will randomly take you to one of five different
> destinations. If anohter room (which you will have to pass through
> earlier) has the annoying property that entering it will kill all
> poultry carried on your person, things are getting a bit complicated
> :-).
Let's say the path-finding function generates a NULL-terminated string (of
characters/bytes) describing the shortest way to the location. The string is
then 'fed' to the parser. Typing "go bathroom" would be equivalent to typing
"go living room then go hallway then go bathroom" or "e,e,n" (which most
present-day parsers can handle). Should anything unexpected happen (like an
obstacle that wasn't there before) the command line is interrupted.
Another problem is the fact that only paths that are known to the
player/protagonist should be taken into account. If there is a short cut
through a secret door that is unknown to the player/protagonist that short
cut must be ignored by the path-finding function.
Yet another problem is teleportation. I have no idea how to solve that one.
Magnus Olsson
Jacek Pudlo <pudlo...@hotmail.com> wrote:
>
>Magnus Olsson <m...@pobox.com> skrev i
>diskussionsgruppsmeddelandet:8vjodv$t$1...@news.lth.se...
>> game will take you theren, but I don't know if this is done by
>> actually searching for a path or if the game "cheats" and just moves
>> you there.
>
>It should be fairly easy to separate the wheat from the 'cheat'. The games
>that implement 'true' path-finding could display the route;
>
>KITCHEN
>->go bathroom
>
>LIVING ROOM
>HALLWAY
>BATHROOM
>You arrived safely at the bathroom.
They *could* display the route, yes, but what if they don't? Or
what if the "cheat" actually is a table of the shortest routes between
all possible pairs of rooms?
>> Yes. There's one problem, though: the algorithm must be able to find
>> all the exits from any room, and where they will take you. This is not
>> always trivial; for example, going north may run a routine that checks
>> what you're carrying, only lets you through if you're carrying a live
>> chicekn, and then it will randomly take you to one of five different
>> destinations. If anohter room (which you will have to pass through
>> earlier) has the annoying property that entering it will kill all
>> poultry carried on your person, things are getting a bit complicated
>> :-).
>
>Let's say the path-finding function generates a NULL-terminated string (of
>characters/bytes) describing the shortest way to the location. The string is
>then 'fed' to the parser. Typing "go bathroom" would be equivalent to typing
>"go living room then go hallway then go bathroom" or "e,e,n" (which most
>present-day parsers can handle). Should anything unexpected happen (like an
>obstacle that wasn't there before) the command line is interrupted.
I don't know if this has anything to do with what I wrote above; what
you're describing is what the game does *after* it has found the route,
while I was discusssing the problems of finding it.
>Another problem is the fact that only paths that are known to the
>player/protagonist should be taken into account. If there is a short cut
>through a secret door that is unknown to the player/protagonist that short
>cut must be ignored by the path-finding function.
That doesn't make the problem any harder; you just have to keep track
of whether the player knows about the exit or not, and check if he/she
does, in addition to checking if he/she is carrying the magic chicekn
or whatever.
>Yet another problem is teleportation. I have no idea how to solve that one.
Depends on how you want teleportation to work. If the player can
teleport at will the entire problem is trivial :-). But most
teleportation I've seen in IF seems to work just like doors.
Adam Atkinson
>Wouldn't it be neat if one could simply type "go <any known location>" and
>the game would try to find the shortest path to that location?
Colossal Cave's documentation suggests you can do this there, though
I'm not sure I ever really used this when playing it.
--
Adam Atkinson (gh...@mistral.co.uk)
In the new approach, as you know, the important thing is to understand
what you're doing, rather than to get the right answer. (T. Lehrer)
Gunther Schmidl
(spoilers)
When Jones carries you towards the Dagon, he uses pathfinding to get there.
I used the excellent moveclass.h, available on a IF-Archive near you.
Jacek Pudlo
> In article <kcfT5.168$O%.29652@newsc.telia.net>,
> Jacek Pudlo <pudlo...@hotmail.com> wrote:
> >
> >Magnus Olsson <m...@pobox.com> skrev i
> >diskussionsgruppsmeddelandet:8vjodv$t$1...@news.lth.se...
> >> There are IF games where you can just, e.g., "go to bathroom" and the
> >> game will take you theren, but I don't know if this is done by
> >> actually searching for a path or if the game "cheats" and just moves
> >> you there.
> >
> >It should be fairly easy to separate the wheat from the 'cheat'. The
games
> >that implement 'true' path-finding could display the route;
> >
> >KITCHEN
> >->go bathroom
> >
> >LIVING ROOM
> >HALLWAY
> >BATHROOM
> >You arrived safely at the bathroom.
>
> They *could* display the route, yes, but what if they don't? Or
> what if the "cheat" actually is a table of the shortest routes between
> all possible pairs of rooms?
How was the table generated? By hand? That's an awfull lot of work (100
rooms = 10.000 paths, if I'm not mistaken).
> >> Yes. There's one problem, though: the algorithm must be able to find
> >> all the exits from any room, and where they will take you. This is not
> >> always trivial; for example, going north may run a routine that checks
> >> what you're carrying, only lets you through if you're carrying a live
> >> chicekn, and then it will randomly take you to one of five different
> >> destinations. If anohter room (which you will have to pass through
> >> earlier) has the annoying property that entering it will kill all
> >> poultry carried on your person, things are getting a bit complicated
> >> :-).
> >
> >Let's say the path-finding function generates a NULL-terminated string
(of
> >characters/bytes) describing the shortest way to the location. The string
is
> >then 'fed' to the parser. Typing "go bathroom" would be equivalent to
typing
> >"go living room then go hallway then go bathroom" or "e,e,n" (which most
> >present-day parsers can handle). Should anything unexpected happen (like
an
> >obstacle that wasn't there before) the command line is interrupted.
>
> I don't know if this has anything to do with what I wrote above; what
> you're describing is what the game does *after* it has found the route,
> while I was discusssing the problems of finding it.
It means that we should let the parser/game and not the path-finding routine
decide whether the player can enter a location carrying poultry or not. The
path generated by the path-finding routine should be considered as merely a
suggestion. The actual checking of whether this suggestion can be executed
or not should be done in 'real-time'.
KITCHEN
->get chicken
Taken.
->go bathroom
LIVING ROOM
HALLWAY
Upon entering the hallway the chicken suddenly deseased!
You may not enter the bathroom without the chicken!
It's hardly fair to expect a path-finding routine to take account of magical
chickens.
> >Another problem is the fact that only paths that are known to the
> >player/protagonist should be taken into account. If there is a short cut
> >through a secret door that is unknown to the player/protagonist that
short
> >cut must be ignored by the path-finding function.
>
> That doesn't make the problem any harder; you just have to keep track
> of whether the player knows about the exit or not, and check if he/she
> does, in addition to checking if he/she is carrying the magic chicekn
> or whatever.
What if I'm using the path-finding routine to move all the other characters
in the game? Would that mean that every character has got to have
his/hers/its own distinctive map where all the known location are 'checked'?
Robb Sherwin
<pudlo...@hotmail.com> wrote:
>Wouldn't it be neat if one could simply type "go <any known location>" and
>finding an allready known location is a rather tedious and mechanical task
>that could be just as well acomplished by the computer instead of burdening
>the player. Has this been implemented in any IF-game you know of?
Knight Orc, by Level 9, worked that way. I think a lot of their games
had that feature. Although it was usually used to go get an item as
opposed to go to a specific location because many of the rooms had
the same name,
I think there's code that does something like that in Inform on the
archive....?
Robb
Is it
>possible to write a path-finding alg in any of the major IF-languages? Has
>this been done? Is there some kind of library extension that could deal with
>that? Is it only I who find the lack of path-finding abilities in most
>(all?) IF-games annoying?
>
>
>
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Robb Sherwin, Fort Collins CO
Reviews From Trotting Krips: http://ifiction.tsx.org
Knight Orc Home Page: www.geocities.com/~knightorc
Campbell Wild
> Wouldn't it be neat if one could simply type "go <any known location>" and
> the game would try to find the shortest path to that location? After all,
> finding an allready known location is a rather tedious and mechanical task
> that could be just as well acomplished by the computer instead of burdening
> the player. Has this been implemented in any IF-game you know of? Is it
> possible to write a path-finding alg in any of the major IF-languages?
This feature is built into ADRIFT. It basically finds the shortest route based
on a depth-first-search, taking blocked routes into account.
> Has
> this been done? Is there some kind of library extension that could deal with
> that? Is it only I who find the lack of path-finding abilities in most
> (all?) IF-games annoying?
Campbell
Magnus Olsson
Jacek Pudlo <pudlo...@hotmail.com> wrote:
>
>Magnus Olsson <m...@pobox.com> skrev i
>diskussionsgruppsmeddelandet:8vk340$2j1$1...@news.lth.se...
>> In article <kcfT5.168$O%.29652@newsc.telia.net>,
>> Jacek Pudlo <pudlo...@hotmail.com> wrote:
>> >It should be fairly easy to separate the wheat from the 'cheat'. The
>games
>> >that implement 'true' path-finding could display the route;
>> >
>> >KITCHEN
>> >->go bathroom
>> >
>> >LIVING ROOM
>> >HALLWAY
>> >BATHROOM
>> >You arrived safely at the bathroom.
>>
>> They *could* display the route, yes, but what if they don't? Or
>> what if the "cheat" actually is a table of the shortest routes between
>> all possible pairs of rooms?
>
>How was the table generated? By hand? That's an awfull lot of work (100
>rooms = 10.000 paths, if I'm not mistaken).
Yep. Perhaps the author simply had too much free time :-).
Seriously, most games are much smaller than that, and my point is
that you can never *know* just by playing the game.
>It means that we should let the parser/game and not the path-finding routine
>decide whether the player can enter a location carrying poultry or not. The
>path generated by the path-finding routine should be considered as merely a
>suggestion. The actual checking of whether this suggestion can be executed
>or not should be done in 'real-time'.
(...)
>It's hardly fair to expect a path-finding routine to take account of magical
>chickens.
Fair enough, as long as this is documented. In cases like the chicken
dying because the game choose the wrong path for you, I think the player
should have some way of aborting the path.
> go to diamond room
Okey-dokey.
>>North [game-generated direction]
Mine entrance.
>>North
Dark tunnel. There's a faint smell of gas on the air.
["Oh no, it's walking towards the gas-filled rooms, and I haven't put
out the torch"]
ctrl-C ctrl-Break stop $$ABEND break quit
stopisaidstopdamnitcantyouhearme
>>North
Dark room. The smell of gas is almost overpowering here. Unfortunately,
you're carrying a burning torch...
>>> KABOOM <<<
*** You have died ***
>> That doesn't make the problem any harder; you just have to keep track
>> of whether the player knows about the exit or not, and check if he/she
>> does, in addition to checking if he/she is carrying the magic chicekn
>> or whatever.
>
>What if I'm using the path-finding routine to move all the other characters
>in the game? Would that mean that every character has got to have
>his/hers/its own distinctive map where all the known location are 'checked'?
In principle, yes. I think it would be simpler to have just one map and,
in effect, put different kinds of checkmarks on each exit depending on
who's seen it. That is, each exit could have an array of flags, one flag
for each character.
Magnus Olsson
>>the game would try to find the shortest path to that location?
>
>I'm not sure I ever really used this when playing it.
Yes. IIRC, the way it's implemented
is that there are a number of special verbs like "bathroom" (if there
had been a bathroom in the game; I'm not sure there isn't a version that
has one) that simply move you to the bathroom if a number of conditions
are met (you must have been there before, there must not be any obvious
obstacles in the way - but the latter condition is very easy to check
in Colossal Cave where there are very few obstacles that appear after
you've travelled past their location, so no pathfinding is necessary).
The trouble with this is, again IIRC, that it only works for *some*
rooms. The effect is that many players are puzzled about "undocumented
magic teleportation words similar to xyzzy". This is a design problem:
the game's interface doesn't distinguish sufficiently between the true
magic teleportation words, like "xyzzy", which really are supposed to
be magic (and which work in a subtly different way from the "bathroom"
class of words) and simple shortcuts through the cave.
Magnus Olsson
Campbell Wild <camp...@adrift.NOSPAMorg.uk> wrote:
>[snip]
>
>> Wouldn't it be neat if one could simply type "go <any known location>" and
>> finding an allready known location is a rather tedious and mechanical task
>> that could be just as well acomplished by the computer instead of burdening
>> the player. Has this been implemented in any IF-game you know of? Is it
>> possible to write a path-finding alg in any of the major IF-languages?
>
>This feature is built into ADRIFT. It basically finds the shortest route based
>on a depth-first-search, taking blocked routes into account.
How does it handle the cases with side-effects, like my examples with
magic chickens and lit torches in gas-filled rooms?
Campbell Wild
> magic chickens and lit torches in gas-filled rooms?
It would take them as it finds them.
Basically it calculates the route before setting off, then evaluates each step one
at a time. If you got blown up halfway, then that would end your game.
A random route would probably confuse it, and it would attempt to continue the rest
of the original route. To get around this, you'd have to re-evaluate the route at
every step, which in essence would mean it wouldn't necessarily be the shortest
route. One would expect players to move one step at a time if there was such an
exit, then "goto" rooms once they were past the problematic door.
Campbell
Jon Ingold
>Is there some kind of library extension that could deal with
>that?
Depending on the design of your map it can be quite easy to hardcode
pathfinding routes. For example, say you had a set-up which can be distorted
and stretched to make a spine which branches either side, ie.
Prow
|
Bridge - Balcony
|
Locker - Stairwell - Upstairs Bedroom - Bathroom
|
Stern
(that's going to look kinda scummy in some newsreaders, I'm afraid)
..then pathfinding is easy. You move the player/NPC firstly towards the main
spine (stopping if he reaches his require destination room), then up to the
correct vertical level of the destination, then across. And you can code all
that really easily by just giving each room two coordinates: x and y. So in
the example above, give the Prow (1,0); Balcony (2,1); Locker (0,2),
Bathroom (3,2) and so forth. And it's not that inflexible - it doesn't
matter that the connection from Stairwell to Bedroom is up, or if Bridge to
balcony is northwest, and using a bit of cunning you can extend it to way
more complicated maps.
However, it does mean you'll have to design everything with a little more
thought.
Jon
Paul O'Brian
> Wouldn't it be neat if one could simply type "go <any known location>" and
> the game would try to find the shortest path to that location?
> Has this been implemented in any IF-game you know of?
Try Dangerous Curves.
--
Paul O'Brian obr...@colorado.edu http://ucsu.colorado.edu/~obrian
SPAG #23 will be devoted to the 2000 IF competition, and is actively
seeking reviews! Submit your comp reviews to me by December 5. Thanks!
Jacek Pudlo
Paul O'Brian <obr...@ucsu.colorado.edu> skrev i
diskussionsgruppsmeddelandet:Pine.GSO.3.96.1001125104128.8876A-100000@ucsu.c
olorado.edu...
> On Thu, 23 Nov 2000, Jacek Pudlo wrote:
>
> > Wouldn't it be neat if one could simply type "go <any known location>"
and
> > the game would try to find the shortest path to that location?
> > Has this been implemented in any IF-game you know of?
>
> Try Dangerous Curves.
Where can I get it?
Paul O'Brian
> Paul O'Brian <obr...@ucsu.colorado.edu> skrev i
> diskussionsgruppsmeddelandet:Pine.GSO.3.96.1001125104128.8876A-100000@ucsu.c
> olorado.edu...
> >
> > Try Dangerous Curves.
>
> Where can I get it?
Like most IF, it's available at the GMD IF archive.
ftp://ftp.gmd.de/if-archive/games/zcode/curves.z8
MFischer5
>> On Thu, 23 Nov 2000, Jacek Pudlo wrote:
>> > Wouldn't it be neat if one could simply type "go <any known location>"
>and
>> > the game would try to find the shortest path to that location?
>> > Has this been implemented in any IF-game you know of?
>>
>> Try Dangerous Curves.
FWIW (as AOL doesn't show Irene having answered this), Dangerous Curves doesn't
"compute" the shortest path - it doesn't use an algorithm.
I believe we've try to explain it a time or two so you could check Deja for
specifics (I'd search for GO TO ROOM, or possibly GO TO LOCATION).
Kathleen
--
-- Masquerade - http://baf.wurb.com/if/competition00/inform/mask/
-- The Cove - Best of Landscape, Interactive Fiction Art Show 2000
-- ftp://ftp.gmd.de/if-archive/games/zcode/Cove.z5
-- Excuse me while I dance a little jig of despair
Daniel Barkalow
for the player and for NPCs. It actually uses dijkstra's algorithm (iirc),
and doesn't use any connections which are not either a doorway or a direct
connection. The path is stored in the character, and the character follows
it on subsequent turns until they arrive or something interesting happens.
Of course, platypus does a lot of things somewhat differently, so it would
probably be impossible to switch to it mid-project.
-Iabervon
*This .sig unintentionally changed*
GoddoG
>Wouldn't it be neat if one could simply type "go <any known location>" and
>the game would try to find the shortest path to that location? After all,
>finding an allready known location is a rather tedious and mechanical task
>that could be just as well acomplished by the computer instead of burdening
>the player. Has this been implemented in any IF-game you know of? Is it
>possible to write a path-finding alg in any of the major IF-languages? Has
>this been done? Is there some kind of library extension that could deal with
>that? Is it only I who find the lack of path-finding abilities in most
>(all?) IF-games annoying?
My server's been a bit flakey on getting all the messages
lately, so maybe someone has already mentioned this, but I haven't
seen it.
For TADS there is a GOTO.T module available at the IF
Archive's TADS progamming examples section which "allows a player to
walk directly to any room that (s)he has already seen and that can be
reached without special actions" by Lars Joedal.
ftp://ftp.gmd.de/if-archive/programming/tads/examples/
Toni Arnold
(using breath-first search) at:
ftp://ftp.gmd.de/if-archive/programming/inform6/library/contributions/goto.zip
In the archive there is an additional perl script which adds the needed name
properties to the room objects.
ical...@my-deja.com
> >> > Wouldn't it be neat if one could simply type "go <any known
> >> > location>" and
> >> > the game would try to find the shortest path to that location?
> >>
>
> FWIW (as AOL doesn't show Irene having answered this), Dangerous
> Curves doesn't "compute" the shortest path - it doesn't use an
> algorithm.
>
> I believe we've try to explain it a time or two so you could check
> Deja for specifics (I'd search for GO TO ROOM, or possibly GO TO
> LOCATION).
Sorry, Deja's been down, so I just now saw this thread. Kathleen
is correct when she says DC doesn't compute the shortest path (or
any path). Also, it moves the player character one location at a
time. Example:
-----
>GO TO LIBRARY
Lobby
You head for the public library.
>AGAIN
Northwest Corner of Main and First
You make your way toward the public library.
>AGAIN
Outside the Library
You arrive at the public library.
-----
This allows for the player to interrupt his or her travel if
something important happens in a location. It does require the
player to type AGAIN or G over and over, but I thought it was
a reasonable compromise.
irene
Sent via Deja.com http://www.deja.com/
Before you buy.
Gabe McKean
>For Inform I wrote a library extension which does more or less the job you
want,
>(using breath-first search)
Breath-first search? Does that mean you have to have 'smell' implemented
for all your rooms for it to work? ;)