algorithm for 2D array that represents the topographic map of geographic surface

Question

I'm having difficulty figuring out what to do with the following problem

The input will be 2D array A[n][n] numbers, representing the topographic map of the geographic surface. Also among the input will be a starting location (r,c). referring to entry A[r][c]

If you were planning hiking trails you would be bound by the differences in elevation between neighboring entries. A person could traverse between 2 adjacent locations, if their elevations differ by no more than 2). Adjacency follows just the 4 standard compass directions, (so I assume no diagonals). Therefore , a point on the map is considered reachable if it is traversable from A[r][c] through any sequence of adjacent entires.

Write an algorithm that computes all of the reachable locations. The output will be another 2D array R[n][n] with true/fals values. (I assume true means reachable, false means unreachable)

If i understand this question correctly, I can create following matrix. (suppose A[10][10] looks like this from A[0][0]:)

50 51 54 58 60 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 64 66 69

44 46 53 52 57 60 60 61 65 68

42 45 50 54 59 61 63 63 66 70

38 42 46 56 56 63 64 61 64 62

36 40 44 50 58 60 66 65 62 61

36 39 42 49 56 62 67 66 65 60

30 36 40 47 50 64 64 63 62 60

50 50 50 50 50 50 50 50 50 50

Both south and east are traversable from A[0][0] so reachable entries would be:

50 51 54 58 60 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 64 66 69

44 46 53 52 57 60 60 61 65 68

42 45 50 54 59 61 63 63 66 70

38 42 46 56 56 63 64 61 64 62

36 40 44 50 58 60 66 65 62 61

36 39 42 49 56 62 67 66 65 60

30 36 40 47 50 64 64 63 62 60

50 50 50 50 50 50 50 50 50 50

so I can conclude that my resulting array should be

1 1 0 0 0 0 0 1 0 0

1 1 1 0 0 0 1 1 0 0

0 0 1 0 0 0 1 1 1 0

0 0 1 1 0 0 0 0 1 0

0 0 0 1 0 0 0 0 1 0

0 0 0 1 1 0 0 0 1 1

0 0 0 0 1 1 0 0 1 1

0 0 0 0 1 1 0 0 0 1

0 0 0 0 0 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0

I want to implement this in c code but i think its improper to ask for the code here. My plan is to implement this in pseudocode first then implementing in c code, which I will try doing it by myself =). I'm not sure as to where to start with my pseudocode. Can anyone please clarify this?

Thank you very much!

p.s just edited my matrix

Answer 1

Have a look at Dijkstra or A-Star which are used in such a case. Further more you may have a look at Graph Theory basics in order to create an appropriate representation of your matrics.

Additionally you may need the Manhatten Distance which can be used as a heuristic for the A-Star in your case.

There are many other algorihms if you dive deeper into the topic of graph theory and search algorithms.

EDIT due to comment:

You can also use Depth First Search (DFS) or Breadth First Search (BFS). These algorithms are simpler to implement especially at the beginning.

At first you need to create an appropriate datastructur which represents the hightmap. These structur could look like this:

struct Vertex 
     int x                 // coordinate x
     int y                 // coordinate y
     Vertex neighbors[8]; // Array of all adjacent vertices 
     int height            // height
}

after that you can use the following pseudocode as an proposal taken from Breadth first search and depth first search which already is aware of cycles within the graph, which would lead to infinite loops.

 dfs(vertex v) {
    visit(v); 
    for each neighbor w of v            
        if w is unvisited **and reachable** // reachable according to your hight differences
        {
        dfs(w); // recursive call to the dfs 
        add edge vw to tree T  //tree contains a result path in your
                               //case the second matrix
        }
    }

Some steps are missing within the pseudocode. For example the condition for abandon the DFS when visiting the goal.

Some additional notes:

• the DFS will find just a solution for your problem
• Dijkstra and A-Star will find the shortest (optimal) solution for the problem (shortest path from start to goal, taking into account the hight of your Vertices