Path Finding Application Algorithm

Question

I am trying to develop an application that maps my office (exactly like application like google maps, showing path from one seat to another).

From what I have read so far, algorithms like Dijkstra's, or Back Tracking can be used to solve the problem. But these algorithms require something of a 2 D matrix (or a variant of that) as an input. Now thinking from an administrative point of view of application, the person has only the floor map of office to feed as input to the application. How can this floor map be transposed to something which these algorithms can take as input? Or am I missing something altogether?

Any suggestion would be appreciated.

Answer 1

Actually the matrix isn't required. The graph can just aswell be generated on runtime. The image can be converted into a map of walls and open spots by simply converting it into a two-colored image, where one color represents walls. This would look like this for your requirements:

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