Finding shortest path in 2D Integer array Java
I am making a snake game where the snake traverses a 2D array as its terrain. The values stored in the 2D array represent the time in seconds it takes to cross.
For example,
int[][] MAP = {
{ 1, 1, 1, 2, 2 },
{ 1, 2, 2, 2, 2 },
{ 3, 2, 2, 3, 1 },
{ 1, 1, 3, 2, 1 },
{ 1, 1, 3, 2, 1 }
};
So, the transition from map[0][0]
to map[0][4]
takes 1 + 1 + 2 + 2
seconds. How would I make an algorithm that would find the shortest path to move the snake from position map[startX][startY]
to map[endX][endY]
?
This is not homework, I'm just making a game for fun and would like to know how to do it.
source to share
This is one of the known problems when discussing "dynamic programming" and even reminds of an old post .
However, I haven't found a solution that also prints the shortest path, so:
public class FastestPathCalculator {
private final int[][] map;
public FastestPathCalculator(int[][] map) {
this.map=map;
}
public static void main(String[] args) {
int[][] map = new int[][]{
{1, 1, 1, 4, 2},
{1, 2, 5, 2, 2},
{3, 2, 2, 3, 1},
{1, 1, 3, 2, 1},
{3, 1, 3, 2, 1}
};
FastestPathCalculator c = new FastestPathCalculator(map);
boolean[] result = c.computeFastestPath(map);
c.printPath(result);
}
Here the boolean array represents the steps taken from (0,0) - (4,4). TRUE means step to the right, FALSE means "down". In this example, the array has 8 cells.
public boolean[] computeFastestPath(int[][] map) {
int pathLength = map.length + map[0].length - 2;
boolean[] result = new boolean[pathLength];
int[][] mapOfMinimalSums = buildMapOfMinimalSums();
int x = map.length-1;
int y = map[0].length-1;
for (int i = pathLength - 1 ; i >= 0; i--) {
if (x == 0)
result[i] = true;
else if (y == 0)
result[i] = false;
else if (mapOfMinimalSums[x][y] == map[x][y] + mapOfMinimalSums[x][y-1]) {
result[i] = true;
y--;
}
else {
result[i] = false;
x--;
}
}
return result;
}
public void printPath(boolean[] result) {
String[][] newPath = new String[map.length][map[0].length];
int x = 0;
int y = 0;
newPath[x][y] = String.valueOf(map[x][y]);
for (int i = 0 ; i < result.length; i++) {
if (result[i]) {
y++;
} else {
x++;
}
newPath[x][y] = String.valueOf(map[x][y]);
}
for (int i = 0 ; i < map.length; i++) {
for (int j = 0 ; j < map[0].length; j++) {
if (newPath[i][j] == null) {
System.out.print(" , ");
} else {
System.out.print(newPath[i][j] + ", ");
}
}
System.out.println();
}
System.out.println();
}
private int[][] buildMapOfMinimalSums() {
int[][] mapOfSums = new int[map.length][map[0].length];
for (int i = 0 ; i < map.length; i++) {
for (int j = 0 ; j < map[0].length; j++) {
if (i == 0 && j == 0)
mapOfSums[i][j] = map[i][j];
else if (i == 0) {
mapOfSums[i][j] = mapOfSums[i][j - 1] + map[i][j];
}
else if (j == 0)
mapOfSums[i][j] = mapOfSums[i-1][j] + map[i][j];
else
mapOfSums[i][j] = Math.min(mapOfSums[i-1][j], mapOfSums[i][j-1]) + map[i][j];
}
}
return mapOfSums;
}
}
source to share