Abstract
Artificial Intelligence (AI) seeks to bring intelligent behavior for machines by using specific techniques. These techniques can be employed in order to solve tasks, such as planning paths or controlling intelligent agents. Some tasks that use AI techniques are not trivially testable, since it can handle a high number of variables depending on their complexity. As digital games can provide a wide range of variables, they become an efficient and economical means for testing artificial intelligence techniques. In this paper, we propose a combination of a behavior tree and a Pathfinding algorithm to solve a maze-based problem using the digital game Bomberman of the Nintendo Entertainment System (NES) platform. We perform an analysis of the AI techniques in order to verify the feasibility of future experiments in similar complex environments. Our experiments show that our intelligent agent can be successfully implemented using the proposed approach.
Introduction
The challenge of testing Artificial Intelligence in complex, dynamic environments is significant. While real-world testing is often prohibitively expensive or difficult, digital games provide a rich, measurable proxy. This study presents an intelligent agent capable of beating the classic NES game Bomberman by combining high-level decision-making via Behavior Trees with low-level navigation using pathfinding algorithms.
Bomberman is characterized by a massive state space (approximately $10^{602}$ possible states), real-time constraints, and stochastic elements like random enemy movements. To "beat" the game, an agent must perceive the environment, prioritize objectives (like avoiding explosions vs. hunting enemies), and navigate a changing maze—tasks that mirror real-world robotics and autonomous systems.
Methodology
The researchers implemented a hybrid architecture to control the "Intelligent Agent" consisting of two primary components: a Behavior Tree and Pathfinding algorithms.
Behavior Tree (BT)
The Behavior Tree serves as the decision-making "brain," following a hierarchical logic to prioritize actions based on the current state of the game. The priority sequence is:
- Safety First: If a bomb is present, find a safe spot and wait.
- Resource Acquisition: If safe, look for power-ups.
- Objective Completion: If no items are available, hunt reachable enemies.
- Progression: If enemies are dead, find and reach the exit.
Pathfinding Algorithms
For any "Go to..." action triggered by the Behavior Tree, the agent uses one of two algorithms to navigate the grid:
- Breadth-First Search (BFS): An uninformed search that explores all possible directions equally.
- A-Star (A*): An informed search using a Manhattan distance heuristic ($h(n) = |x_1 - x_2| + |y_1 - y_2|$) to find the goal more efficiently.
The system was built using the FCEUX emulator, allowing the AI to interface directly with the NES game code at 60 frames per second (FPS).
Experimental Setup
As this is a study on agent-environment interaction, the benchmark was the game Bomberman itself. The authors evaluated performance on Stage 1 (no power-ups) and Stage 31 (advanced power-ups like fire invulnerability) to compare the AI against human performance.
Analysis and Results
The study yielded several key insights regarding computational efficiency and reliability:
- Computational Efficiency: The choice of pathfinding algorithm significantly impacts performance. A* maintained a much higher frame rate (up to 800 FPS) compared to BFS, which dropped as low as 20 FPS because it exhaustively searched the map.
- Reliability vs. Intuition: While the human subject cleared stages faster on average, they failed (died) in four separate trials. The AI, though slightly slower, never died, highlighting the trade-off between human-like "risky" efficiency and algorithmic "safe" consistency.
- Success Rate: Both BFS and A* implementations successfully cleared all enemies and found the exit in every test stage.
Conclusion
The proposed approach successfully demonstrates that a combination of Behavior Trees and pathfinding can navigate the complex environment of Bomberman. While the current agent follows a fixed, hand-coded behavior tree, future work aims to incorporate more sophisticated knowledge representation, multi-agent systems, and eventually transpose these techniques into physical robotics operating in real-world mazes.
Summary updated