Get random direction based off of location and previous direction

Question

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<Integer> list = new ArrayList<>(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.

JS1 · Accepted Answer · 2015-03-18 08:54:46Z

I come from a C programming background, so when I saw this question I immediately thought to use bit manipulations and array lookups for speed. It's interesting to see all the other answers that use other data types such as ArrayList, EnumSet, Stream, and HashSet.

Using a bitmask

Instead of using 4 booleans, you can use a bitmask that contains the possible directions to move in. Using your definitions for directions, the bitmask should start at 0xf for all 4 possible directions. You can eliminate directions by and'ing off bits that represent directions that are impossible to move in.

After removing impossible directions, you will be left with a bitmask with 1-3 bits set, each bit representing a possible direction to move in. Next, you use a predefined array called NumDirections to find out how many bits are in the bitmask. For example, NumDirections[5] is 2 because the bitmask 0x5 is 0101 which has 2 bits set in it.

Then, you pick a random number as you did before. With the random number, you index into a second predefined array called PickDirection. This is a two dimensional array of size [16][4], which contains the directions for each bitmask and random number. So for example, if the bitmask were 0x5, the random number would be either 0 or 1 because there were 2 bits set. PickDirection[5][0] is 0x1 and PickDirection[5][1] is 0x4 because those are the 2 bits that are in 0x5.

The predefined arrays

These should be defined at the class level since they are constants.

private static final int DIRECTION_UP    = 0x1;
private static final int DIRECTION_LEFT  = 0x2;
private static final int DIRECTION_DOWN  = 0x4;
private static final int DIRECTION_RIGHT = 0x8;
private static final int DIRECTION_MASK  = 0xf;

private static final byte [] NumDirections = {
    /* 0000 */ 0, /* 0001 */ 1, /* 0010 */ 1, /* 0011 */ 2,
    /* 0100 */ 1, /* 0101 */ 2, /* 0110 */ 2, /* 0111 */ 3,
    /* 1000 */ 1, /* 1001 */ 2, /* 1010 */ 2, /* 1011 */ 3,
    /* 1100 */ 2, /* 1101 */ 3, /* 1110 */ 3, /* 1111 */ 4,
};
private static final byte [][] PickDirection = {
    /* 0000 */ { 0, 0, 0, 0 },
    /* 0001 */ { 1, 0, 0, 0 },
    /* 0010 */ { 2, 0, 0, 0 },
    /* 0011 */ { 1, 2, 0, 0 },
    /* 0100 */ { 4, 0, 0, 0 },
    /* 0101 */ { 1, 4, 0, 0 },
    /* 0110 */ { 2, 4, 0, 0 },
    /* 0111 */ { 1, 2, 4, 0 },
    /* 1000 */ { 8, 0, 0, 0 },
    /* 1001 */ { 1, 8, 0, 0 },
    /* 1010 */ { 2, 8, 0, 0 },
    /* 1011 */ { 1, 2, 8, 0 },
    /* 1100 */ { 4, 8, 0, 0 },
    /* 1101 */ { 1, 4, 8, 0 },
    /* 1110 */ { 2, 4, 8, 0 },
    /* 1111 */ { 1, 2, 4, 8 },
};

The fast function

Here is the function to choose a new direction. The only thing tricky here is that you can get the opposite direction by either shifting left by 2 bits or shifting right by 2 bits. So if you do both and OR the two together, you can get the opposite direction.

private static int nextDirection(final int row, final int col,
        final int rowLimit, final int columnLimit, final int previous)
{
    int possibleDirs = DIRECTION_MASK;
    if (row <= 0)
        possibleDirs &= ~DIRECTION_UP;
    else if (row >= rowLimit)
        possibleDirs &= ~DIRECTION_DOWN;

    if (col <= 0)
        possibleDirs &= ~DIRECTION_LEFT;
    else if (col >= columnLimit)
        possibleDirs &= ~DIRECTION_RIGHT;

    int oppositeDir = ((previous >> 2) | (previous << 2)) & DIRECTION_MASK;
    possibleDirs &= ~oppositeDir;

    int r = random.nextInt(NumDirections[possibleDirs]);
    return PickDirection[possibleDirs][r];
}

Testing the speed

I ran a test where I called the function 100 million times, moving to the next cell as directed by the function. The row and column limits were set to 100. Here are the timing results of a few programs:

Author            Method           Time (msec)
------            ------           -----------
JS1               Array lookups    1848
Obicere           ArrayList        3057
S. Forsberg       EnumSet          3673

Notes: I couldn't get hjk's program to build (because I don't have Java 8). I couldn't get ginkner's program to build as-is, but when I modified it to work it took way longer than the others. I had to use Integer objects everywhere instead of plain ints to make the HashSet work. Since I'm not sure that is what he intended, I didn't want to list it.

For NumDirections, will Integer.bitCount() be a suitable replacement as well? — h.j.k., Mar 18, 2015 at 9:21
@h.j.k. It would work but it would be slower. Since the bitmask is limited to four bits the array lookup only needs 16 bytes. If there were more than 8 bits or so, I would switch to using thebitCount function to not use an excessive amount of space. — JS1, Mar 18, 2015 at 9:25
Due to the nature of the question, I've gone with this one. Just a few runs shows that this method can be ran millions of times, so even a small improvement is huge. I also was aiming entirely for speed, which this achieved. — Obicere, Mar 18, 2015 at 23:35

Community · Accepted Answer · 2017-04-13 12:40:52Z

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<Direction> 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<Direction> it = directions.iterator();
    for (int i = 0; i < 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)];

This really does seem like the best solution. Was hoping for one with some bitwise trickery. I'll give it a few hours and see if anything else pops up. — Obicere, Mar 18, 2015 at 2:00

Community · Accepted Answer · 2017-04-13 12:40:52Z

Building on top of Simon's excellent answer, why stop at enums for Directions when you can do one to represent Borders too?

Looking at it from that perspective, if we have just moved Left, we cannot go Left again if there is a border on the Left. If we just moved Up, we cannot go Up again if there is a border on the top (i.e. Up, for naming consistency). You should get the idea by now.

Let's create our Border enum:

import java.util.EnumSet;
import java.util.Set;

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

    public static Set<Border> getBorders(final int y, final int x, final int rowLimit, final int columnLimit) {
        Set<Border> result = EnumSet.noneOf(Border.class);
        if (x == 0) {
            result.add(LEFT);
        } else if (x == rowLimit) {
            result.add(RIGHT);
        }
        if (y == 0) {
            result.add(BOTTOM);
        } else if (y == columnLimit) {
            result.add(UP);
        }
        return result;
    }
}

