KMP鸿蒙跨端迷宫生成与求解系统实战

程序猿里奥 1
Viewed 0

本文档介绍如何在 Kotlin Multiplatform (KMP) 鸿蒙跨端开发中实现一个完整的迷宫生成和求解系统。这个案例展示了如何使用 Kotlin 的递归算法、图论和搜索算法来创建一个功能丰富的迷宫工具。通过 KMP，这个工具可以无缝编译到 JavaScript，在 OpenHarmony 应用中运行，并支持用户输入进行实时处理。

该工具具备以下特点：

  • 迷宫生成：使用递归回溯算法生成随机迷宫，支持 3×3 到 10×10 的大小范围，每次生成不同的迷宫。
  • 路径求解：使用 BFS 算法找到最短路径，并显示从起点到终点的步数，同时判断迷宫的可解性。
  • 可视化展示：用 ASCII 字符清晰展示迷宫和路径，其中 S 表示起点，E 表示终点。
  • 统计分析：分析迷宫的结构特性，包括总格子数、墙数量、通路数及其百分比。
  • 跨端兼容：一份 Kotlin 代码可同时服务多个平台，实现跨端开发。

核心实现

迷宫网格初始化

首先，初始化迷宫的基础数据结构。创建一个 size × size 的二维整数数组 maze，所有元素初始化为 1（表示墙）。同时创建一个同样大小的布尔数组 visited，用于追踪在递归回溯过程中已访问的单元格。这种初始化方式确保了迷宫最初是完全被墙包围的，然后通过算法逐步打通通路。

val maze = Array(size) { IntArray(size) { 1 } }
val visited = Array(size) { BooleanArray(size) { false } }

递归回溯生成迷宫

递归回溯算法用于生成迷宫。首先标记当前单元格为已访问，并将其设置为通路（0）。定义四个方向的移动向量，每次移动 2 个单位以保留墙。使用 shuffled() 随机打乱方向顺序，确保生成的迷宫具有随机性。对于每个方向，检查目标单元格是否在边界内且未被访问。如果满足条件，打通当前单元格和目标单元格之间的中间墙，然后递归地对目标单元格调用 carvePath()。这个算法生成的迷宫具有完美的连通性，即每个单元格都可以从任何其他单元格到达。

fun carvePath(x: Int, y: Int) {
    visited[x][y] = true
    maze[x][y] = 0

    val directions = listOf(
        Pair(-2, 0),
        Pair(0, 2),
        Pair(2, 0),
        Pair(0, -2)
    )

    val shuffled = directions.shuffled()

    for ((dx, dy) in shuffled) {
        val nx = x + dx
        val ny = y + dy

        if (nx in 0 until size && ny in 0 until size && !visited[nx][ny]) {
            maze[x + dx / 2][y + dy / 2] = 0
            carvePath(nx, ny)
        }
    }
}

迷宫统计

计算迷宫的统计信息，包括总格子数、墙数量、通路数及其百分比。这些统计数据可以用来评估迷宫的难度和结构特性。

val totalCells = size * size
val wallCount = maze.sumOf { row -> row.count { it == 1 } }
val pathCount = totalCells - wallCount
val wallPercent = (wallCount * 100) / totalCells
val pathPercent = (pathCount * 100) / totalCells

BFS 路径求解

广度优先搜索（BFS）算法用于求解迷宫。创建一个队列用于存储待探索的单元格，创建一个 Map 用于存储每个单元格的父节点（用于路径回溯），创建一个布尔数组追踪已访问的单元格。初始化起点 (0, 0) 到队列中。使用 while 循环处理队列中的每个单元格。当到达终点 (size-1, size-1) 时，通过父节点 Map 回溯路径。对于每个单元格，探索四个方向的相邻单元格。如果相邻单元格在边界内、未被访问且是通路，则标记为已访问、记录父节点、添加到队列。如果队列为空且未找到终点，则返回 null（迷宫无解）。BFS 算法保证找到的是最短路径。

