使用A*搜索算法解决忒修斯和牛头怪难题

Question

我最近观看了这个视频，它使用 BFS 搜索算法解决了忒修斯和牛头怪难题。如果你不熟悉的话，这是一个谜题，忒修斯和牛头怪被放在一个瓷砖迷宫里，忒修斯必须在不被牛头怪抓住的情况下逃脱。忒修斯每移动一格，牛头怪就会移动两次。然而牛头怪的行为是这样的，它只能直接向忒修斯移动，并且在尝试垂直移动之前它总是会先尝试水平移动。因此，可以利用这一点来逃离迷宫。如果您有兴趣尝试玩游戏，可以在here找到该游戏的一个很好的实现。

我现在尝试在 Kotlin 中实现我自己的求解器，但使用 A* 算法而不是 BFS。但是，我在这样做时遇到了麻烦，并且我不确定为什么我的代码不起作用。与传统的 A* 算法不同，传统的 A* 算法有一个节点对象来存储代理的位置，但我有一个状态对象来存储Theseus 和 Minotaur 的位置。然后，我使用一系列辅助函数来确定Theseus 和 Minotaur 的下一个可能位置，这样Theseus 就不会撞到墙壁、走出迷宫或进入 Minotaur（函数 getNextStates）。从这里开始，我使用 A* 算法的相当传统的实现，该算法仅考虑Theseus 的位置（函数 aStar），并使用辅助函数根据Theseus 相对于目标的位置来计算启发式。这是我的代码：

data class Position(val x: Int, val y: Int)
data class State(val theseusPos: Position, val minotaurPos: Position)

// Manhattan distance heuristic
fun heuristic(point: Position, goal: Position): Int {
    return Math.abs(point.x - goal.x) + Math.abs(point.y - goal.y)
}

// Checks if a given position is valid: if it is within the maze, and it is an empty space
fun isPositionValid(pos: Position, maze: Array<IntArray>): Boolean {
    return pos.y in 0 until maze.size && pos.x in 0 until maze[0].size && maze[pos.y][pos.x] == 0;
}

// Returns the next possible neighbors given the current node and a maze
fun getNextTheseusPositions(current: Position, maze: Array<IntArray>): List<Position> {
    val moves = listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)
    val states = mutableListOf<Position>();

    for ((dx, dy) in moves) {
        val x = current.x + dx
        val y = current.y + dy
        val neighbor = Position(x, y)

        if (isPositionValid(neighbor, maze)) { 
            states.add(neighbor)
        }
    }

    return states
}

// Return change in x or y based on given horizontal/vertical coordinates
fun moveMinotaur(minotaurCoord: Int, theseusCoord: Int): Int {
    return when {
        minotaurCoord < theseusCoord -> 1
        minotaurCoord > theseusCoord -> -1
        else -> 0
    }
}

fun getNextMinotaurPosition(minotaurPos: Position, theseusPos: Position, maze: Array<IntArray>): Position {
    var currMinotaurX = minotaurPos.x;
    var currMinotaurY = minotaurPos.y;

    for(i in 0 until 2) {
        val dx = moveMinotaur(currMinotaurX, theseusPos.x)
        if(dx != 0 && isPositionValid(Position(currMinotaurX + dx, currMinotaurY), maze)) {
            currMinotaurX += dx
            continue
        }

        val dy = moveMinotaur(currMinotaurY, theseusPos.y)
        if(dy != 0 && isPositionValid(Position(currMinotaurX, currMinotaurY + dy), maze)) {
            currMinotaurY += dy
        }
    }

    return Position(currMinotaurX, currMinotaurY)
}

// Returns next possible states
fun getNextStates(state: State, maze: Array<IntArray>): List<State> {
    val states = mutableListOf<State>();

    // Adding possible states based on whether or not the minotaur gets to Theseus
    for(theseusPos in getNextTheseusPositions(state.theseusPos, maze)) {
        val minotaurPos = getNextMinotaurPosition(state.minotaurPos, theseusPos, maze)

        if(minotaurPos == theseusPos) {
            continue
        }

        states.add(State(theseusPos, minotaurPos))
    }

    return states
}