We have a static method to generate the Set of Borders for us given the current y, x (side note, I think it's easier to read as x, y instead) positions and the limits of our plane.

Our Direction enum can then be enhanced with two helper methods to determine what are the valid moves (I'm borrowing Streams from Java 8, but I don't think it's that hard to replace it with loops for a < Java 8 implementation):

import java.util.List;
import java.util.Set;
import java.util.stream.Stream;
import java.util.stream.Collectors;

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();
        }
    }

    public boolean isValidMove(final Set<Border> borders) {
        return borders.stream().noneMatch(v -> v.name().equals(name()));
    }

    public List<Direction> getValidMoves(final Set<Border> borders) {
        return Stream.of(values())
                .filter(v -> v != opposite() && v.isValidMove(borders))
                .collect(Collectors.toList());
   }
}

The trick we employ in isValidMove assumes that the Border enums have the same names as our Direction enums to simplify the logic (returning false when the name()s match), alternatively, you can replace it with a more full-blown switch logic. getValidMoves calls isValidMove for the Direction it is evaluating, on top of making sure it is not in the opposite direction of the current Direction (v != opposite()) to give us the List of valid moves.

For testing and illustration purpose, I have the Game class below that shows all the possible outcomes for a given Direction, i.e. the previous argument in your original code for nextDirection():

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.stream.Stream;

