pathfinding in 2d array

Question

I am currently working on a project, in which I have to perform tasks with a 2 dimensional array, containing random numbers. The array forms a grid, which represents peaks (heights) of a mountain. I resolved every task except the last one:

The last task would be to find if there exists a path, which goes form the smallest peak to the highest (it doesn't have to be the shortest). The path should consist of ever growing peaks, I can't step on a lower peak.

Here's an example, for simplicity's sake, represented on 3x3 grid (original is much bigger, and not necessary square-like, it's generated as the user wants and numbers are completely random).

2  4  5    
1  3  8
9  7  10

The possible ways would be 1-3-7-10, 1-3-8-10, 1-2-4-5-8-10.

I am pretty sure, that I should use some kind of a recursion. I read about a* pathfinder, but to work with it, I have to have a "map" with the "obstacles" (the nodes where I cannot step = smaller peaks) and that is exactly, which I can't make, as you only find it out on the go.

By that I mean I could put number 7 on a "exception list" -as steps 1-9-7 are forbidden, but steps 1-3-7-10 are perfect, so putting 7 on a exception list would be a mistake.

Answer 1

The key is to first convert your array into a "digraph" which is a directed-graph consisting only of the valid cell-to-cell moves according to your rules. This digraph would be an array or list of entries consisting of: {FromCell, ToCell}

Your digraph would contain data like this:

2,4
4,5
5,8
1,2
1,3
1,9
3,4
3,8
3,7
8,10
7,10

From here you should be able to apply the A* algorithm, or any of a number of others.

(note: I am not posting a completed answer, as I assume that you want to do this yourself)

---

That said, you could just do a brute-force recursive search with back-tracking. This is the simplest solution, though probably not the most efficient.

Answer 2

You could do the following:

1. Create a weighted graph from your matrix (the weight of each edge would be the abs( difference between the values of the two nodes))

   2 - 4 - 5
   
   |   |   |
   
   1 - 3 - 8
   
   |   |   |
   
   9 - 7 - 9 
   

the weight of (2, 4) is abs(4 - 2) = 2

the weight of (4, 5) is abs(4 - 5) = 1

1. Apply a shortest path algorithm which takes into account the weight of the edges http://www.informatics.susx.ac.uk/courses/dats/notes/html/node147.html

2. Remove the solutions in which the values of the nodes aren't ascending

Answer 3

(I fixed post and placed the answer here.)

This is how I finally solved it:

Since I already had the min and max places, I surrounded the original array with zeroes. Zeroes are global minimums of the array, as I never generate zeroes by default. With this I don't have to check every time if I'm out or in the array (I only step on bigger numbers).

I created two queues (QueueX,QueueY). Starting from the smallest number (whose place I en-queued in the beginning into the queues, gave to x,y variables of array t[x,y], and then de-queue).

I then en-queue every bigger numbers' "coordinates" into the respective queues. If I found all the bigger numbers around the actual point (t[x,y]), I en-queue the next X,Y coordinates, which will be the new actual points (as explained in the start). And the inspection repeats.

The whole thing is in a while cycle, which stays in while one of the queues empty out.

If at any given inspection X,Y is the same as max peak's X,Y coordinates, I return and there exists a path. At the end of the while cycle if X,Y isn't the same as max's X,Y, there is no path.

I hope my explanation is somewhat understandable, English isn't my native language. If you'd like, I could post the code here.