Get random direction based off of location and previous direction I've recently implemented a Wilson's Algorithm for maze generation. This problem however could also be extended to things such as snake, or some other simple AIs.

The problem is as follows:


  Blue Node -> Previous nodes
  
  Red Node -> Current node
  
  Black Line -> Wall
  
  
  
  In this case, we can analyze each of the 4 possible directions: up,
  right, down and left.
  
  
  Up - Not available, since the last move was down (reversing itself)
  Right - Not available, since there is a wall directly to the right
  Down - Available
  Left - Available
  
  
  From here we can see that should it move down, then the same
  availability will occur. If it should move left: up, left and down
  would then be available.


The way I have implemented this is as follows:

private int nextDirection(final int i, final int j, final int rowLimit, final int columnLimit, final int previous) {
    boolean up = true;
    boolean right = true;
    boolean down = true;
    boolean left = true;
    if (i == 0) {
        up = false;
    } else if (i == rowLimit) {
        down = false;
    }
    if (j == 0) {
        left = false;
    } else if (j == columnLimit) {
        right = false;
    }
    switch (previous) {
        case DIRECTION_UP:
            down = false;
            break;
        case DIRECTION_DOWN:
            up = false;
            break;
        case DIRECTION_RIGHT:
            left = false;
            break;
        case DIRECTION_LEFT:
            right = false;
    }
    final ArrayList&lt;Integer&gt; list = new ArrayList&lt;&gt;(4);
    if (left) {
        list.add(DIRECTION_LEFT);
    }
    if (right) {
        list.add(DIRECTION_RIGHT);
    }
    if (down) {
        list.add(DIRECTION_DOWN);
    }
    if (up) {
        list.add(DIRECTION_UP);
    }
    return list.get(random.nextInt(list.size()));
}


Where:


i           - row of current node
j           - column of current node
rowLimit    - row count minus one
columnLimit - column count minus one
previous    - previous direction
random      - java.util.Random instance


Now, I highly doubt this is the most efficient solution. However it is the least - well - troublesome. The others I have used are just a large amount of if statements considering every possible case.

However, neither of these solutions - at least how I see them - are efficient enough. Due to this and what Knuth once said, I went for readability. The main problem is, this has become a bottleneck in the calculation speeds.

Question:

Is there a way to better calculate the available directions? And therefore a better way to select a random direction.

Sides notes:

DIRECTION_UP    = 0x01;
DIRECTION_RIGHT = 0x02;
DIRECTION_DOWN  = 0x04;
DIRECTION_LEFT  = 0x08;


These can be changed to whatever value needed.
First of all, using i and j as variable names when dealing with 2D-arrays is just crazy in my personal opinion. Using x and y makes it so much clearer to know which is which.

Then, use an enum:

public enum Direction {
    LEFT, UP, RIGHT, BOTTOM;

    public Direction opposite() {
        switch (this) {
            case LEFT: return RIGHT;
            case RIGHT: return LEFT;
            case UP: return BOTTOM;
            case BOTTOM: return UP;
            default: throw new IllegalStateException();
        }
    }
}


This is probably the most useful enum there is. I don't know how many versions of it I have. Also note that you can add dx and dy values to this enum (UP for example is dx = 0 and dy = -1). This tends to reduce a lot of code duplication.

Now that we have an enum we can return that instead of those int things.

Also, we can use Java's EnumSet class to handle a collection of enums. This class is optimized to use a long (BitSet object for longer enums) and bitmasks, sort of like you seem to already be doing.

Once we have a nice EnumSet to use, then we can either create an array of it and grab a random item from the array, or we can use the iterator of it to iterate over random.nextInt(size) items (not the cleanest and fastest solution perhaps, but it should be faster than creating an array).

Random random = new Random();
private Direction nextDirection(final int y, final int x, final int rowLimit, final int columnLimit, final Direction previous) {
    EnumSet&lt;Direction&gt; directions = EnumSet.allOf(Direction.class);
    if (x == 0) {
        directions.remove(Direction.LEFT);
    }
    if (x == columnLimit) {
        directions.remove(Direction.RIGHT);
    }
    if (y == 0) {
        directions.remove(Direction.UP);
    }
    if (y == rowLimit) {
        directions.remove(Direction.BOTTOM);
    }
    directions.remove(previous.opposite());

    Iterator&lt;Direction&gt; it = directions.iterator();
    for (int i = 0; i &lt; random.nextInt(directions.size()); i++) {
        it.next();
    }
    return it.next();
}


Or, if you would like the array approach:

Direction[] options = directions.toArray(new Direction[directions.size()]);
return options[random.nextInt(options.length)];