Best Practice for Transitioning From Nested State to Nested State (see diagram)

Question

I am trying to wrap my mind around the best way to implement nested state transitions in a single threaded programming language (Actionscript). Say I have a structure like this behavior tree:

Now imagine that each leaf node is a destination point on a website, like an image in a gallery, or a comment nested in a post view nested in a page view... And the goal is to be able to run animated transitions from leaf node to leaf node, by animating out the previous tree (from bottom to top), and animating in the current tree (from top to bottom).

So, if we were at the bottom-left-most leaf node, and we wanted to go to the bottom-right-most leaf node, we would have to:

• transition out bottom-left-node
• on complete (say after a second of animation), transition out it's parent,
• on complete, transition out it's parent
• on complete, transition IN the right-most parent
• on complete, transition in right most-child
• on complete, transition in leaf

My question is:

If you imagine each of these nodes as HTML views (where the leaves are 'partials', borrowing the term from rails), or MXML views, where you're nesting sub components, and you don't necessarily know the nest levels from the application root, what is the best way to animate the transition as described above?

One way is to store all possible paths globally, and then to say "Application, transition out this path, transition in this path". That works if the application is very simple. That's how Gaia does it, an Actionscript framework. But if you want it to be able to transition in/out arbitrarily nested paths, you can't store that globally because:

1. Actionscript couldn't handle all that processing
2. Doesn't seem like good encapsulation

So this question can be reworded as, how do you animate out the left-most-leaf node and it's parents, starting from the leaf, and animate in the right-most-leaf node, starting with the root? Where is that information stored (what to transition in and out)?

Another possible solution would be to just say "Application, transition out previous child node, and when that's complete, transition in the current child node", where the "child node" is the direct child of the application root. Then the left-most child of the application root (which has two child nodes, which each have two child nodes), would check if it's in the right state (if it's children are 'transitioned out'). If not, it would call "transitionOut()" on them... That way everything would be completely encapsulated. But it seems like that'd be pretty processor intensive.

What do you think? Do you have any other alternatives? Or can you point me to any good resources on AI Behavior Trees or Hierarchical State Machines that describe how they practically implement asynchronous state transitions:

• From where do they call "transitionOut" on an object? From the root or a specific child?
• Where is the state stored? Globally, locally? What is the scope defining what calls "transitionIn()" and "transitionOut()"?

I have seen/read many articles/books on AI and State Machines, but I have yet to find something describing how they actually implement asychronous/animated transitions in a complex MVC Object Oriented Project with 100s of Views/Graphics participating in the behavior tree.

Should I call the transitions from the parent-most object, or from the child?

Here are some of the things I've examined:

• An Architecture for Game Behavior AI: Behavior Multi-Queues
• Hierarchical State Machines — a Fundamentally Important Way of Design
• Programming Game AI by Example
• Goal-Driven Agent Behavior
• Advanced State Management by Troy Gardner
• Troyworks' AS3 COGS Library
• Popular Approaches to Behavior-Tree Design
• Building Event-Driven Conditions for an Asynchronous Sensory System

While this is not necessarily an AI problem, there are no other resources describing how to apply nested state architectures to websites; these are the closest things.

Another way to word the question: How do you broadcast state changes to the application? Where do you keep the event listeners? How do you find what view to animate when it's arbitrarily nested?

Note: I am not trying to build a game, just trying to build animated websites.

Answer 1

I'm just guessing here but you can store that tree in an actual tree in your code and then, when clicked you want to navigate you call a function that's called, say, findPath(fromNode, toNode) that function will find the path between the two nodes, one way to do that is with this pseudo code:

Define array1;
Define array2;

loop while flag is false {
    store fromNode's parent node in array1;
    store toNode's parent node in array2;

    loop through array1 {
        loop through array2 {
            if array1[i] == array2[j] {
             flag = true;
            }
        }
    }
}

path = array1 + reverse(array2);

And there is your path.

UPDATE:

Another solution would be to make each page have something like this pseudo code--I'm starting to really love pseudo code:

function checkChildren(targetNode) {
    loop through children {
        if children[i] == target {
            return path;
        }
        if children[i].checkChildren == target node {
            return path;
        }
    }
}

This is very very abstract, it has a lot more details to it and a lot of optimizations, here's what I have in mind:

• Pass the path going up the tree to the function so the path can be found directly instead of returning to the calling function.
• Pass the current calling child to the parents checkChildren so it won't bother checking that child to make checking faster.

I still think i haven't delivered my idea well so I'll try to explain it.

Say you're going from pic2 in the gallery to project3 in projects.

pic2 would check its children (if any), if it finds the target it goes there, otherwise it calls its parent (gallery)'s checkChildren passing itself to the parent won't bother checking it, and passing itself to the parent in an array so the parent knows what path has been taken.

The parent checks its children if any of them is the target, if it is it adds itself and the child to the path array and that's the path.

If it none of its direct children is the target then it calls each of its children's checkChildren passing adding itself to the array of the path so that if any of its children finds the target it adds itself and the child to the array and you have your path.

If none of the children find the target gallery calls its parent (home page)'s check children passing itself and the adding itself to the array of the path.

The homepage checks all its children except gallery using the same method.

