What's wrong with my collection algorithm for my AI when it's trying to gather points? It gets confused and goes back and forth

Question

I'm trying to write a basic AI for a game where the character collects points on a grid. The points are randomly generated on the grid and my AI just has to move onto that coordinate on the grid.

The AI can't see the full grid however, it can only see a 5x5 grid with it at the center as it moves around each "turn". (So it's at coordinate (2, 2) each turn.)

My algorithm is basic, but it basically scans the 5x5 grid and tries to find the closest point, then it moves the character toward that direction. Then the next turn that point will be even closer (as we just moved even closer to it) so it will choose to keep approaching it until it finds gets to the desired coordinate.

Here it is in Java:

  Field[][] fields =  gameboard.getFields();
  int centerX = 2;
  int centerY = 2;

  // Large numbers that points will always be closer than
  int nearestPointX = 1000;
  int nearestPointY = 1000;

  for (int i = 0; i < 5; i++) {
     for (int j = 0; j < 5; j++) {
        Field field = fields[i][j];

        if (field.getType() == 0 && field.hasPoint()) {
           int distanceX = Math.abs(i - centerX);
           int distanceY = Math.abs(j - centerY);

           int totalDistance = distanceX + distanceY;
           int totalBestDistance = nearestPointX + nearestPointY;

           if (totalDistance < totalBestDistance) {
              nearestPointX = i;
              nearestPointY = j;
           }
        }
     }
  }

  Field northField = fields[centerX][centerY-1];
  Field southField = fields[centerX][centerY+1];
  Field eastField = fields[centerX+1][centerY];
  Field westField = fields[centerX-1][centerY];

  String move = previousMove;

  // If there's a point nearby
  if (nearestPointX != 1000) {
     if (nearestPointX > centerX) {
        move = "E";
     } else if (nearestPointX < centerX) {
        move = "W";
     } else if (nearestPointY > centerY) {
        move = "S";
     } else if (nearestPointY < centerY) {
        move = "N";
     }
  }

But under certain conditions it will approach an area with multiple points, seemingly get confused and just pulsate back and forth over two blocks. It also seems sporadic with choosing the exact best block sometimes, which I assume is related.

I've read it over a million times and tried to debug it, but I just can't figure out what is causing the bug. Can anyone pinpoint what I'm doing wrong in finding the closest point?

Answer 1

Look at the comparison you're doing. totalDistance is equal to the number of steps from your current location to the point being considered, but totalBestDistance is the in-frame x,y coordinates of the previous "best point". So (for example) if you had points at (2, 4) and (3, 0), your code would:

Evaluate (2, 4) - distanceX is 0, distanceY is 2, totalDistance is 2. This updates nearestPointX to 2 and nearestPointY to 4.

Evaluate (3, 0) - distanceX is 1, distanceY is 2. totalDistance is 3. totalBestDistance then becomes nearestPointX + nearestPointY, which is 6. So (3, 0) becomes your new "best point", even though your previous one was closer (actual distance was 2).