# State Ranges Tree - how to implement it?

This topic is 4733 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello everyone, Q: In order to make a GameEntity "smarter", I have read somewhere that one way to do it is introduce "ranges" when you're switching to a new state. It's in the form of a tree. ex: root of the tree is the state "attack ennemy". The child nodes of this root node are "health 0 - 49" and "health 50 - 100". The child of "health 0 - 49" could have children "ammo 0 - 69" and "ammo 70 - 100". The leaf node of "ammo 70 - 100" would have "attack" (presumably because the entity feels it has enough ammo to kill the opponent), whereas "ammo 0 - 69" would have the leaf node "flee" (not enough health and low ammo". My question is, how would one code this? Seems to me u'd need to have each node do a comparison and the comparison that specific node would do is very specific and different from the rest of the nodes (different range, different variable to compare the range against. ex: the variable could be ammo, or health). So why not just straight out code this as a different "StateExecutor" class? The class would have bunch of if-else's - yes not too elegant, but then again the tree is a nice idea, but you have to "program" each node anyways. If the nodes just needed value range, then I could see that perhaps the ranges could be read from a file. But it has a "behaviour" change (different variable to work with). I am really kind of stumped by this. I really like the idea of a tree for this application, but I just can't figure out a decent way to "populate" such a tree at non-runtime without having to have to code each node with specific behaviour and having to then assemble this tree at runtime. Any ideas would be most welcomed!

##### Share on other sites
I don't know why the tree idea seems maybe too complex. If you have something like this, it may be quicker and easier to use the if/else or switches because in the end(tell me if I'm wrong), when you traverse the tree, you'll have to do these comparisons anyway. I'd just the grouped if/else depending on the decisions.

##### Share on other sites
kburkhart84,

I agree with you. I said as much in my post.

However, it seems to me my logic is probably flawed, since trees like like a really cool DS to use for this particular problem. I saw this in a book, except they didn't go into details as to how to implement it.

That is why I want the opinions of other people, since it is imposible that I am the only one faced with this kind of situations.

And if-else can get quite ugly quite fast and aren't flexible - you can't add conditions after you've compiled the game - wouldn't it be cool to add new conditions into this tree with a level / character editor or at least use xml files for that perhaps?

##### Share on other sites
Trees can be useful for this sort of thing - it'd be a 'decision tree', in AI parlance. Gives you a lot of flexibility that statically coded if's etc. don't have. (Warning: code below is almost certainly horribly broken.)

What you need to do is have some kind of data structure to represent a given decision. Say for example your entity is considering its own statistics to make a decision:

