Avoiding cycles in nested containers?

Technical Development
1

Suppose you’re holding a red cup with a blue cup inside.

player has "red cup"
"blue cup" is in "red cup"

Then you put the red cup in the blue cup.

"blue cup" is in "red cup"
"red cup" is in "blue cup"

Whoops, our cups disappeared – they’ve become disconnected from the rest of the scene graph.

How are cycles like this typically avoided? I suppose it would be easy enough to walk through a container’s outer containers and make sure the thing we’re putting into it isn’t one of them, but then what? A message explaining why you can’t do that?

What I’m tempted to do here is, disallow putting things in portable containers when the container isn’t held (so issue an implicit “take blue cup” first). This avoids the issue of having to traverse the scene graph or deny an action which might seem reasonable to the player. But I’m worried that’s too restrictive – for example a puzzle where you’re supposed to put something on a table and then put something else inside of it.

Any thoughts on this?

2

The classic method (or at least, what Inform 6 does, if I remember right) is to store objects as a forest so each object has only a single parent. Before adding a new edge to the tree—for any reason, not just due to player action, but in your MoveObject subroutine or whatever—you start at the intended parent and walk up the tree until you reach the root; if you come across the intended child at any point, the new edge can’t be added.

(When this happens as a result of a player action, an error message seems reasonable enough: “you can’t put the X in the Y while the Y is in the X!” or the like.)

Notably, Infocom did not actually implement a solution to this in the lowest levels of their engine—in quite a lot of early Infocom games you can make this sort of loop and cause the objects to disappear from reality. Oops.

1 Like
3

Makes sense. Maybe the thing to do is do the check, if it fails try to take the container first, and if that fails then leave the error message.

One possible issue is there’s nothing preventing things from being in multiple places at once in the setup I have now; for example the same door can be in two rooms at once. But it’s only meant to be used for non-portable things, so I don’t think it’ll be an issue… once we hit a non-portable thing, we can probably stop traversing the tree, since there can’t be any player-induced cycles at that point (I think).

4

Then your model is a DAG (directed acyclic graph) rather than a forest. You can still check for cycles before adding a new connection.

6

Generally, when you act on an object you must first cut old connections (which connections depends on the action) and then form new connections to complete the action. So, start thinking in terms of transactions rather than actions. You sever ties in the first half (leg) of the transaction and then create new ties in the second leg of the transaction.

In your cup example, you must first sever the ties between the red cup and the blue cup and then form new ties between them. This is no different than taking an object from a room. First you sever the ties between the object and the room and then form new ties between object and the player.

Also, the first leg may fail or the second leg may fail and so you also need a way to roll back the transaction, which might have some overlap with your earlier question about undo.

7

That’s generally(*) true but it doesn’t address the cycle problem. The Infocom games mentioned earlier worked this way: the move-object opcode first removed object X from its previous parent, then added it to the new parent. But you could still form a cycle because they didn’t check for that case.

(* Not universally true. For example, you might have a “sun” object which is a backdrop (in I7 terms) – it exists in several rooms. At dawn, the sun is added to every outdoor location, but there’s no connection-cutting step.)

8

Then your model is a DAG (directed acyclic graph) rather than a forest. You can still check for cycles before adding a new connection.

True, it’s just a more branchy search instead of linear. Although the relationship of movable things is supposed to be more like a forest in this setup, and I don’t think these cycles can arise from player actions on immovable things, so once we hit one of those I think the search could end.

Somehow or other, exactly this situation happened with a pair of folders on my computer. Folder B was in folder A, but somehow folder A also ended up in folder B.

Interesting. I just tried this to see what would happen…

> mkdir A
> mkdir A/B
> mv A A/B
mv: cannot move 'A' to a subdirectory of itself, 'A/B/A'

I’m thinking that it could be interpreted in more a forgiving way. User wants to put A in B, so make it happen and then figure out where B needs to go. A reasonable interpretation could be that we end up with ./B/A.

Generally, when you act on an object you must first cut old connections (which connections depends on the action) and then form new connections to complete the action.

