Explore

The BFS solver, step by step

The thesis checks every floor with an exact breadth-first search (BFS). It turns a floor into a graph of nodes (monsters, doors and merged groups of items) and searches over the sets of nodes the hero has cleared. Every state is a cleared set with the hero's HP, attack, defence and keys. Step through the search and watch which states it keeps.

The search runs in your browser. On the complex floor and hand03 it takes minutes and a lot of memory, so those two show the stored result of the same search instead.

Search graph
node 0: start (5,0) (cleared in this state)node 1: Red Gem (+1 ATK) (1,0) +1node 1: Red Gem (+1 ATK) (1,0) +1node 2: yellow door (7,0) +2node 2: yellow door (7,0) +224node 2: yellow door (7,0) +2 Green Slime: HP 50 ATK 7 DEF 3 gold 0 costs 24 HP to kill now114node 3: Slime Lord (2,1) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill now114node 3: Slime Lord (2,1) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill nownode 4: Yellow Key (5,1)node 5: Red Gem (+1 ATK) (9,1) +2node 5: Red Gem (+1 ATK) (9,1) +2node 5: Red Gem (+1 ATK) (9,1) +2node 6: Red Gem (+1 ATK) (1,3) +2node 6: Red Gem (+1 ATK) (1,3) +2node 6: Red Gem (+1 ATK) (1,3) +256node 7: Red Slime (5,3) Red Slime: HP 70 ATK 11 DEF 1 gold 0 costs 56 HP to kill now55node 8: Black Slime (6,4) Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill nownode 9: Blue Gem (+1 DEF) (10,4) +1node 9: Blue Gem (+1 DEF) (10,4) +1182node 10: Bat (3,5) Bat: HP 100 ATK 17 DEF 2 gold 0 costs 182 HP to kill nownode 11: yellow door (7,5)55node 12: Black Slime (9,5) Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill now24node 13: Green Slime (5,6) Green Slime: HP 50 ATK 7 DEF 3 gold 0 costs 24 HP to kill nownode 14: Blue Gem (+1 DEF) (0,7) +1node 14: Blue Gem (+1 DEF) (0,7) +155node 15: Black Slime (3,7) +1 Black Slime: HP 45 ATK 5 DEF 5 gold 0 costs 55 HP to kill nownode 15: Black Slime (3,7) +1node 16: Red Potion (+75 HP) (7,7)56node 17: Red Slime (10,7) +1 Red Slime: HP 70 ATK 11 DEF 1 gold 0 costs 56 HP to kill now114node 17: Red Slime (10,7) +1 Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill nownode 18: Yellow Key (2,8) +2node 18: Yellow Key (2,8) +2node 18: Yellow Key (2,8) +2114node 19: Slime Lord (1,9) Slime Lord: HP 80 ATK 10 DEF 5 gold 0 costs 114 HP to kill now182node 20: Bat (5,9) Bat: HP 100 ATK 17 DEF 2 gold 0 costs 182 HP to kill now!node 21: Boss (5,10) Boss: HP 50 ATK 20 DEF 12 gold 0 cannot be beaten at the hero's ATKnode 22: Red Gem (+1 ATK) (7,10) +1node 22: Red Gem (+1 ATK) (7,10) +1

One frame per node over the game's tiles: monsters red (boss purple), doors in their colour, items green, the start gold; cleared nodes are filled and their tiles emptied. Items next to each other are merged into one node (dashed lines), as are chains of monsters and doors with nothing else attached. Lines join nodes the hero can walk between. Numbers give the order of the decisions in the state shown (the hero marks the start; items picked up on the way are not numbered): the state just taken from the queue, and once the search ends the best state. Gold ring: the nodes it can take next. The number on a monster is the HP it costs to kill at the hero's current stats (green: affordable, red: not, !: cannot be beaten). Hover a tile for its node and monster stats.

HP470start 470
ATK / DEF9 / 4
Keys0 / 0 / 0yellow / blue / red
Expanded00 taken from the queue
Queue10 queued in total
Skipped0set already expanded with ≥ HP
Best so far–optimum 13
What the search did (newest first)

Press step to take the first state from the queue.

Exact search. States are taken in order of decisions (breadth first), most HP first. A set of cleared monsters and doors is expanded again only if a later state reaches it with more HP, so no better route is thrown away.

Published search. The solver released with the test maps keeps the first state it takes for each set. On this floor both find 13 HP; on the complex floor the published search reports 22 HP and the exact search 68.