public class Game {

    public static void main(String[] args) {
        final int limit = 10;
        final Set<Border> leftBorder = Border.getBorders(1, 0, limit, limit);
        final Set<Border> rightBorder = Border.getBorders(0, 1, limit, limit);
        final Set<Border> topBorder = Border.getBorders(limit, 1, limit, limit);
        final Set<Border> bottomBorder = Border.getBorders(1, limit, limit, limit);
        final Set<Border> topLeftCorner = Border.getBorders(limit, 0, limit, limit);
        final Set<Border> topRightCorner = Border.getBorders(limit, limit, limit, limit);
        final Set<Border> bottomRightCorner = Border.getBorders(0, limit, limit, limit);
        final Set<Border> bottomLeftCorner = Border.getBorders(0, 0, limit, limit);
        final Set<Border> free = Border.getBorders(1, 1, limit, limit);
        final List<Set<Border>> combinations = Arrays.asList(leftBorder, rightBorder, topBorder, bottomBorder,
                topLeftCorner, topRightCorner, bottomRightCorner, bottomLeftCorner, free);
        Stream.of(Direction.values())
                .flatMap(d -> combinations.stream()
                        .filter(b -> b.stream().noneMatch(v -> v.name().equals(d.opposite().name())))
                        .peek(b -> System.out.println("Generating moves for " + d + " given borders " + b))
                        .map(b -> d.getValidMoves(b)))
                .forEach(System.out::println);
    }
}

What the final Stream.of() statement does is this:

