algorithm - 寻路应用算法

Question

我正在尝试开发一个绘制我办公室 map 的应用程序(就像谷歌地图这样的应用程序，显示从一个座位到另一个座位的路径)。

根据我目前所读的内容，Dijkstra 或回溯 等算法可用于解决该问题。但是这些算法需要某种二维矩阵(或它的变体)作为输入。现在从应用程序的管理角度考虑，这个人只有办公室的平面图可以作为应用程序的输入。如何将此平面图转换为这些算法可以作为输入的内容？还是我完全遗漏了什么？

如有任何建议，我们将不胜感激。

Answer 1

实际上不需要矩阵。该图也可以在运行时生成。只需将图像转换为双色图像(其中一种颜色代表墙壁)，即可将图像转换为墙壁和开放点的 map 。根据您的要求，这看起来像这样:

define node: (int x , int y)

define isWall:
//this method is actually used for imageprocessing
//i've forgotten the name of it, so if anyone knows it, pls comment
    input: int rgb
    output: boolean wall

    int red = red(rgb)
    int green = green(rgb)
    int blue = blue(rgb)

    int maxWallVal//comparison value

    return (red + green + blue) / 3 < maxWallVal

define listNeighbours:
    input: node n , int[][] img
    output: list neighbours

    int x = n.x
    int y = n.y

    list tmp

    if x + 1 < img.length
        add(tmp , (x + 1 , y)
    if x > 0
        add(tmp , (x - 1 , y)
    if y + 1 < img[x].length
        add(tmp , (x , y + 1)
    if y > 0
        add(tmp , (x , y - 1)

    for node a in tmp
        int rgb = img[a.x][a.y]
        boolean wall = isWall(rgb)

        if NOT wall
            add(neighbours , a)

    return neighbours

define findPath:
     input: node start , node end , int[][] img
     output: list path

     set visited
     map prevNodes

     queue nodes
     add(nodes , start)

     while NOT isEmpty(nodes)
         node n = remove(0 , nodes)

         if n == end
             break     

         add(visited , nodes)

         for node a in listNeighbours(n)//list all neighbour-fields that are no wall
             if contains(visited , a)
                  continue

             add(queue , a)
             put(n , a)

    node tmp = start
    while tmp != null
    add(path , tmp)
    tmp = get(prevNodes , tmp)

    return path