Tree Algorithm

Question

I was thinking earlier today about an idea for a small game and stumbled upon how to implement it. The idea is that the player can make a series of moves that cause a little effect, but if done in a specific sequence would cause a greater effect. So far so good, this I know how to do. Obviously, I had to make it be more complicated (because we love to make it more complicated), so I thought that there could be more than one possible path for the sequence that would both cause greater effects, albeit different ones. Also, part of some sequences could be the beggining of other sequences, or even whole sequences could be contained by other bigger sequences. Now I don't know for sure the best way to implement this. I had some ideas, though.

1) I could implement a circular n-linked list. But since the list of moves never end, I fear it might cause a stack overflow ™. The idea is that every node would have n children and upon receiving a command, it might lead you to one of his children or, if no children was available to such command, lead you back to the beggining. Upon arrival on any children, a couple of functions would be executed causing the small and big effect. This might, though, lead to a lot of duplicated nodes on the tree to cope up with all the possible sequences ending on that specific move with different effects, which might be a pain to maintain but I am not sure. I never tried something this complex on code, only theoretically. Does this algorithm exist and have a name? Is it a good idea?

2) I could implement a state machine. Then instead of wandering around a linked list, I'd have some giant nested switch that would call functions and update the machine state accordingly. Seems simpler to implement, but... well... doesn't seem fun... nor ellegant. Giant switchs always seem ugly to me, but would this work better?

3) Suggestions? I am good, but I am far inexperienced. The good thing of the coding field is that no matter how weird your problem is, someone solved it in the past, but you must know where to look. Someone might have a better idea than those I had, and I really wanted to hear suggestions.

Answer 1

What you're describing sounds very similar to the technology tree in a game live Civilization.

I don't know how the Civ authors built theirs, but I'd be inclined to use a multigraph to represent possible 'moves' - there will be some you can start at with no 'experience', and once you're in them, there will be multiple paths through to the end.

Draw-out what potential options you can have at each stage of the game, and then draw lines going from some options to others.

That should give you a start on implementation, as graphs are [relatively] easy concepts to implement and utilize.

Answer 2

You might want to implement a state machine anyway, but you don't have to hardcode state transitions.
Try to make a graph of states, where link between state A to state B will mean A can lead to B.
Then you can traverse graph at runtime to find where player goes.

Edit: You can define graph node as:
-state-id
-list of links to other states, where every link defines:
-state-id
-precondition, a list of states what must be visited before going to this state

Answer 3

Sounds like a neural network. You could create one and train it to recognize the patterns that cause the various effects you are looking for.

Answer 4

What you're describing sounds somewhat similar to a dependency graph or a word graph. You might look into those.

Answer 5

I'm not absolutely completely sure that I understand exactly what you're saying, but as an analagous situation, say someone's inputting an endless stream of numbers on the keyboard. '117' is a magic sequence, '468' is another one, '411799' is another (which contains the first one).

So if the user enters:

55468411799

you want to fire 'magic events' at the *s:

55468*4117*99*

or something like that, right? If that's analagous to the problem you're talking about, then what about something like (Java-like pseudocode):

MagicSequence fireworks = new MagicSequence(new FireworksAction(), 1, 1, 7);
MagicSequence playMusic = new MagicSequence(new MusicAction(), 4, 6, 8);
MagicSequence fixUserADrink = new MagicSequence(new ManhattanAction(), 4, 1, 1, 7, 9, 9);

Collection<MagicSequence> sequences = ... all of the above ...;

while (true) {
  int num = readNumberFromUser();
  for (MagicSequence seq : sequences) {
    seq.handleNumber(num);
  }
}

while MagicSequence has something like:

Action action = ... populated from constructor ...;
int[] sequence = ... populated from constructor ...;
int position = 0;

public void handleNumber(int num) {
  if (num == sequence[position]) {
    // They've entered the next number in the sequence
    position++;
    if (position == sequence.length) {
       // They've got it all!
       action.fire();
       position = 0; // Or disable this Sequence from accepting more numbers if it's a once-off
    }
  } else {
    position = 0; // missed a number, start again!
  }
}

Answer 6

create a small state machine for each effect that you'd want. at each user action, 'broadcast' it to all state machines. most of then won't care, but some will advance, or maybe go backwards. when one of them reaches it's goal, produce the desired effect.

to keep the code neat, don't hardcode the state machines, instead build a simple data structure that encodes the state graph: each state is a node with a list of interesting events, each one points to the next state's node. Each machine's state is simply a reference to the appropriate state node.

edit: It seems Cowan's advice is equivalent to this, but he optimises his state machines to express only simple sequences. seems enough for your specific problem, but more complex conditions could need a more general solution.

Answer 7

@Cowan, @Javier: Nice idea, mind if I add to it?

Let the MagicSequence objects listen to the incoming stream of user input, that is notify them of the input (broadcast) and let each of them add the input to there internal input stream. This stream is cleared when the input is not the expected next input in the pattern that would have the MagicSequence fire its action. As soon as the pattern is completed, fire the action and clear the internal input stream.

Optimize this by only feeding input to the MagicSequences that are waiting for it. This could be done two ways:

1. You have an object that lets all MagicSequences connect with events that correspond with numbers in their patterns. MagicSequence(1,1,7) would add itself to got1 and got7, for example:

   UserInput.got1 += MagicSequnece[i].SendMeInput;

2. You could optimize this such that after each input MagicSequences deregister from invalid events and register with valid ones.