fun aStar(maze: Array<IntArray>, start: State, goal: Position): List<State>? {
    // Stores nodes based on priority (cost), based on how close they are to the goal
    // and how many steps they are from the starting point
    val openSet = PriorityQueue(compareBy<Pair<Int, State>> { it.first })
    openSet.add(0 to start)
    // Map that tracks previous state for each state so that the route can be reconstructed
    val cameFrom = mutableMapOf<State, State>()
    // gScore cost for each theseus position
    val gScore = mutableMapOf(start.theseusPos to 0)
    
    // Main loop, runs until priority queue is empty (all nodes have been processed)
    while (openSet.isNotEmpty()) {
        // Gets pair at front of queue, where current is the current Position
        val (_, current) = openSet.poll()

        // If we find the goal, reconstruct the path and return
        if (current.theseusPos == goal) {
            val path = mutableListOf<State>()
            var cur: State? = current
            // Reconstruct the path using the parent node from each node, reversed to get the original path
            while (cur != null) {
                path.add(cur)
                cur = cameFrom[cur]
            }
            path.reverse()
            return path
        }

        for (state in getNextStates(current, maze)) {
        // The gScore of moving from the current node to its neighbour is just the score
        // of the current node + 1, since moving from one tile to another has a uniform cost
        // of 1
            val tentativeG = gScore[current.theseusPos]!! + 1

            if (!gScore.containsKey(state.theseusPos) || tentativeG < gScore[state.theseusPos]!!) {
                gScore[state.theseusPos] = tentativeG
                val fScore = tentativeG + heuristic(state.theseusPos, goal)
                openSet.add(fScore to state)
                cameFrom[state] = current
            }
        }
    }

    // If all nodes have been explored and a path has not been found, return null
    return null
}

目前，我正在调用这样的函数，它打印“null”表示未找到路径：

fun main() {
    val maze = arrayOf(
        intArrayOf(0, 1, 0, 0, 0, 0, 0, 0),
        intArrayOf(0, 1, 0, 1, 0, 1, 1, 1),
        intArrayOf(0, 0, 0, 1, 0, 0, 0, 0),
        intArrayOf(1, 1, 0, 1, 0, 1, 1, 0),
        intArrayOf(0, 0, 0, 1, 0, 0, 0, 0),
        intArrayOf(1, 0, 1, 1, 0, 1, 0, 1),
        intArrayOf(0, 0, 1, 0, 0, 1, 0, 0)
    )

    val start = State(Position(1, 2), Position(5, 2))
    val goal = Position(7, 0)

    val path = aStar(maze, start, goal)
    println(path)
}

迷宫是这样的（忒修斯的起始位置用篮球标记，牛头怪用手标记）：

迷宫绝对是可能的，因为它是基于原始视频中使用的迷宫这里

我已经广泛测试了每个辅助函数，它们都按预期工作（除了 aStar 之外的每个函数）。我还在添加辅助函数之前实现了 A* 算法，如果不考虑牛头怪，该算法就可以工作。我尝试为每个循环打印优先级队列前面的位置，似乎Theseus 被困在迷宫的角落里，无法回溯，尽管我可能解释错误。我最近才学这个算法，所以我觉得我还没有完全理解它是如何工作的。

如果您有任何建议或需要澄清，请告诉我。

Answer 1

这是我看到的错误。

1. Theseus 等不及你的解算器了。他站在原地也是正当的。也就是说，您需要移动

   0 to 0

   。
2. 牛头怪可以在解算器中的目标处抓住忒修斯。但在游戏中，即使牛头怪能追上，忒修斯只要射门就获胜。所以在

   getNextStates

   中，不要失去牛头怪在球门处抓住忒修斯的状态。
3. 你缺少墙壁。游戏中有牛头怪和忒修斯无法穿过的墙。您需要一个表示，让您注意到您不仅需要合法的开始和结束位置，还需要没有穿过墙壁。
4. 你的

   gScore

   需要是该州的分数，而不是忒修斯所在位置的分数。您游戏中的获胜路径是

   lddrdduuluuuuurrrrr

   。 （l = 左，r = 右，u = 上，d = 下，w = 等待）忒修斯在困住牛头怪后需要被允许原路返回。这不是一个重复的位置，因为牛头怪被困住很重要。