Alternatively, you can choose not to pass the path as an array but instead just transition to the parent page if none of the children or the children's children match 'cause you're sure the target is not under this page.

I hope I made myself clear. I can write checkChildren for you if you want.

Answer 2

I'll try to simplify the problem before suggesting a possible approach. The transitions seem related to the views, and not the model. If I were to skip the transitions and go straight to some other leaf node, the application still works but there is not visual clue for the users. So I'd suggest you use a view-controller specifically to hold the current branch and the transitions of various views.

It's probably a better approach to split the two types of transitions into a sort of stack where a pop transition is to go back to a previous node, while a push transition goes forward in the hierarchy. Apple uses a similar technique to manage navigational applications using a navigation view controller. It basically maintains a stack of view controllers that the user followed to get to a particular node. When a user goes back, the top item is popped off the stack, and the user sees the previous item. If the user goes deeper in the hierarchy, a new view controller is pushed onto the stack.

You would still need a global way to represent the hierarchies in a flyweight manner, while the navigation stack only stores the currently visible branch down to the leaf node.

If a user went from one leaf node to another, the current stack will be popped out upto the common parent. Then the global tree structure will be asked to get the path from that parent upto the new leaf node. This path of nodes is pushed into the current navigation stack, and as each item is pushed, the transition is shown.

In a simple algorithm, there'd be these two data structures and a way to get the entire branch that contains leaf node:

1. a global representation of the tree
2. a stack of the current branch

initially:

stack = []
tree = create-tree()

algorithm:

// empty current branch upto the common ancestor, root node if nothing else
until stack.peek() is in leaf-node.ancestors() {
    stack.pop() // animates the transition-out
}
parent = stack.peek();
// get a path from the parent to leaf-node
path = tree.get-path(parent, leaf-node)
for each node in path {
    stack.push(node) // animates the transition-in
}

Update:

The entire application could have a single navigation controller, or multiple such controllers. A navigation controller only needs to know that there is a tree which exposes certain operations. So you could create an interface with those operations and let concrete subclasses implement that.

I can only think of two operations that would need to be exposed (pseudo-Java syntax):

interface Tree {
    List<Node> getAncestors(node);
    List<Node> findPath(ancestorNode, descendantNode);
}

That should provide sufficient abstraction to keep the navigation controller poking inside the global tree structure. To take it to the next level, use dependency injection so the tree object is injected into the navigation controller, improving testability and breaking the tree connection completely.

Answer 3

either I don't fully understand you problem, or you are making it much too complicated ... try to think simple, because basically, all what you want to do, is the following:

1. retrieve a path within a tree
2. execute multiple animations sequentially (along that very path)

none of these things is much to hard. for the latter task, you can probably use one of the better AS3 animation libraries. but for the sake of understanding, let me offer you a lightweight solution:

your problem is simply carrying out asynchronous tasks sequentially. retrieving the sequence itself is not really hard. however, you should consider, that not every path passes through the root (for example from one leaf to its sibbling). in the flash world, the only way to execute asynchronous tasks sequentially are callbacks. when one task finishes, it calls back, and from there you decide what to do next.

so here comes some code:

first, let's define an interface for all your leafs/nodes ... the following should do the trick:

package  {
    public interface ITransitionable {
     //implementors are to call callback when the show/hide transition is complete
     function show(callback:Function):void;
     function hide(callback:Function):void;
     function get parent():ITransitionable;
    }
}

now the following class will be able to do transitions as you specified on trees of ITransitionable:

package  {
 public class Transition {
  ///Array of animation starting functions
  private var funcs:Array;
  ///Function to call at the end of the transition
  private var callback:Function;
  public function Transition(from:ITransitionable, to:ITransitionable, callback:Function) {
   this.callback = callback;
   this.funcs = [];
   var pFrom:Array = path(from).reverse();
   var pTo:Array = path(to).reverse();
   while ((pFrom[0] == pTo[0]) && (pTo[0] != null)) {//eliminate common path to root
    pFrom.shift();
    pTo.shift();
   }
   pFrom.reverse();//bring this one back into the right order
   //fill the function array:
   var t:ITransitionable;
   for each (t in pFrom) this.funcs.push(hider(t));
   for each (t in pFrom) this.funcs.push(shower(t));
   this.next();
  }
  ///cancels the overall transition
  public function cancel():void {
   this.funcs = [];
  }
  ///creates a function that will start a hiding transition on the given ITransitionable.
  private function hider(t:ITransitionable):Function {
   return function ():void {
    t.hide(this.next());
   }
  }
  ///@see hider
  private function shower(t:ITransitionable):Function {
   return function ():void {
    t.show(this.next());
   }
  }
  ///this function serves as simple callback to start the next animation function
  private function next(...args):void {
   if (this.funcs.length > 0) this.funcs.shift()();
   else this.callback();
  }
  ///returns the path from a node to the root
  private function path(node:ITransitionable):Array {
   var ret:Array = [];
   while (node != null) {
    ret.push(node);
    node = node.parent;
   }
   return ret;
  }
 }

}

it's not a perfect beauty, but it should suffice to point you into the right direction. no need for fancy state machines, what so ever ... hope this helps ... ;)

greetz

back2dos