CODEWITHSUNDEEP
javarecursion
localnewsletter23
localnewsletter23

Reputation: 31

how to find best possible path in a grid with recursion

picture of map. I'm writing a code that makes its own grid filled with dots and 1's, 1 representing a lootable location and the dots representing a movable location. Every time the program moves one spot, the border closes in once. The program is supposed to figure out the best possible path that gives the most loot. I know I have to use recursion for this because that's the theme of the project but I'm unsure of how to fully go about it.

This is for java and I tried doing this to figure out every single path, but I dont know exactly how to find which one was the best one.

  public static int bestMoves(char[][] coordinates, int movesPossible, int playerX, int playerY, int mapSize, boolean[][] visited){
char[][] mapCopy = new char[mapSize][mapSize];
boolean[][] visitedCopy = new boolean[mapSize][mapSize];
for (int i = 0; i < mapSize; i++){
  for (int j = 0; j < mapSize; j++){
    mapCopy[i][j] = coordinates[i][j];
  }
}
for (int i = 0; i < mapSize; i++){
  for (int j = 0; j < mapSize; j++){
    visitedCopy[i][j] = visited[i][j];
  }
}

if (movesPossible > 0){
  if (playerX - 1 >=0  && !visited[playerY][playerX-1]){
    visitedCopy[playerX-1][playerY] = true;
    if (coordinates[playerY][playerX-1] == '1'){
      return 1 + bestMoves(mapCopy, movesPossible-1, playerX-1, playerY, mapSize-1,visited); 
    }else{
      return bestMoves(mapCopy, movesPossible-1, playerX-1, playerY, mapSize-1,visited); 
    }
  }

  if (playerY - 1 >=0  && !visited[playerY-1][playerX]){
    visitedCopy[playerY-1][playerX] = true;
    if (coordinates[playerY-1][playerX] == '1'){
      return 1 + bestMoves(mapCopy, movesPossible-1, playerX, playerY-1, mapSize-1,visited); 
    }else{
      return bestMoves(mapCopy, movesPossible-1, playerX, playerY-1, mapSize-1,visited); 
    }
  }

  else if (playerY + 1 >= mapSize  && !visited[playerY-1][playerX]){
    visitedCopy[playerY][playerX] = true;
    if (coordinates[playerY+1][playerX] == '1'){
      return 1 + bestMoves(mapCopy, movesPossible-1, playerX, playerY+1, mapSize-1,visited); 
    }else{
      return bestMoves(mapCopy, movesPossible-1, playerX, playerY+1, mapSize-1,visited); 
    }
  }

  else if (playerX + 1 >= mapSize  && !visited[playerY-1][playerX]){
    visitedCopy[playerY][playerX] = true;
    if (coordinates[playerY+1][playerX] == '1'){
      return 1 + bestMoves(mapCopy, movesPossible-1, playerX+1, playerY, mapSize-1,visited); 
    }else{
      return bestMoves(mapCopy, movesPossible-1, playerX+1, playerY, mapSize-1,visited); 
    }
  }else{
    return 0;
  }            
}else{
  return 0;
}

I call this function outside in the main, but it always just returns the number 1 instead of the best path. this is the map that is being used 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . 1 P . 1 1 1 . . . . . 1 1 . . . . . . . . . . 1 . . 1 . . . . . . . . . . . . . . 1 . 1 1 1 . . . . . . . . . 1 . . . . . . . . . . . . . . . . 1 1 1 p is the original location

Upvotes: 1

Views: 87

Answers (1)

Glains
Glains

Reputation: 2863

One possible solution that comes to my mind is related to the MiniMax algorithm. In this algorithm, usually fitting for two player based zero-sum games, you create a game tree and evaluate possible positions up to a maximum depth. This can be adapted, of course, we have only one player here, so that the game tree can be created for each outgoing move (left, right, up, bottom, diagonal if needed) and evaluated with a function that scores better for each collected point. If no more points are left on the board, no more outgoing positions are created. AT the end, take that path that scored the most points.

If the depth is good enough, this should always lead to a best-effort-solution.

Of course, if the board gets larger, there may be a better algorithm. But since the board is shrinking rapidly each move, all positions should be able to be generated.

Upvotes: 1

Related Questions