Strategy: Navigation Implementation of 'right' and 'left'

[mklapp2]

Goal: Implement a method to return the next valid movement direction that is 'left' or 'right' of a desired direction

Description: My early bots seemed to get gridlocked due to being solely interesting in moving to their optimal next movement position, and not considering alternatives if it were occupied. One thing that would help immensely would be having a team standard of 'traffic rules' such as 'if two friendly bots want to get past one another, they both move to their respective right-hand side of the path'.

To implement the above 'stay to the right' standard, the concept of 'right' and 'left' must be coded in. This should be pretty easy since I think the movement directions are coded as enums and we can probably add/subtract (with rollover off the array ends) to implement this.

It is probably useful if whoever codes what 'one space left' and 'one space right' mean would also code up a second method 'next valid space left/right'.

Out of scope but also important: Storing an array of 'previously visited spaces' and if those spaces are in the direction of the goal, it means your bot had to back up (hit a wall or something) and it should not consider that space valid again until it is no longer between the bot and its goal (allow bot to back up into previous spaces, but not move forward into 'known' dead ends).

[Odyhibit]

There are turn-right and turn-left methods that can be used for this. I used similar code last year. When I get home tonight I can check if the code is good enough to warrant sending to ya.

[mklapp2]

Sounds good, I probably won't be working on Battlecode much more until tomorrow morning.

[Odyhibit]

        // do the moving go around if we are blocked.
        if (rc.canMove(dir)) {
            rc.move(dir);
            //System.out.println("I moved! Byte count " + Clock.getBytecodeNum() + "/10,000 Soldier Bytecodes this round.");
        } else if (rc.canMove(dir.rotateLeft())) {
            //if there is something blocking us - go around
            rc.move(dir.rotateLeft());
        } else if (rc.canMove(dir.rotateRight())) {
            rc.move(dir.rotateRight());
        }
        rc.setIndicatorString("trying to go " + dir + " to get to " + toMove.x + "," + toMove.y);

[Odyhibit]

the dir.rotateLeft() is just a 45 degree turn, so a second level would be required if we want to be able to turn 90 degrees

[Odyhibit]

another idea would be to step through the directions as an offset, you were alluding to this in your original message, but check the original direction, then increase the offset(45-degree increments) by 1. Then check both directions by that offset. The code would something like.

    // Alternate logic structure
    static Direction moveable_direction(RobotController rc,Direction desired_dir){
        if(rc.canMove(desired_dir)) return desired_dir;
        for (int rotation_offset = 0; rotation_offset <= 4; rotation_offset++){  // 4 is 1/2 of the 8 possible directions
            Direction left_dir = Direction.values()[desired_dir.ordinal() + ((4 - rotation_offset) % 8)];
            Direction right_dir = Direction.values()[desired_dir.ordinal() + ((8 - rotation_offset) % 8)];
            if (rc.canMove(left_dir)) return left_dir;
            if (rc.canMove(right_dir)) return right_dir;
        }
        return Direction.CENTER;
    }

[mklapp2]

@Odyhibit Thanks for the code above, that appears to implement exactly what I was alluding to. The only part I see that I want to change is the method name.

[Odyhibit]

The math is off, I have updated the version on my github

[mklapp2]

I implemented this and also made the following helper function to return an array of all movement (non-Center) directions in a clockwise order: /**

• Returns list of all non-Center directions in clockwise order with North at index 0.
• @return list of all non-Center directions in clockwise order with North at index 0. */ public static Direction[] getClockwiseMoveDirectionsN0(){ Direction[] goodDirections = new Direction[] {Direction.NORTH, Direction.NORTHEAST, Direction.EAST, Direction.SOUTHEAST, Direction.SOUTH, Direction.SOUTHWEST, Direction.WEST, Direction.NORTHWEST}; return goodDirections; }

[mklapp2]

I'm going to close this as completed. As @Odyhibit stated above, there are existing methods Direction.rotateLeft() and rotateRight(). I ended up implementing a some related helper methods that may or may not prove useful in the long run.