This is along the lines of what I was originally thinking. The thing is, it’s the container’s ties that need to be severed, not the thing going inside of it. The simple no-search solution here would be to force taking the container first (if it can be taken), but then when you put cookie in jar you end up holding the jar, which is not what you’d probably want.

9

Yes, path finding (for reporting or other purposes) must be cycle aware, but that just means keeping a list of visited nodes as you explore the path so that you don’t get caught in a loop.

Regarding Inform7 backdrops, consider this code from the documentation:

After sleeping:
    say "It's a bright new day!";
    now the stars are nowhere.

After waiting:
    say "Darkness falls rapidly here.";
    now the stars are everywhere.

I would say in each case the now statement is performing a transaction with two legs. In the first instance the connection to everywhere is first cut and then added to nowhere. Similarly the second now also has two legs: first cut the connection to nowhere and then add the connection to everywhere.

(I assume everywhere and nowhere are regions in Inform7?)

now the sun is in every outdoor location

Even if the sun is not moved to nowhere at night and the now statement is set to run once a day, it can still be thought of transactionally regardless of how it is coded. Cutting the connections (to the same set of rooms) and then re-adding them is equivalent to overwriting the existing connections, which I’m guessing is what’s happening.

10

You can do ln -s ../../A A/B/A to make a symbolic link.

11

In XVAN, the interpreter checks if you try to move something into itself, but not if you move something into a contained object (as in CPB’s cup example). So I made a test story how I could handle this.

The approach is that if you want to move something in a contained object, you take the contained object out first. Consequence is that if you are holding neither object you will end up holding the contained object with the other object in it. But this seems fair to me: if there are two stacked bowls on the floor and you want to put the lower one in the upper one, you must pick up the upper one first.

Here’s transcript output:


=====================================
XVAN transcript for: Containment
version: 1.0

=====================================


> look
Laboratory

You are in the laboratory.

There is a wooden table here.

On the wooden table is a red bowl.

In the red bowl is a blue bowl.


> * now, let's put the red bowl in the blue bowl and see what happens


> put red in blue

Taking the blue bowl out of the red bowl first...
Blue bowl: taken.

Taking the red bowl...
Red bowl: taken.
The red bowl is now in the blue bowl.


> i
You are carrying:
  a blue bowl
    in the blue bowl is a red bowl


> * we are carrying both bowls, because we took the blue bowl out first



> put bowls on table
The blue bowl is now on the wooden table.


> get red
Red bowl: taken.


> l
Laboratory

You are in the laboratory.

There is a wooden table here.

On the wooden table is a blue bowl.


> * now put the red bowl in the blue bowl and see that it doesn't take the blue bowl first


> put red in blue
The red bowl is now in the blue bowl.


> l
Laboratory

You are in the laboratory.

There is a wooden table here.

On the wooden table is a blue bowl.

In the blue bowl is a red bowl.


> take blue
Blue bowl: taken.


> i
You are carrying:
  a blue bowl
    in the blue bowl is a red bowl


> * now put the blue bowl in the red bowl while we are carrying it


> put blue in red

Taking the red bowl out of the blue bowl first...
Red bowl: taken.
The blue bowl is now in the red bowl.


> q
Do you really want to quit? 

Y/n: y

And here’s the source text, trigger t_put does the work.



TITLE         "Containment"
VERSION       "1.0"
AUTHOR        "Marnix van den Bos"


$insert "XVAN Library v1-3-1.lib"