class Enemy {  int stat_a, stat_b, stat_c;  friend class DecisionNode;  DecisionNode* strategy; // the enemy's state}

Now you make normal strategy objects to represent plain states (flee, attack etc.) :

class DecisionLeaf : public DecisionNode {  enum { FLEE, ATTACK, ... } action;  action a;  // etc.  void operator() (Enemy * parent) {    // Cause the Enemy to do something according to 'action'  }}

And now we need other types of DecisionNode to handle the 'logic' cases:

class ComparisonNode : public DecisionNode {  DecisionNode* lessThan;  DecisionNode* equal;  DecisionNode* greaterThan;  int threshold;  Enemy::int& type; // provides an offset to the Enemy data member to use.  // I'm pretty sure something like this exists but I don't really know how the  // syntax needs to work.  // etc.  void operator() (Enemy * parent) {    int parents_value = parent->type;    // Do the comparison, select a child and invoke it    if parents_value < threshold  { *lessThan(parent); }    else if parents_value == threshold { *equal(parent); }    else { *greaterThan(parent); }  }}

The idea is to make an object that encapsulates the concept of the comparison and dispatch.

##### Share on other sites
Hey ZahlMan,

thanks a million for your post. It helped me a lot. I really appreciate you taking your time and writing up all that code. You consistently post good answers. To you these things are probably obvious at this point, but to the rest of us it always isn't so and hence help such as yours is primordial.

I have few questions regarding your post:

1) I imagine the class that's missing from your code, DecisionNode is simply an interface ABC - something like so:

class DecisionNode{

void operator(Enemy * parent) = 0;

}

2) in your class Enemy, where you have the line DecisionNode* strategy; - does this represent the root node for ONE particular state, or does the resulting nodes represent all the states? It seems it represents one state only (yes, your tree nodes can definitely end up calling different DecisionLeaf that represent different states).

What I am getting at is that should I have one strategy (or tree) PER ENTITY STATE? Or should I have one tree for ALL entity states?

I was trying to see how I could have one tree for all entity states and I am not sure if it is reasonably feasible. First I'd still have to draw it out on a paper and see if you can even arrange all the states in one tree or if the states are not simply on the same level and hence necessitate different tree for each. Furthermore, I'd have to wrap the nodes into a tree class to ficilitate depth-first searches, since the first thing would be to search for the right state node and start executing from there.

Any thought on all this?

Thanks a lot!

##### Share on other sites
Quote:
 Original post by nikdoHey ZahlMan,thanks a million for your post. It helped me a lot. I really appreciate you taking your time and writing up all that code. You consistently post good answers. To you these things are probably obvious at this point, but to the rest of us it always isn't so and hence help such as yours is primordial.

Thanks. I sure hope noone expects my stuff to compile and work right, right off, though. ^^; (I really should just download and set up a C++ compiler...)

Quote:
 1) I imagine the class that's missing from your code, DecisionNode is simply an interface ABC - something like so:class DecisionNode{ void operator(Enemy * parent) = 0;}

virtual void operator() (Enemy * parent), is more or less what I had in mind, yeah. You might find a use for other stuff in there, I don't know. Note the brackets; you need the empty () to specify which operator is being overloaded, and then the arguments go in a second set.

Quote:
 2) in your class Enemy, where you have the line DecisionNode* strategy; - does this represent the root node for ONE particular state, or does the resulting nodes represent all the states? It seems it represents one state only (yes, your tree nodes can definitely end up calling different DecisionLeaf that represent different states).What I am getting at is that should I have one strategy (or tree) PER ENTITY STATE? Or should I have one tree for ALL entity states?

The 'strategy' is the root node for an Enemy instance's current "brain". You have conceptually one tree per Enemy, although you may be able to share them in some cases ("hive mind"?) You can change the trees at run-time according to whatever criteria. You might for example set up some prototype trees to represent various sorts of "behaviour" (or "emotion"? Hmm...), and then have each Enemy link to the root of one of these (and at intervals, possibly change that linkage). The entire tree represents a strategy; each node represents just a step in the decision-making process.

Quote:
 I was trying to see how I could have one tree for all entity states and I am not sure if it is reasonably feasible. First I'd still have to draw it out on a paper and see if you can even arrange all the states in one tree or if the states are not simply on the same level and hence necessitate different tree for each. Furthermore, I'd have to wrap the nodes into a tree class to ficilitate depth-first searches, since the first thing would be to search for the right state node and start executing from there.

You don't "search" the tree; you "execute" it. Each node is a callable object. The leaf nodes implement the 'primitives' of entity behaviour; internal nodes select one of their children and invoke it. Thus, to cause the entity to do something, you just invoke the root node; it invokes one of the children, and so on recursively until a child node is reached, which then makes the entity Do Something(TM) (by acting through an interface which the entity exposes to the nodes - for illustration purposes I chose to just make it a friend class, so you could do anything).

The trick is in building the trees, really. :) Really advanced AI might involve tweaking trees on the fly according to what seems to be working or not working (genetic programming), by substituting nodes in the tree (or just changing the threshold values in those nodes).

##### Share on other sites
Lets see, you could set up something like this:

class Node{  public:   Node(short checkStat, int min, int max, short children, in action);   ~Node();    int check();   private:     short _checkStat;     int _min;     int max;     short _children;     Node* _childrenList;};

