I am working on a project for UAV coordinated searching. I have a sample terrain data (which is supposed to be searched) of an area and it has been divided into a 20*20 grid, i.e. 400 cells. Now given a starting cell and ending cell, I need to find the shortest path from Starting to ending cell.
I had a look at the available shortest path algorithms such as A*, Yen's algo, Dijkstra algo but the difficulty I have in these is that they are implemented for graphs. Converting the input into a graph isn't possible due to memory constraints on the arduino board along with absence of STL. I had a look at StandardCplusplus library but it doesn't meet my requirements due to memory constraints (I have around 10 modules in my project).
Is there a possible way to get this implementation of the shortest path using only the default libraries in arduino, i.e. by using arrays? It would be really great if someone could guide me in the process while I try to implement it. Perhaps a use of anytime algorithms, especially because this is time critical.
The terrain input is as follows:
"Each cell has edges to all of its surrounding neighbours, with the elevation difference between the cell and a neighbour as the weight of the respective edge. Unreachable neighbours have edges with weights of 9999. Sample data for the first three cells are shown as follows:
0 21 9999 0 20 9999 0 1 7 1 20 9999 1 22 16 1 21 9999 1 0 7 1 2 9999 2 21 9999 2 23 9999 2 22 10 2 1 9999 2 3 7
In this set of data, this means that from cell (0, 0), cells (1, 0) and (1, 1) are unreachable, but it is possible to reach cell (0, 1) with a cost of 7. Similarly, from cell (0, 1), cells (1, 0), (1, 1) and (0, 2) are unreachable, but it is possible to reach cells (1, 2) with a cost of 16 and (0, 0) with a cost of 7.
Thanks a lot in advance