DFS Algorithm Visualization for Maximum Bomb Chain

Game Grid (Placement Mode)

Grid size: 10x10

Total bombs: 0

DFS Algorithm Visualization

Place some bombs on the grid to start.

How It Works

This visualizer demonstrates a Depth-First Search (DFS) algorithm to find the maximum chain of bomb detonations in a Bomberman-like game.

Bomb Chain Logic

  • Each bomb has a position (x, y) and a radius (R).
  • A bomb can detonate another bomb if the Manhattan distance between them is less than or equal to the radius of the first bomb.
  • Manhattan distance is calculated as |x1 - x2| + |y1 - y2|.
  • The algorithm builds a graph where bombs are connected if one can detonate another.
  • DFS is used to find all bombs that would detonate in a chain reaction from each starting bomb.
  • The maximum chain is the longest chain found across all possible starting bombs.

DFS Algorithm

  • DFS uses a stack data structure to keep track of nodes to visit.
  • It explores as far as possible along each branch before backtracking.
  • The algorithm marks each bomb as visited to avoid cycles.
  • For each bomb, it adds all unvisited neighbors (bombs it can detonate) to the stack.
  • The process continues until the stack is empty, meaning all reachable bombs have been explored.

Instructions:

  1. Place bombs on the grid by clicking in "Place Bombs" mode
  2. Click "Visualize Maximum Chain" to see the DFS algorithm in action
  3. Watch as the algorithm finds the maximum possible chain reaction
  4. The final result will highlight the maximum chain in purple