#-------------------------------------------------------------------------------
$LOCATION l_laboratory
 DESCRIPTIONS
   d_sys        "the laboratory"
   d_entr_long  "\nYou are in the laboratory.\n\n"
   d_entr_short "\nYou are in the laboratory.\n\n"

 TRIGGERS
   "put [o_subject] in [o_spec]" -> t_put
   
   t_put
     if owns(o_spec, o_subject) then
       print("[the] [o_subject] is already in [the] [o_spec].\n")
       disagree()
     endif

     if owns(o_subject, o_spec) then
       # the specifier is in the subject
       print("\nTaking the [o_spec] out of [the] [o_subject] first...\n")
       if not(try(o_actor, 0, 1, "take [o_spec]")) then
         # forget the whole thing
         disagree()
       endif
     endif

     # maybe we were not holding the subject
     # we must hold something before we can put it in something else
     if not(owns(o_actor, o_subject)) then
       print("\nTaking the [o_subject]...\n")
       if not(try(o_actor, 0, 1, "take [o_subject]")) then
         disagree()
       endif
     endif

     # finally, put the subject in the specifier
     if not(try(o_actor, 0, 1, "put [o_subject] in [o_spec]")) then
       disagree()
     endif

END_LOC
#-------------------------------------------------------------------------------

#-------------------------------------------------------------------------------
$OBJECT o_table
 DESCRIPTIONS
   d_sys        "the wooden table"
   d_exa        "A wooden table.\n"
   d_entr_long  "There is a wooden table here.\n"
   d_entr_short "There is a wooden table here.\n"

 CONTAINED in l_laboratory

 FLAGS
   f_supporter = 1

END_OBJ
#-------------------------------------------------------------------------------

#-------------------------------------------------------------------------------
$OBJECT o_red_bowl
 DESCRIPTIONS
   d_sys        "the red bowl"
   d_exa        "A red bowl, with rooom for another bowl.\n"
   d_entr_long  "There is a red bowl here.\n"
   d_entr_short "There is red bowl here.\n"

 CONTAINED on o_table

 FLAGS
   f_takeable  = 1
   f_container = 1
   f_open      = 1

 TRIGGERS
   "i" -> t_i

END_OBJ
#-------------------------------------------------------------------------------

#-------------------------------------------------------------------------------
$OBJECT o_blue_bowl
 DESCRIPTIONS
   d_sys        "the blue bowl"
   d_exa        "A blue bowl, with rooom for another bowl.\n"
   d_entr_long  "There is a blue bowl here.\n"
   d_entr_short "There is blue bowl here.\n"

 CONTAINED in o_red_bowl

 FLAGS
   f_takeable  = 1
   f_container = 1
   f_open      = 1

 TRIGGERS
   "i" -> t_i

END_OBJ
#-------------------------------------------------------------------------------

#-------------------------------------------------------------------------------
$OBJECT o_player
 # The o_player object is mandatory and represents the human player.
 DESCRIPTIONS
   d_sys   "You", "me", "I", "head"
   d_exa   "The average adventurer.\n"
   d_init  "Test game for containment.\n\n"

 CONTAINED in l_laboratory

 FLAGS
   f_lit         = 1
   f_seenbefore  = 1
   f_alive       = 1
   f_quenched    = 0
   f_may_save    = 1
   f_verbose     = 0
   f_first       = 1
   f_fixed       = 0
   f_any         = 0  # exclude from t_reveal
   f_verb_help   = 1
   f_exits       = 0  # for the 'exits' command

 ATTRIBUTES
   r_is           = are
   r_have         = have
   r_do           = do
   r_nr_to_reveal = 0
   r_next_dir     = %none
   r_dest         = %none
   r_random       = 0
   r_score        = 0
   r_max_score    = 250  # 5 times 50
   r_key_blocked  = 0

 TRIGGERS
   t_entrance
     agree()

   t_init
     background(blue)
     printcr(d_init)
     printcr("Hit enter...\n")
     hitanykey()
     clearscreen()

     entrance(owner(%this)) # act as if the player just entered the room
     stoptimer(m_init)      # served its purpose

   t_move
     if valdir(l_location, %dir) then
       # it's a valid direction
       if exit(l_location) then
         # no object objects to the player leaving the room
         move(o_player, %dir) # move updates current location
         entrance(l_location)
       endif
     else
       nomatch()  # let other objects or verb default code react.
     endif
     agree()

END_OBJ
#-------------------------------------------------------------------------------
12

I wouldn’t ever want that. It’s just as likely – probably more likely – that the user really wanted to put A in N, and made a typo! Safer to report that the user has made an unreasonable request, and make no changes.

