The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Decision Trees

Next ►
►

Introduction

Decision trees are a popular method for implementing decision-making in video games. They provide a clear and structured way to represent decisions and their possible outcomes, making them easy to understand and implement. In this section, we will cover the basics of decision trees, their structure, and how to implement them in a game environment.

Key Concepts

What is a Decision Tree?

A decision tree is a tree-like model used to make decisions based on a series of conditions. Each node in the tree represents a decision point, and each branch represents the outcome of that decision. The leaves of the tree represent the final actions or outcomes.

Structure of a Decision Tree

  • Root Node: The starting point of the tree, representing the initial decision.
  • Internal Nodes: Represent decisions based on certain conditions.
  • Branches: Represent the outcomes of decisions, leading to other nodes or leaves.
  • Leaf Nodes: Represent the final actions or outcomes.

Advantages of Decision Trees

  • Simplicity: Easy to understand and implement.
  • Flexibility: Can handle both numerical and categorical data.
  • Transparency: The decision-making process is clearly visible.

Disadvantages of Decision Trees

  • Overfitting: Can become overly complex with too many branches.
  • Instability: Small changes in data can lead to different trees.

Example: Implementing a Decision Tree in a Game

Let's consider a simple example where an NPC (Non-Player Character) decides whether to attack, defend, or flee based on its health and the number of enemies nearby.

Step-by-Step Implementation

  1. Define the Decision Criteria:

    • Health of the NPC
    • Number of enemies nearby

  2. Create the Decision Tree:

                [Health > 50%]
                /           \
             Yes             No
            /                 \
    [Enemies < 3]           Flee
    /         \
  Yes         No
 Attack     Defend
  1. Implement the Decision Tree in Code:
class NPC:
    def __init__(self, health, enemies_nearby):
        self.health = health
        self.enemies_nearby = enemies_nearby

    def make_decision(self):
        if self.health > 50:
            if self.enemies_nearby < 3:
                return "Attack"
            else:
                return "Defend"
        else:
            return "Flee"

# Example usage
npc = NPC(health=60, enemies_nearby=2)
decision = npc.make_decision()
print(f"NPC Decision: {decision}")

Explanation of the Code

  • Class Definition: We define an NPC class with attributes for health and the number of enemies nearby.
  • Decision Method: The make_decision method implements the decision tree logic.
  • Example Usage: We create an instance of the NPC class and call the make_decision method to determine the NPC's action.

Practical Exercise

Exercise 1: Extend the Decision Tree

Extend the decision tree to include an additional decision based on the NPC's stamina. If the stamina is below 30%, the NPC should always choose to flee, regardless of health or enemies nearby.

Solution:

  1. Update the Decision Tree:
                [Stamina > 30%]
                /           \
             Yes             No
            /                 \
    [Health > 50%]           Flee
    /           \
  Yes           No
 /               \
[Enemies < 3]   Flee
 /       \
Attack   Defend
  1. Implement the Extended Decision Tree in Code:
class NPC:
    def __init__(self, health, enemies_nearby, stamina):
        self.health = health
        self.enemies_nearby = enemies_nearby
        self.stamina = stamina

    def make_decision(self):
        if self.stamina <= 30:
            return "Flee"
        if self.health > 50:
            if self.enemies_nearby < 3:
                return "Attack"
            else:
                return "Defend"
        else:
            return "Flee"

# Example usage
npc = NPC(health=60, enemies_nearby=2, stamina=25)
decision = npc.make_decision()
print(f"NPC Decision: {decision}")

Exercise 2: Add More Conditions

Add a condition to check if the NPC has a weapon. If the NPC does not have a weapon, it should always choose to flee.

Solution:

  1. Update the Decision Tree:
                [Has Weapon]
                /           \
             Yes             No
            /                 \
    [Stamina > 30%]          Flee
    /           \
  Yes           No
 /               \
[Health > 50%]   Flee
 /       \
[Enemies < 3]
 /       \
Attack   Defend
  1. Implement the Updated Decision Tree in Code:
class NPC:
    def __init__(self, health, enemies_nearby, stamina, has_weapon):
        self.health = health
        self.enemies_nearby = enemies_nearby
        self.stamina = stamina
        self.has_weapon = has_weapon

    def make_decision(self):
        if not self.has_weapon:
            return "Flee"
        if self.stamina <= 30:
            return "Flee"
        if self.health > 50:
            if self.enemies_nearby < 3:
                return "Attack"
            else:
                return "Defend"
        else:
            return "Flee"

# Example usage
npc = NPC(health=60, enemies_nearby=2, stamina=40, has_weapon=False)
decision = npc.make_decision()
print(f"NPC Decision: {decision}")

Common Mistakes and Tips

  • Overcomplicating the Tree: Keep the decision tree as simple as possible. Overcomplicated trees can be hard to manage and understand.
  • Not Handling All Conditions: Ensure that all possible conditions are handled in the tree to avoid unexpected behavior.
  • Testing: Thoroughly test the decision tree with different scenarios to ensure it behaves as expected.

Conclusion

Decision trees are a powerful tool for implementing decision-making in video games. They provide a clear and structured way to represent decisions and their outcomes. By understanding the basics of decision trees and practicing their implementation, you can create more intelligent and responsive game characters.

In the next section, we will explore Behavior Trees, which offer a more flexible and scalable approach to decision-making in complex game environments.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved