Macromedia Flash MX 2004 Game Programming (Premier Press Game Development) - page 104
Trees
A tree is a way of organizing data. The idea is that each data element, called a node , contains data as well as links to other nodes. Each tree begins with a root node , and the tree builds from there. Generally, we draw trees upside down with the root node on top and the connections from it going down. Nodes at the bottom (furthest from the root) are called leaf nodes. See Figure 10.7 for an example of a tree.
Figure 10.7:
A tree structure contains a root node, interior nodes, and leaf nodes.
Tree structures are commonly used data formats in programming. Trees have countless applications, but this chapter focuses on using them to build computer AI. Just be aware that you can use trees to store data for many different kinds of applications.
Now we need to define what a node is. Each node, as I've said, has links to other nodes further down the tree. The nodes further down the tree are called child nodes . Nodes further up the tree are called parent nodes .
| Tip |
One particular type of tree, called a binary tree , contains nodes with a maximum of two children. These kinds of trees can store ordered data ”that is, data that has been sorted into a particular order. By storing sorted data in a tree structure, you can increase performance when accessing, adding, and deleting data (nodes). This performance increase is most pronounced when there are many nodes. With few nodes, the additional work required to iterate the tree (recursion) is more work than the tree structure provides in benefit. |
Using a tree structure requires recursion because a simple loop cannot handle this situation. If you are modeling data with a tree structure, you want to define methods to add data, remove data, and access data into the tree structure. All these
Our use of the tree structure is limited to what we need to build a game tree.
The Game Tree
A game tree is a model of all possible moves in a game, organized as a tree. For example, consider the tic tac toe board in Figure 10.8.
Figure 10.8:
A tic tac toe board is
Now imagine that you are playing X and the computer is trying to play O. You have just made your second move. For the computer to decide where to play next, it must analyze each possible move. (There are nine possible moves for O right now.) If we draw every possible
Figure 10.9:
The tic tac toe
Now let's take it one step further. For each of those nine possible moves, let's construct every possible next move of X. If we add each of these under the nine possible moves for O, our tree will be one level deeper and look like Figure 10.10.
Figure 10.10:
Every possible next move for X is added to the tree. Note that only two lower branches are shown in this figure for space considerations.
At this point, you can see that some of the possible moves O can make next allow X to win the game. Those are obviously moves that O would not want to make. Some of the moves do not yet win for X, so those are worth considering further. We can continue to do this until all possible conclusions to the game have been reached.
In this way, all possible moves are
As an example, I want to implement tic tac toe so that you can see a simple recursive solution to a