Given an element from a Stream of Direction.values(), d,
And an element from a Stream of our test Set<Border> cases, b,
We filter any b where it is impossible to make the move d (e.g. we can't come from the LEFT if we are along the RIGHT edge),
And then call d.getValidMoves() with each b to map() the results as the resulting Stream,
finally calling println to the console for each result.

The console output:

Generating moves for LEFT given borders [LEFT]
[UP, BOTTOM]
Generating moves for LEFT given borders [BOTTOM]
[LEFT, UP]
Generating moves for LEFT given borders [UP]
[LEFT, BOTTOM]
Generating moves for LEFT given borders [LEFT, UP]
[BOTTOM]
Generating moves for LEFT given borders [LEFT, BOTTOM]
[UP]
Generating moves for LEFT given borders []
[LEFT, UP, BOTTOM]
Generating moves for UP given borders [LEFT]
[UP, RIGHT]
Generating moves for UP given borders [UP]
[LEFT, RIGHT]
Generating moves for UP given borders [RIGHT]
[LEFT, UP]
Generating moves for UP given borders [LEFT, UP]
[RIGHT]
Generating moves for UP given borders [UP, RIGHT]
[LEFT]
Generating moves for UP given borders []
[LEFT, UP, RIGHT]
Generating moves for RIGHT given borders [BOTTOM]
[UP, RIGHT]
Generating moves for RIGHT given borders [UP]
[RIGHT, BOTTOM]
Generating moves for RIGHT given borders [RIGHT]
[UP, BOTTOM]
Generating moves for RIGHT given borders [UP, RIGHT]
[BOTTOM]
Generating moves for RIGHT given borders [RIGHT, BOTTOM]
[UP]
Generating moves for RIGHT given borders []
[UP, RIGHT, BOTTOM]
Generating moves for BOTTOM given borders [LEFT]
[RIGHT, BOTTOM]
Generating moves for BOTTOM given borders [BOTTOM]
[LEFT, RIGHT]
Generating moves for BOTTOM given borders [RIGHT]
[LEFT, BOTTOM]
Generating moves for BOTTOM given borders [RIGHT, BOTTOM]
[LEFT]
Generating moves for BOTTOM given borders [LEFT, BOTTOM]
[RIGHT]
Generating moves for BOTTOM given borders []
[LEFT, RIGHT, BOTTOM]

In conclusion

Retrofitting everything together...

private Direction nextDirection(final int y, final int x, final int rowLimit, final int columnLimit, final Direction previous) {
    List<Direction> results = previous.getValidMoves(Border.getBorders(y, x, rowLimit, columnLimit));
    return results.get(random.nextInt(results.size()));
}

Caveats

This solution can't claim to be the speediest, and I still think Simon's answer provides the ideal balance between performance and an 'OO'-approach. JS1's approach is the bit mask approach you ask for... Consider this if it turns out you do have a case to determine where your Borders are, such that the comparison logic between your Directions and said Borders can be abstracted away.

Community · Accepted Answer · 2020-06-10 13:24:26Z

Well, you can significantly shorten your code.

final ArrayList<Integer> possibleMoves = new ArrayList<>()={DIRECTION_UP,DIRECTION_RIGHT,DIRECTION_LEFT,DIRECTION_DOWN};
if(i==0) possibleMoves.remove((object)DIRECTION_UP);
if(i==rowLimit) possibleMoves.remove((object)DIRECTION_DOWN);
if(j==0) possibleMoves.remove((object)DIRECTION_LEFT);
if(j==columnLimit) possibleMoves.remove((object)DIRECTION_RIGHT);

list.remove((object)previous);
return list.get(random.nextInt(list.size()));

I'm not super sure about how java would treat the remove method on a list, so I casted the DIRECTION_X values to objects so that the object itself would get removed, not the value at the given index. You may want to create an enumeration rather than relying on integer constants.

Edit (Reversal)

This should solve both issues:

//Use a HashSet rather than an ArrayList. These are usually quite snappy (The java documentation promises O(1) for add and remove.)
// There also seems to be an EnumSet, but I have no idea how that works.
final HashSet<Integer> possibleMoves = new HashSet<>()={DIRECTION_UP,DIRECTION_RIGHT,DIRECTION_LEFT,DIRECTION_DOWN};
if(i==0) possibleMoves.remove((object)DIRECTION_UP);
if(i==rowLimit) possibleMoves.remove((object)DIRECTION_DOWN);
if(j==0) possibleMoves.remove((object)DIRECTION_LEFT);
if(j==columnLimit) possibleMoves.remove((object)DIRECTION_RIGHT);

//Reverse previous direction;
//Could also do this with a switch statement.
if(prev==DIRECTION_UP) list.remove((object)DIRECTION_DOWN);
if(prev==DIRECTION_DOWN) list.remove((object)DIRECTION_UP);
if(prev==DIRECTION_LEFT) list.remove((object)DIRECTION_RIGHT);
if(prev==DIRECTION_RIGHT) list.remove((object)DIRECTION_LEFT);

//Select a random value from the hash set. Since we can't access indexes in a //hash set, we have to use a different method of selection.
int val=Integer.MIN_VALUE;
int dir=0;
for(int d:list){
     int rand=random.nextInt();
     if(rand>=val){
        val=rand;
        dir=d;
     }
}
return dir;

Not using brackets for all your if make things hard to read. Indeed the code is shorter, but I think we've lost a lot of readability that way. — Marc-Andre, Mar 18, 2015 at 13:43

Stack Exchange Network

Get random direction based off of location and previous direction

4 Answers 4

Using a bitmask

The predefined arrays

The fast function

Testing the speed

In conclusion

Caveats

Edit (Reversal)

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
algorithm
random
or ask your own question.

Linked

Hot Network Questions

Get random direction based off of location and previous direction

4 Answers 4

Using a bitmask

The predefined arrays

The fast function

Testing the speed

In conclusion

Caveats

Edit (Reversal)

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged javaalgorithmrandom or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
java
algorithm
random
or ask your own question.