Be careful not to confuse player-moveable things with state changes made by game code. Game code is free to rearrange scenery at will, but should still be protected from accidental cycles.

13

I like that solution, but I think there may be a corner case it doesn’t handle.

Say you have three bowls, a red bowl in a green bowl in a blue bowl. You’re holding the blue bowl. Then you put blue bowl in red bowl. Won’t this create a cycle, because the red bowl was only indirectly inside of the blue bowl, not immediately inside it?

I’m assuming owns checks if something is directly “inside” something else, but doesn’t walk through the whole ownership chain.

Fair enough. I’ve been trying to avoid messages like that for the most part, if something obvious needs to be done first, and just implicitly do that thing instead. But maybe this isn’t one of those cases.

I’m not sure about that last part. If game code creates a cycle, what should happen? Program terminates with an error? Can some kind of static analysis be done to catch it at build time?

I’m tempted to chalk that up to user error, and just worry about not letting the player screw things up. If the author screws something up, I’m not sure what to do about that.

14

Owns() can have additional parameters that are not in the example. One of which is the depth of the containment. By default, containment depth is 1 level, which in most cases is enough. Depth 0 searches the complete tree. So owns(o_player, o_blue_bowl, 0) will return true if the blue bowl is anywhere in the containment tree’s player branch.

I’m looking into an example with four bowls. Complicating factor is that a bowl may only contain one other bowl at the same containment level. So the red bowl may contain both the green and the blue bowl, but only if the green bowl is contained in the blue bowl or the blue bowl is contained in the green bowl.

15

Not in the general case (Rice’s theorem).

But I think you’ll find authors will like your system more if it protects them from this type of error, rather than saying “well, if it breaks it’s your fault”. There’s a reason most programming languages now put in a little bit of overhead to catch null pointer dereferences instead of just calling it undefined behavior like C.

In Inform 6, for example, the standard way to change an object’s parent does this sort of error-checking automatically, and fails (and prints an error message) if you try to create a cycle. You can turn this checking off with a command-line flag if you need the slight speed increase, but most people just leave it on: the extra insight when something breaks is considered more valuable than the few extra virtual CPU cycles it costs.

16

Hmm, I see what you mean. I think part of the issue is that there is currently no smart “move” routine that makes sure something is actually allowed to go somewhere. I could separate that out from the routine for putting something somewhere, though.

The other part of the issue is there are currently no runtime errors possible, other than an out-of-memory error if you create an infinite loop and do something inside it that causes memory allocation. So I’m hesitant to create one at this level, I guess.

The other thing is that I’m still not convinced this should actually represent an unrecoverable error. Here’s the thing – say I’m playing solitaire, and I have a jack on the table, and a queen on the jack. You say “now put the jack on the queen.” I respond “I can’t, because the queen is on the jack; that would be a paradox. I quit!” Something seems wrong with that interpretation… it should be clear that you meant take the jack from under the queen, leaving the queen on the table, then put the jack on top of the queen.

I’ll think about this more, thanks for the input!

17

It doesn’t necessarily have to be a full exception-handling system: Inform (both 6 and 7) basically just prints an error message and keeps going, without altering the object tree. (Same if you divide by zero, request the parent or sibling of nothing, etc.)

I’d expect that to be handled in user code: in other words, the PUT X ON Y command doesn’t just call a @move X, Y instruction, it does some checking first to make sure it’s sensible. Same as implicit taking and the like.

18

What I ended up doing is a full cycle check, and if it fails (trying to put X in Y when Y is in X), it says “you’ll need to take Y from X first,” then tries to take Y before putting X in Y.

If Y can’t be taken, you’re left with messages like “you’ll need to take Y from X first … Y is firmly attached to Z,” which seems like a clear enough indication that it would create a cycle. If Y can be taken, the cycle is broken and you end up holding Y with X in it.

This is just baseline default behavior, all boilerplate messages and behavior can be overridden. Still no smart “move” routine, but the cycle check is available to authors. This is essentially the same as Marnix’s solution, with the cycle check traversing all ancestors.