AI.Bootcamp

Context

As part of the Artificial Intelligence Applied to Video Games course in the Master’s in Video Game Development at the University of Sherbrooke (DDJV), taught by Carle Côté, we solved a programming challenge known as AI.Bootcamp.

AI.Bootcamp is a dedicated challenge designed to help developers learn and experiment with advanced AI concepts in a gaming environment.

Team Members:

Rules

AI.Bootcamp features numerous levels. Every time the level counter reaches a new decade (e.g., 10, 20, 30), a new mechanic is introduced.

Basic rules

The primary goal is to move NPCs to objective tiles while staying within a turn limit and a CPU time budget. NPCs can perform one action per turn:

  • Move to an adjacent tile
  • Search for a hidden door (within a wall)
  • Open a door

NPCs are also subject to specific constraints:

  • Two NPCs cannot occupy the same tile.
  • NPCs cannot step on red tiles.
  • NPCs cannot pass through walls or closed doors.
NPCs and tiles
NPCs and tile types

Levels 000 - 005: Basic Cases

The initial levels can be solved with straightforward logic.

Level 005 - No Limits
Level 005 - No Limits

Levels 010 - 013: Pathfinding

The 01x levels require implementing a pathfinding algorithm and ensuring that NPCs do not collide or overlap.

Level 012 - PathFollowing or Fail!
Level 012 - PathFollowing or Fail!

Levels 020 - 023: Walls and Windows

The 02x levels introduce obstacles like walls and windows. The key difference is that windows allow NPCs to see through them, which becomes essential in non-omniscient levels.

Level 022 - Walls and Windows
Level 022 - Walls and Windows

Levels 030 - 034: Non-Omniscient Fog of War

From level 030 onwards, levels are non-omniscient. Previously, NPCs had full knowledge of the entire map; now, they have a limited, variable field of vision.

Level 032 - Still not connected
Level 032 - Still not connected

Levels 040 - 042: Strategic Use of Windows

Levels 040 to 042 force the intelligent use of windows to gather as much information as possible about the environment.

Level 041 - Goal Traps II
Level 041 - Goal Traps II

Level 050: The Maze

Level 050 combines most of the learned mechanics to navigate a massive maze with very limited visibility.

Level 050 - a-MAZE-ing!
Level 050 - a-MAZE-ing!

Levels 060 - 066: Doors

The 06x levels introduce various types of doors:

  • Manual Doors: The NPC can use the Open Door action and pass through on the following turn.
  • Pressure Plate Doors: Each plate is linked to a specific door that stays open only while the plate is triggered.
  • Hidden Doors: NPCs must use the Search for hidden door action on walls. If discovered, the door must then be opened before crossing.
Level 066 - Good Luck
Level 066 - Good Luck

Levels 070 - 073: Cooperation

Levels 070 and above emphasize cooperation: avoiding tile conflicts and helping fellow NPCs (e.g., one NPC holding a pressure plate so another can pass).

Level 072 - Not so simple!
Level 072 - Not so simple!

Levels 080 - 083: Optimization

The final levels introduce strict optimization constraints. All processing for a turn must be completed in under 15ms.

Level 081 - Not so a-MAZE-ing! - Optim
Level 081 - Not so a-MAZE-ing! - Optimization focus

Our Solution

For every turn, our solution follows this workflow:

  • Global Map Update: Updating the “Fog of War” and shared world knowledge.
  • HiveMind: A high-level controller that manages task distribution (collaboration, exploration) using a Behavior Tree.
  • Individual NPCs: Each NPC follows its assigned task via its own Behavior Tree. Calculations for all NPCs are performed in parallel.
  • Conflict Resolution: A final step to resolve instances where multiple NPCs attempt to move to the same tile.
Solution Architecture
Architecture of our AI solution

Our pathfinding algorithm is based on A*, modified to account for doors and different tile costs.

Source Code

AI.Bootcamp

Download the AI.Bootcamp solution.

Source Code