地牢游戏DFS递归函数逻辑错误排查与修复

背景 #

开发地牢爬行游戏的玩家逃生模拟，计划用深度优先搜索（DFS）验证所有逃生路径是否均能成功，但Dungeon类的can_all_paths_make_it方法存在逻辑错误，导致单元测试失败。

测试失败详情 #

self = <main_test.GraphTest testMethod=test_can_all_paths_make_it>

    def test_can_all_paths_make_it(self):
        dungeon = self.create_dungeon()
>       self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)
E       AssertionError: True != False

coderbyte-tests/main_test.py:140: AssertionError
----------------------------- Captured stdout call -----------------------------
Checking node: <graph.Monster object at 0x7f82158aa190>, Current Health: 11
Checking neighbor: <graph.Monster object at 0x7f82158aa130>
Encountered Monster: <graph.Monster object at 0x7f82158aa130>
Checking node: <graph.Monster object at 0x7f82158aa130>, Current Health: 7
Checking neighbor: <graph.Monster object at 0x7f82158aa040>
Encountered Monster: <graph.Monster object at 0x7f82158aa040>
Checking node: <graph.Monster object at 0x7f82158aa040>, Current Health: 2
Checking neighbor: <graph.Treasure object at 0x7f8215914850>
Processing neighbor: <graph.Treasure object at 0x7f8215914850>
Checking node: <graph.Treasure object at 0x7f8215914850>, Current Health: 2
Found Treasure!

当前can_all_paths_make_it实现 #

初始版本：

# Will any path make it to the end? Can they choose randomly and always make it?
def can_all_paths_make_it(self, player: Player) -> bool:
    def dfs(node, current_health):
        if isinstance(node, Treasure):
            return True

        if current_health <= 0:
            return False
        
        if node is not node.next:
            return False
        
        for neighbor in node.next:
                if isinstance(neighbor, Monster):
                    # Simulate a battle with the monster
                    new_health = current_health - neighbor.damage
                    if not dfs(neighbor, new_health):
                        return False
                elif not dfs(neighbor, current_health):
                    return False

        return True

    return dfs(self.monster, player.health)

添加打印后的版本：

def can_all_paths_make_it(self, player: Player) -> bool:
    def dfs(node, current_health):
        print(f"Checking node: {node}, Current Health: {current_health}")

        if isinstance(node, Treasure):
            print("Found Treasure!")
            return True

        if current_health <= 0:
            print("Player has lost all health!")
            return False

        if not isinstance(node.next, list):
            print("Invalid path: node.next is not a list")
            return False  # If node.next is not a list, it's not a valid path

        for neighbor in node.next:
            print(f"Checking neighbor: {neighbor}")

            if isinstance(neighbor, Monster):
                print(f"Encountered Monster: {neighbor}")
                # Simulate a battle with the monster
                new_health = current_health - neighbor.damage
                if not dfs(neighbor, new_health):
                    return False
            elif not dfs(neighbor, current_health):
                return False

        return True

    return dfs(self.monster, player.health)

相关单元测试用例 #

import unittest

from graph import Monster, Treasure, Player, Dungeon

