Путь поиска алгоритма приложения

Question

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

Из того, что я до сих пор читал, для решения проблемы могут использоваться алгоритмы типа Dijkstra's или 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