What's wrong with my random wandering algorithm?

Question

I've created a 2 dimensional 'grid' for a game world I'm creating in Java. I'm having a problem with the 'wander' mode algorithm I've created.

I noticed a problem that the objects would seem to favor the bottom right corner of the grid. I changed the algorithm and thought it was fixed.

Today, while stress testing, I noticed that the problem was not fixed, and now wandering objects favor the top left corner of the grid, but it takes longer for them to wander in that area.

The algorithm works by: 1. Getting the current values of the person's position 2. Putting all the squares in 3 block radius into a linked list 3. Randomize the list 4. Choose a random value from the list 5. Setting that values point as the next target

Here's a code snippet:

 Point personAt = this.getTopLeftPoint();
    personAt = Game.getGame().screenToGame(personAt);
    LinkedList<Point> thisSet = new LinkedList<Point>();
    for (int x = personAt.x - 2; x < personAt.x + 3; x++) {
 for (int y = personAt.y - 2; y < personAt.y + 3; y++) {
     if (!(x == personAt.x && y == personAt.y)) {
  //TODO: Clean up the next line of code.
  if (x > 0 && y > 0 && !Board.getBoard().getSquare(x, y).getSquareType().equals(SquareType.path)) {
      if (!Game.getGame().getMap().blocked(x, y)) {
   thisSet.add(new Point(x, y));
      }
  }
     }
 }
    }
    Collections.shuffle(thisSet);
    //Random random = new Random();
    //Integer randomNo = random.nextInt(thisSet.size());
    setNextTarget(thisSet.get(0));

Is there anything I'm missing here?

I am confused as to why they still end up within the top left quarter of the grid.

EDIT: I completely removed the Random object, as suggested by Don. Still end up with the same result.

EDIT: Updated code to fix one part of the issue, so now only the square the person is currently on is ignored, rather that all squares on the current X or Y co ordinate. As suggested by rsp.

Answer 1

Only initialize random once. You're ruining the randomness by reinstantiating the random generator over and over.

Preferably, use a factory for the entire application to create a random singleton.

public class RandomFactory
{
    private Random random;
    public Random getRandom()
    {
       if( random == null ){ random = new Random(); }

       return random;
    }
}

Answer 2

Assuming the shuffle() method is unbiased, there's no reason why you should need to randomly choose an element after shuffling, you could simply choose the first element. In other words, replace this:

Collections.shuffle(thisSet);
Random random = new Random();
Integer randomNo = random.nextInt(thisSet.size());
setNextTarget(thisSet.get(randomNo));

with:

Collections.shuffle(thisSet);
setNextTarget(thisSet.get(0));

Answer 3

A few points, some of which have been made in other answers:

• As ever, only create a single instance of Random(). I suspected this would be part of the answer - very few questions about random numbers on Stack Overflow aren't to do with this :)
• Why are you shuffling the set and taking a random element? Just pick one random element.
• One point of asymmetry: you're checking the x > 0 and y > 0 (not >= 0, by the way?) but you're not checking whether x and y are within the upper bounds of the board. if Board.getSquare() copes with that, do you really need the > 0 checks?

Answer 4

as others have said, you should only ever instantiate a Random object once and then reuse it, and the shuffle() call should mean you don't need to use Random at all. But as for the root cause of your bug, it looks like every time it is called it initializes at this.getTopLeftPoint(), so I don't see how it wouldn't always go to the top left. I would think you'd want to instantiate personAt at their actual location, not at the top left point.

Answer 5

You say you put all surrounding points in the list but your code excludes the horizontal and vertical lines, so your objects tend to move in diagonal direction only, which might explain a preference for upper left.

Btw, your conditionals can be placed a bit more readable saving some unnecessary execution in the process:

for (int x = personAt.x - 2; x < personAt.x + 3; x++) {
  if (x > 0 && x != personAt.x) {
    for (int y = personAt.y - 2; y < personAt.y + 3; y++) {
      if (y > 0 && y != personAt.y) {

         if (!Game.getGame().getMap().blocked(x, y) &&
               !Board.getBoard().getSquare(x,y).getSquareType().equals(SquareType.path)) {

            thisSet.add(new Point(x, y));
         }
      }
   }
}

Answer 6

What is the order of the list of Person objects (that you are running this code over)? If you iterate through them all in some pre-set order then you could be introducing a bias there because the results of the first one will have an effect on the second (and so on).

You might try shuffling the list of people before processing them.

Answer 7

It's hard to find any problem in that code, but you're calling a lot of methods outside that code. Starting with getTopLeftPoint(), my first suspect, are you sure that you are using the same reference for the coordinates. If getTopLeftPoint() returns the leftmost, topmost point but setNextTarget sets the middle point, we have the problem!

Next: screenToGame() also changes the coordinate... could also be the source of the problem.

Is that if part correct

!Board.getBoard().getSquare(x, y).getSquareType().equals(SquareType.path)

you can only walk a square that is NOT a path? (nothing to do with the problem...)

Another: blocked() not sure what that realy does. If all squares dwonside and to the right of the person get blocked as it walks, he will end up in the top left corner.

The last, almost same as first: setNextTarget() same coordinate reference as screenToGame()?

Summary: better create some kind of unit test to test only the random wandering algorithm without all these "noise".
I got nice results doing so (nothing blocked, no path)... Person visit each corner almost the same number of times.

One more point: I would prefer to use a Random instead of shuffling all the list to get just one element of it...