class GraphTest(unittest.TestCase):

    # a(3) -> b(4) -> c(5) -> treasure
    def create_dungeon(self) -> Dungeon:
        a = Monster("a", 3)
        b = Monster("b", 4)
        c = Monster("c", 5)
        treasure = Treasure()
        a.append_monster(b)
        b.append_monster(c)
        c.append_treasure(treasure)

        return Dungeon(a)

    # a(3) -> b(4)  c(5) -> treasure
    def create_dungeon2(self) -> Dungeon:
        a = Monster("a", 3)
        b = Monster("b", 4)
        c = Monster("c", 5)
        treasure = Treasure()
        a.append_monster(b)
        c.append_treasure(treasure)

        return Dungeon(a)

    # a(1) -> b(4)
    #   |      |
    #   v      v
    # c(2) -> d(1) -> treasure
    def create_dungeon3(self):
        a = Monster("a", 1)
        b = Monster("b", 4)
        c = Monster("c", 2)
        d = Monster("d", 1)
        treasure = Treasure()
        a.append_monster(b)
        a.append_monster(c)
        b.append_monster(d)
        c.append_monster(d)
        d.append_treasure(treasure)

        return Dungeon(a)

    # a(1) -> b(4) -> e(1)
    #   |      |
    #   v      v
    # c(2) -> d(1) -> treasure

    '''
    Probability review: Just because there are 2 different possiblilites does not 
    mean that they are equal probability. For example, on any given day, there could be 
    rain or no rain. That doesn't imply that rain has a 50% chance.

    In this case, there are 3 different paths:
    a->c->d->treasure, a->b->d->treasure, and a->b->e. 

    Here, a->c->d->tresure has a 50% chance of happening, a->b->e is 25%, and a->b->d->treasure is 25%. 
    An easy way to think about it that the probability of A reaching C is 50% and C reaching D is 100%
    and D reaching Treasure is 100%. Overall, it would be 50% chance to do A->C->D->Treasure.
    '''
    def create_dungeon4(self):
        a = Monster("a", 1)
        b = Monster("b", 4)
        c = Monster("c", 2)
        d = Monster("d", 1)
        e = Monster("e", 1)
        treasure = Treasure()
        a.append_monster(b)
        a.append_monster(c)
        b.append_monster(d)
        c.append_monster(d)
        b.append_monster(e)
        d.append_treasure(treasure)

        return Dungeon(a)

    # a(1) -> b(5) -> e(1) 
    #   |      |       |       
    #   v      v       v        
    # c(2) -> d(7) -> f(2) -> treasure
    # optimal -> a -> b -> e -> f
    def create_dungeon5(self):
        a = Monster("a", 1)
        b = Monster("b", 5)
        c = Monster("c", 2)
        d = Monster("d", 7)
        e = Monster("e", 1)
        f = Monster("f", 2)
        treasure = Treasure()
        a.append_monster(b)
        a.append_monster(c)
        b.append_monster(e)
        b.append_monster(d)
        c.append_monster(d)
        d.append_monster(f)
        e.append_monster(f)
        f.append_treasure(treasure)

        return Dungeon(a)

    # a(1) -> b(5) -> e(1) ------
    #   |      |       |        |
    #   v      v       v        v
    # c(2) -> d(7) -> f(2) -> treasure
    # optimal -> a -> b -> e -> f
    def create_dungeon6(self):
        a = Monster("a", 1)
        b = Monster("b", 5)
        c = Monster("c", 2)
        d = Monster("d", 7)
        e = Monster("e", 1)
        f = Monster("f", 2)
        treasure = Treasure()
        a.append_monster(b)
        a.append_monster(c)
        b.append_monster(e)
        b.append_monster(d)
        c.append_monster(d)
        d.append_monster(f)
        e.append_monster(f)
        e.append_treasure(treasure)
        f.append_treasure(treasure)

        return Dungeon(a)

    def test_can_at_least_one_path_make_it(self):
        dungeon = self.create_dungeon()
        self.assertEqual(dungeon.can_at_least_one_path_make_it(), True)
        
        dungeon = self.create_dungeon2()
        self.assertEqual(dungeon.can_at_least_one_path_make_it(), False)


    def test_can_all_paths_make_it(self):
        dungeon = self.create_dungeon()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)

        dungeon = self.create_dungeon()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(12)), True)

        dungeon = self.create_dungeon2()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(7)), False)
        
        dungeon = self.create_dungeon3()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(5)), False)

        dungeon = self.create_dungeon3()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(6)), True)

        dungeon = self.create_dungeon4()
        self.assertEqual(dungeon.can_all_paths_make_it(Player(100)), False)

    def test_probability_player_will_make_it(self):
        dungeon = self.create_dungeon()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(12)), 1.0)

        dungeon = self.create_dungeon()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(11)), 0.0)
        
        dungeon = self.create_dungeon2()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.0)

        dungeon = self.create_dungeon3()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)

        dungeon = self.create_dungeon3()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)

        dungeon = self.create_dungeon3()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 1.0)

        dungeon = self.create_dungeon4()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)

        dungeon = self.create_dungeon4()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)

        dungeon = self.create_dungeon4()
        self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.75)

    def test_can_make_it(self):
        dungeon = self.create_dungeon5()
        self.assertEqual(dungeon.can_make_it(Player(9)), True)

        dungeon = self.create_dungeon5()
        self.assertEqual(dungeon.can_make_it(Player(8)), False)

        dungeon = self.create_dungeon6()
        self.assertEqual(dungeon.can_make_it(Player(7)), True)

        dungeon = self.create_dungeon6()
        self.assertEqual(dungeon.can_make_it(Player(6)), False)

问题分析与修复方案 #

核心问题 #

1. 生命值扣除时机错误：当前代码在处理Monster邻居时才扣血，而非进入Monster节点时。比如测试用例中，玩家进入c节点（伤害5）时，当前生命值是7（11-3-4），但代码未扣除c的伤害就直接处理Treasure邻居，导致误判路径有效。
2. 未处理死路情况：当节点不是Treasure且无后续节点时，属于死路，当前代码未判定这种情况为路径失败。
3. 初始版本的无效判断：if node is not node.next: return False完全错误，node.next是邻接列表，节点不可能等于自身的邻接列表，会导致DFS提前终止。

修复后的代码 #

def can_all_paths_make_it(self, player: Player) -> bool:
    def dfs(node, current_health):
        print(f"Checking node: {node}, Current Health: {current_health}")

        # 到达宝藏，路径有效
        if isinstance(node, Treasure):
            print("Found Treasure!")
            return True

        # 当前节点是怪物，立即扣除伤害
        if isinstance(node, Monster):
            current_health -= node.damage
            print(f"Encountered Monster: {node}, New Health: {current_health}")
            # 扣血后生命值不足，路径无效
            if current_health <= 0:
                print("Player has lost all health!")
                return False

        # 判定死路：非宝藏且无后续节点
        if not isinstance(node.next, list) or len(node.next) == 0:
            print("Dead end: no path to treasure")
            return False

        # 遍历所有邻居，所有路径必须都有效才返回True
        for neighbor in node.next:
            print(f"Checking neighbor: {neighbor}")
            if not dfs(neighbor, current_health):
                return False

        return True

    return dfs(self.monster, player.health)

修复说明 #

1. 调整生命值扣除时机：进入Monster节点时立即扣除伤害，确保生命值状态正确反映玩家当前节点后的状态。
2. 新增死路判断：当节点不是Treasure且无后续节点时，直接返回False，标记该路径为失败。
3. 简化邻居处理：不管邻居类型，直接递归调用DFS，Monster的伤害会在进入该节点时处理，无需在邻居遍历阶段重复操作。

修改后，针对create_dungeon测试用例，玩家生命值11时：

• 进入a节点，生命值11-3=8
• 进入b节点，生命值8-4=4
• 进入c节点，生命值4-5=-1，此时返回False，整个DFS最终返回False，符合单元测试预期。

内容的提问来源于stack exchange，提问作者LearningLittleByLittle