fun solveMaze(): List<Pair<Int, Int>>? {
    val queue = mutableListOf<Pair<Int, Int>>()
    val parent = mutableMapOf<Pair<Int, Int>, Pair<Int, Int>?>()
    val visited2 = Array(size) { BooleanArray(size) { false } }

    queue.add(Pair(0, 0))
    visited2[0][0] = true
    parent[Pair(0, 0)] = null

    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeAt(0)

        if (x == size - 1 && y == size - 1) {
            // 回溯路径
            val path = mutableListOf<Pair<Int, Int>>()
            var current: Pair<Int, Int>? = Pair(x, y)

            while (current != null) {
                path.add(0, current)
                current = parent[current]
            }
            return path
        }

        // 探索四个方向
        for ((dx, dy) in directions) {
            val nx = x + dx
            val ny = y + dy

            if (nx in 0 until size && ny in 0 until size &&
                !visited2[nx][ny] && maze[nx][ny] == 0) {
                visited2[nx][ny] = true
                parent[Pair(nx, ny)] = Pair(x, y)
                queue.add(Pair(nx, ny))
            }
        }
    }

    return null
}

ASCII 可视化

将迷宫转换为 ASCII 字符串用于显示，使迷宫结构清晰易读。起点显示为 “S”，终点显示为 “E”，墙显示为 “█” 符号，通路显示为空格。

val mazeStr = maze.mapIndexed { i, row ->
    "  " + row.mapIndexed { j, cell ->
        when {
            i == 0 && j == 0 -> "S"
            i == size - 1 && j == size - 1 -> "E"
            cell == 1 -> "█"
            else -> " "
        }
    }.joinToString("")
}.joinToString("\n")

实战案例：完整的迷宫生成和求解器

以下是一个完整的 Kotlin 源代码示例，实现了迷宫生成和求解器，并通过 @JsExport 注解使其可编译到 JavaScript，供鸿蒙应用调用。

@OptIn(ExperimentalJsExport::class)
@JsExport
fun mazeGenerator(inputSize: String = "5"): String {

    val size = inputSize.trim().toIntOrNull() ?: 5

    if (size < 3) {
        return "❌ 错误: 迷宫大小必须至少为 3"
    }

    if (size > 10) {
        return "❌ 错误: 迷宫过大"
    }


    val maze = Array(size) { IntArray(size) { 1 } }
    val visited = Array(size) { BooleanArray(size) { false } }


    fun carvePath(x: Int, y: Int) {
        visited[x][y] = true
        maze[x][y] = 0

        val directions = listOf(
            Pair(-2, 0), Pair(0, 2), Pair(2, 0), Pair(0, -2)
        )

        for ((dx, dy) in directions.shuffled()) {
            val nx = x + dx
            val ny = y + dy

            if (nx in 0 until size && ny in 0 until size && !visited[nx][ny]) {
                maze[x + dx / 2][y + dy / 2] = 0
                carvePath(nx, ny)
            }
        }
    }

    carvePath(0, 0)
    maze[0][0] = 0
    maze[size - 1][size - 1] = 0


    val totalCells = size * size
    val wallCount = maze.sumOf { row -> row.count { it == 1 } }
    val pathCount = totalCells - wallCount


    fun solveMaze(): List<Pair<Int, Int>>? {
        val queue = mutableListOf<Pair<Int, Int>>()
        val parent = mutableMapOf<Pair<Int, Int>, Pair<Int, Int>?>()
        val visited2 = Array(size) { BooleanArray(size) { false } }

        queue.add(Pair(0, 0))
        visited2[0][0] = true
        parent[Pair(0, 0)] = null

        while (queue.isNotEmpty()) {
            val (x, y) = queue.removeAt(0)

            if (x == size - 1 && y == size - 1) {
                val path = mutableListOf<Pair<Int, Int>>()
                var current: Pair<Int, Int>? = Pair(x, y)
                while (current != null) {
                    path.add(0, current)
                    current = parent[current]
                }
                return path
            }

            for ((dx, dy) in listOf(Pair(-1, 0), Pair(0, 1), Pair(1, 0), Pair(0, -1))) {
                val nx = x + dx
                val ny = y + dy

                if (nx in 0 until size && ny in 0 until size &&
                    !visited2[nx][ny] && maze[nx][ny] == 0) {
                    visited2[nx][ny] = true
                    parent[Pair(nx, ny)] = Pair(x, y)
                    queue.add(Pair(nx, ny))
                }
            }
        }

        return null
    }

    val solution = solveMaze()
    val solutionLength = solution?.size ?: 0


    return "🎮 迷宫生成和求解器\n" +
           "━━━━━━━━━━━━━━━━━━━━━\n" +
           "1️⃣ 迷宫信息:\n" +
           "  大小: ${size}×${size}\n" +
           "  总格子数: $totalCells\n" +
           "  墙数量: $wallCount\n" +
           "  通路数: $pathCount\n\n" +
           "2️⃣ 求解信息:\n" +
           "  是否可解: ${if (solution != null) "✅ 是" else "❌ 否"}\n" +
           "  路径长度: $solutionLength 步\n\n" +
           "✅ 生成完成！"
}

