Алгоритм поиска пути

Question

Я пытаюсь разработать приложение, которое отображает мой офис (точно так же, как приложение, например, карты Google, показывающее путь от одного места к другому).

Из того, что я читал до сих пор, для решения проблемы могут использоваться алгоритмы, такие как Dijkstra или Back Tracking. Но эти алгоритмы требуют чего-то вроде двумерной матрицы (или ее варианта) в качестве входных данных. Теперь, думая с административной точки зрения приложения, у человека есть только карта этажа офиса для подачи в качестве входных данных для приложения. Как эту карту этажа можно транспонировать в то, что эти алгоритмы могут принимать в качестве входных данных? Или я что-то упустил совсем?

Любое предложение будет оценено.

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