路径查找应用程序算法

Question

我正在尝试开发一个映射我的办公室的应用程序（完全像Google Maps这样的应用程序，显示从一个座位到另一个座位的路径）。

从我到目前为止阅读的内容， dijkstra的算法或后背跟踪可以用于解决问题。但是这些算法需要一个2 d矩阵（或其中的变体）作为输入。现在从管理的角度思考，该人只有办公室的地板图作为输入申请的输入。如何将这些算法可以作为输入的东西转移到这些算法？还是我完全错过了什么？

任何建议将不胜感激。

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