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