在鸿蒙应用中，可以使用 ArkTS 调用上述编译后的 Kotlin 函数。ArkTS 代码负责用户界面，包括输入框、按钮和结果展示，而迷宫生成和求解逻辑完全由 Kotlin 处理，实现了清晰的前后端分离。

编译过程详解

Kotlin 代码通过 KMP 编译到 JavaScript，关键转换包括：

  • 多维数组（如 Array<IntArray>）转换为 JavaScript 的嵌套数组。
  • 集合操作（如 shuffled()）转换为 JavaScript 数组方法。
  • 递归算法直接转换为 JavaScript 递归函数。
  • BFS 搜索中的队列使用 JavaScript 数组实现。

工具扩展

为了增强功能，可以添加以下扩展：

  1. DFS 求解：实现深度优先搜索算法，代码更简洁，但找到的路径不一定最短。
  2. 迷宫难度评分：根据墙比例和路径长度计算难度等级，帮助用户选择合适的迷宫。
  3. 多个出口：生成随机额外出口，增加迷宫的复杂性和趣味性。
  4. 迷宫导出：将迷宫转换为字符串格式，便于保存和传输。

最佳实践

  • 使用递归回溯生成迷宫：这是生成完美迷宫的标准方法，确保良好的连通性和复杂性，优于简单随机生成。
  • 使用 BFS 找最短路径：BFS 保证找到最短路径，适合迷宫求解；而 DFS 可能找到非最短路径。
  • 检查边界条件：在创建迷宫前验证大小范围（如 3-10），防止错误和性能问题。
  • 使用合适的数据结构：例如使用 Pair<Int, Int> 表示坐标，提高代码可读性和可维护性。

常见问题

  • Q1: 为什么使用递归回溯而不是其他算法？
    A: 递归回溯能生成完美迷宫（每个格子都可达），且算法简单高效。
  • Q2: BFS 和 DFS 的区别是什么？
    A: BFS 使用队列找最短路径；DFS 使用栈或递归找任意路径。
  • Q3: 迷宫大小为什么限制在 10×10？
    A: 出于性能考虑，更大的迷宫会导致计算时间过长。
  • Q4: 如何优化迷宫生成性能？
    A: 可考虑使用迭代代替递归、减少随机数生成、使用位操作等。
  • Q5: 如何处理无解的迷宫？
    A: 使用 BFS 搜索，如果队列为空且未找到出口，则迷宫无解。

关键要点

  • 使用递归回溯生成迷宫，使用 BFS 找最短路径。
  • 检查边界条件和特殊情况，使用合适的数据结构。
  • KMP 能无缝编译到 JavaScript，实现跨端开发。
  • 通过扩展和优化，可以增强迷宫工具的功能和性能。
kotlin-mp
0 Answers
Related
Kotlin Multiplatform与Flutter跨平台开发全面对比
Kotlin Multiplatform: Flexible Cross-Platform Development with Compose
Kotlin跨平台开发入门：KMM详解
Kotlin 1.2跨平台新特性详解
深入分析KMP运行原理，内存管理有讲究，架构设计是关键
Kotlin跨平台编程：从Android到多平台应用