Kotlin 用A*搜索算法解决特修斯和米诺陶尔难题

我最近看了这个video，它使用BFS搜索算法来解决特修斯和米诺陶谜题.如果你不熟悉它，这是一个谜题，特修斯和牛头人被放在一个瓷砖迷宫中，特修斯必须在不被牛头人抓住的情况下逃脱.特修斯每移动一块瓷砖，牛头人就会移动两次.然而，牛头人的行为是这样的，它只能直接向特修斯移动，在try 垂直移动之前，它总是会try 水平移动.因此，可以利用这一点来逃离迷宫.如果你有兴趣try 玩这个游戏，你可以在here中找到一个很好的游戏实现.

我现在正try 用Kotlin实现我自己的求解器，但使用的是A*算法而不是BFS.然而，我在这样做时遇到了问题，我不确定为什么我的代码不能工作.在传统的A*算法中，有一个 node 对象来存储代理的位置，而我有一个状态对象来存储提修斯和牛头人的位置.然后，我使用一系列助手函数来确定提修斯和牛头人下一个可能的位置，这样提修斯就不会撞到墙壁、走出迷宫或进入牛头人(函数getNextState).从那里，我使用了A*算法的一个非常传统的实现，它只考虑提修斯的位置(函数astar)，并使用一个助手函数根据提修斯从球门到球门的位置来计算启发式.以下是我的代码:

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)
}

下面是迷宫的样子(特修斯的起跑位置用篮球标记，牛头怪用手标记):Image link

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

我已经广泛地测试了每个助手函数，它们都能正常工作(除了ASSTAR之外的每个函数).在添加助手函数之前，我还实现了A*算法，如果不考虑牛头怪，它就会起作用.我试着 for each 循环打印优先级队列前面的位置，看起来特修斯似乎被困在迷宫的角落里，无法回溯，尽管我可能解释错了.我最近才学会这个算法，所以我觉得我仍然不能完全理解它是如何工作的.

如果您有任何建议或需要澄清，请让我知道.