Tuesday, September 17, 2013

AI Decision Trees

To begin implementing AI into any game, one must first design how the machine is going to think and react. The easiest way to do so is through a decision tree. A decision tree is like a branching river; the flow goes in one direction but the branching paths might lead the flow in drastically separate areas.
The basis for designing a decision tree requires that your AI has states to keep in mind, such as moving to a designated area and then moving back. As a start, here is the image of my AI example with all of the players in a resting state.

At this point their current state was one of doing nothing. They just sat there until I gave the program the right to start. But once they began, the Decision Making started.

---

The players at the top-right and the bottom-left of the screen are classified as defenders, whose job is to only stop players when they've picked up one of the flags, so their decision tree is telling them to sit there and wait until someone takes the flag. The other two players begin moving towards the opposing flag immediately since their decision tree dictates them to do so.


---

But why does their decision tree tell them to do so? Let's take a closer look at the decision tree involved with their movements.

Firstly there exists an overarching Decision Node. Inside this node is the "question" that it must ask, in this case that question is "Does the player currently have the flag?". Every update of the program, this Decision Node checks its question and then decides how the player will react based on the result it has found. Once an answer has been found, the Decision Node will direct towards one of the State Nodes that come along with it. These State Nodes exist simply to change the state of the player into whatever the State Node's are programmed to contain. In our example this means that if the player currently has the flag, the Decision Node will direct him to the Return to Base Node and the player will understand that he need to return to base.
Now Decision Nodes don't always need to come to an abrupt end with State Nodes. Decision Nodes could always lead into other Decision Nodes and deepen the logic further. This manner of layered Decision Nodes is what gives alot of the game's AI the ability to think, or to at least pretend that it is thinking.

---

So now that we understand why the player is moving the way he is, we can easily understand how the defenders work.

The defenders are looking for the signal when an opposing player picks up their flag. As soon as they do the Decision Node gives the defenders a new order to seek out the enemy and reclaim their flag. Their Decision Tree is very similar to the attackers, except that their only states are "defending" and "seeking".

Since the Decision Tree is nearly constantly updating, the player's will always be complying to one of their two states. Therefore when one of the defenders hits the player and returns the flag (as seen in the example with the top two players) that player will then automatically seek out the flag once again. This makes it so there is never an interruption in logic.

No comments:

Post a Comment