路径发现应用算法

Question

我正在尝试开发一个应用程序来映射我的办公室（就像谷歌地图一样，显示从一个座位到另一个座位的路径）。

从我到目前为止所读到的内容来看，像Dijkstra的算法，或者说回溯算法，可以用来解决这个问题。但这些算法需要二维矩阵（或其变体）作为输入。现在，从应用程序的管理角度考虑，此人只有办公室的平面图作为应用程序的输入。如何将这个平面图转换成这些算法可以作为输入的东西？还是我完全错过了什么？

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

Answer 1

实际上矩阵不是必需的。该图也可以在运行时生成。通过简单地将图像转换为双色图像，其中一种颜色代表墙壁，可以将图像转换为墙壁和开放点的地图。对于您的需求，这看起来像这样：

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