You then have two enums, one representing possible stats, one representing possible actions. You then use recursion to go to check each of nodes children to see if they current compariosn is true, if it is then its children are checked. This contiunes until you reach a leaf node you then pop that nodes action back up as the chosen action. Another bit of code then performs that action.

##### Share on other sites
[quotevirtual void operator() (Enemy * parent), is more or less what I had in mind, yeah. You might find a use for other stuff in there, I don't know. Note the brackets; you need the empty () to specify which operator is being overloaded, and then the arguments go in a second set.
[/quote]

Zahlman,

sorry i was out of the door when i wrote the reply, of course I ment a pure virtual function.

I think I have a much better idea of how to go about things. I will look into it deeper now to hammer out some details pertinent to my implementation.

Thanks again for putting me on the right track.

Peter

##### Share on other sites
if you really know how deep the tree is (i.e in your case 3), why use a tree?, you could use a neural net with only 3 layers. Also instead of programming in the runtime data, you could read it in from a generated data file (xml?).

##### Share on other sites
Hey Genjix,

1) Well yes, I could know how deep the tree would be before runtime, sure, but it would be really cool to be able to expand it at runtime.

2) I had in mind to provide an xml node at loadtime to set up my trees - one tree per state per entity. However, reading xml trees at runtime is slow. I would still prefer to load the tree from xml, but then have a runtime tree which i can use in every frame. And since the tree will not be necessarily static (can change) I wouldn't want ti insert into the xml tree at runtime. I think performance-wise, that would kill my frame rates (unless someoen can prove me wrong?).

3) Neural net - hm, heard the word, but dunno what it really stands for. Care to expand on the concept a bit? I would greatly appreciate it. Perhaps you could tell me why it works with static layers and not dynamic ones.

If this would make for a lenghty explanation, if you can provide a link to some ressource where I can learn about neural net, Iwould greatly appreciate it as well.

##### Share on other sites
Neural nets...

They are basically nets, made from interlinking formulas, which are good at generalising, and you can train them to do a whole lot of stuff.

They are nowhere near as fast as if then statements (a dirivitive of which i use)<, but they could be what you need.

What do i use?

I use the ifs to change the probability of each reaction being taken, i use a table of values to do this (Loaded on loadtime), and it is fast, and adjustable (you just can't change the triggers, usually).

From,
Nice coder

##### Share on other sites
another idea i've got is a multi layered graph, where each node makes choices using if/elses. Best Search String I could find and ai-depot.com. Since you know how many nodes you have, and the choices they can make (even if you don't know get a program to generate the best one using a genetic algorithm :P), you can read it in from an xml file, such as naming nodes (depth is indication of type).
<NodeName x="1" y="10" z="2">    <NodeName x="1" y="10" z="2">        <NodeName x="1" y="10" z="2" />        <NodeName x="1" y="10" z="2" />    </NodeName>    <NodeName x="1" y="10" z="2">        <NodeName x="1" y="10" z="2" />    </NodeName></NodeName><NodeName x="1" y="10" z="2">    <NodeName x="1" y="10" z="2">        <NodeName x="1" y="10" z="2" />    </NodeName></NodeName>

(couldn't be bothered to name all nodes) - if you want to be able to loop back (as in a node can go to anywhere else in the tree), you might prefer something like.
<NodeName type="3" x="16" y="7" z="18" />

and when it comes to choices, you can use Nice Coders if statements. Good Luck!

##### Share on other sites
on another note,
struct Whatever{      // ...      int x , y;   // pos in table, of next node};Whatever table[3][xsize][ysize]; // 3 layers// ... set up tabletable[0][XPOS][YPOS].x and table[0][XPOS][YPOS].y is next node down positiontable[1][ table[0][XPOS][YPOS].x ][ table[0][XPOS][YPOS].y ].xtable[1][ table[0][XPOS][YPOS].x ][ table[0][XPOS][YPOS].y ].yis position of last layers node.

this is very crude, and is very simple, but I'd think it'd do the job in this case.

• 12
• 10
• 11
• 18
• 13