如何在VB.Net中为简易金币收集游戏实现寻路算法？

第一步：连通性检测（解决出生封闭/金币不可达） #

先判断玩家起点与金币终点是否处于同一可通行区域，避免无效的路径搜索。推荐用BFS（广度优先搜索），逻辑简单且能同时完成连通性验证与后续路径查找的基础工作。

核心逻辑 #

• 从起点出发，遍历所有可通行格子（排除"w"、ChrW(9068)及已访问过的格子）
• 若遍历过程中抵达金币位置，说明两者连通；若遍历完所有可达格子仍未找到金币，则判定为阻隔或封闭区域

VB.Net代码示例 #

' 定义坐标结构
Public Structure Point
    Public X As Integer
    Public Y As Integer
    Public Sub New(x As Integer, y As Integer)
        Me.X = x
        Me.Y = y
    End Sub
End Structure

' 检测起点与终点是否连通
Function IsConnected(map As String(,), start As Point, target As Point) As Boolean
    Dim rows As Integer = map.GetLength(0)
    Dim cols As Integer = map.GetLength(1)
    Dim visited As Boolean(,) = New Boolean(rows - 1, cols - 1) {}
    Dim queue As New Queue(Of Point)()

    ' 先校验起点/终点本身是否为障碍物
    If IsObstacle(map(start.X, start.Y)) Or IsObstacle(map(target.X, target.Y)) Then
        Return False
    End If

    queue.Enqueue(start)
    visited(start.X, start.Y) = True

    ' 上下左右四个移动方向
    Dim directions() As Point = {New Point(-1, 0), New Point(1, 0), New Point(0, -1), New Point(0, 1)}

    While queue.Count > 0
        Dim current As Point = queue.Dequeue()

        ' 抵达目标，返回连通
        If current.X = target.X And current.Y = target.Y Then
            Return True
        End If

        ' 遍历所有方向的相邻格子
        For Each dir In directions
            Dim newX = current.X + dir.X
            Dim newY = current.Y + dir.Y

            ' 校验坐标合法性、未访问、非障碍物
            If newX >= 0 And newX < rows And newY >= 0 And newY < cols _
               And Not visited(newX, newY) _
               And Not IsObstacle(map(newX, newY)) Then
                visited(newX, newY) = True
                queue.Enqueue(New Point(newX, newY))
            End If
        Next
    End While

    ' 遍历完所有可达格子仍未找到目标，判定为不连通
    Return False
End Function

' 判断当前格子是否为障碍物
Private Function IsObstacle(cellValue As String) As Boolean
    Return cellValue = "w" Or cellValue = ChrW(9068)
End Function

第二步：路径查找算法（获取玩家到金币的可行路径） #

若连通性检测通过，可使用BFS获取最短路径，适合简易游戏的场景；如果地图规模较大，可替换为A*算法（通过曼哈顿距离作为启发函数提升效率）。

VB.Net代码示例（BFS找最短路径） #

' 返回从起点到终点的完整路径（从起点到终点的Point列表）
Function FindPath(map As String(,), start As Point, target As Point) As List(Of Point)
    Dim rows As Integer = map.GetLength(0)
    Dim cols As Integer = map.GetLength(1)
    Dim visited As Boolean(,) = New Boolean(rows - 1, cols - 1) {}
    ' 记录每个格子的前驱节点，用于回溯路径
    Dim parent As Point(,) = New Point(rows - 1, cols - 1) {}
    Dim queue As New Queue(Of Point)()

    If IsObstacle(map(start.X, start.Y)) Or IsObstacle(map(target.X, target.Y)) Then
        Return New List(Of Point)()
    End If

    queue.Enqueue(start)
    visited(start.X, start.Y) = True
    parent(start.X, start.Y) = start

    Dim directions() As Point = {New Point(-1, 0), New Point(1, 0), New Point(0, -1), New Point(0, 1)}
    Dim found As Boolean = False

    While queue.Count > 0 And Not found
        Dim current As Point = queue.Dequeue()

        For Each dir In directions
            Dim newX = current.X + dir.X
            Dim newY = current.Y + dir.Y

            If newX >= 0 And newX < rows And newY >= 0 And newY < cols _
               And Not visited(newX, newY) _
               And Not IsObstacle(map(newX, newY)) Then
                visited(newX, newY) = True
                parent(newX, newY) = current
                queue.Enqueue(New Point(newX, newY))

                ' 找到目标，标记并退出循环
                If newX = target.X And newY = target.Y Then
                    found = True
                    Exit For
                End If
            End If
        Next
    End While

    ' 回溯生成路径
    Dim path As New List(Of Point)()
    If found Then
        Dim current As Point = target
        ' 从终点往起点回溯，再反转得到正向路径
        While Not (current.X = start.X And current.Y = start.Y)
            path.Add(current)
            current = parent(current.X, current.Y)
        End While
        path.Add(start)
        path.Reverse()
    End If

    Return path
End Function

游戏内应用逻辑 #

1. 玩家出生时：调用IsConnected检测起点是否与至少一个金币（或地图可通行区域）连通，若不连通直接提示"出生在封闭区域，请重新生成地图"。
2. 玩家要前往金币时：先调用IsConnected确认可达，不可达则提示"该金币无法到达"；可达则调用FindPath获取路径，引导玩家沿路径移动。

额外优化建议 #

• 大地图场景下，将BFS替换为A*算法，用曼哈顿距离Math.Abs(target.X - current.X) + Math.Abs(target.Y - current.Y)作为启发函数，减少无效遍历。
• 地图生成阶段加入连通性校验，直接避免生成包含封闭区域的地图。

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