dijkstra.py

from pathlib import Path
from queue import Queue

def distance(dx, dy):
    return dx ** 2 + dy ** 2

def direction(dx, dy):
    horizontal = {
        -1: "WEST",
        0: "",
        1: "EAST"
    }[dx]

    vertical = {
        -1: "SOUTH",
        0: "",
        1: "NORTH"
    }[dy]

    return f"Direction.{vertical}{horizontal}"

def generate_dijkstra(vision_radius):
    output_file = Path(__file__).parent.parent / "src" / "camel_case" / "dijkstra" / f"Dijkstra{vision_radius}.java"
    print(f"Generating Dijkstra code for vision radius {vision_radius} to '{output_file}'")

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    offsets = {}

    queue = Queue()
    for (dx, dy) in directions:
        queue.put((dx, dy, 0, direction(dx, dy)))
    
    while not queue.empty():
        (dx, dy, previous_id, direction_from_previous) = queue.get()

        if (dx, dy) in offsets:
            continue

        id = len(offsets) + 1
        predecessors = []
        outer_ring = False
        
        for (direction_dx, direction_dy) in directions:
            new_dx, new_dy = dx + direction_dx, dy + direction_dy
            new_distance = distance(new_dx, new_dy)

            if new_distance < distance(dx, dy):
                if new_dx == 0 and new_dy == 0:
                    predecessors.append(0)
                else:
                    predecessors.append(offsets[(new_dx, new_dy)]["id"])
            elif new_distance <= vision_radius:
                queue.put((new_dx, new_dy, id, direction(direction_dx, direction_dy)))
            else:
                outer_ring = True

        offsets[(dx, dy)] = {
            "id": id,
            "previous_id": previous_id,
            "direction_from_previous": direction_from_previous,
            "outer_ring": outer_ring,
            "predecessors": predecessors if distance(dx, dy) > 2 else [0]
        }

    offsets_by_distance = list(sorted(offsets.keys(), key=lambda item: distance(item[0], item[1])))
    outer_ring_offsets = [(dx, dy) for (dx, dy) in offsets_by_distance if offsets[(dx, dy)]["outer_ring"]]

    content = f"""
package camel_case.dijkstra;

import battlecode.common.Direction;
import battlecode.common.GameActionException;
import battlecode.common.MapLocation;
import battlecode.common.RobotController;

// Generated by scripts/dijkstra.py
// Based on Malott Fat Cats's 2021 pathfinding
// Malott Fat Cats's 2021 post-mortem: https://www.battlecode.org/files/postmortem-2021-malott-fat-cats.pdf
public class Dijkstra{vision_radius} implements Dijkstra {{
    private static RobotController rc;

    private static int mapWidth;
    private static int mapHeight;

    private static MapLocation myLocation;
    private static int myX;
    private static int myY;
    private static int xOffset;
    private static int yOffset;
    """.strip()

    content += "\n"

    for (dx, dy) in offsets_by_distance:
        id = offsets[(dx, dy)]["id"]

        content += f"""
    private static MapLocation location{id};
    private static double distance{id};
    private static Direction direction{id};
        """.rstrip()

    content += "\n"

    content += f"""
    private static double weight;

    private static double currentDistance;
    """.rstrip()

    content += "\n"

    for (dx, dy) in outer_ring_offsets[:-1]:
        id = offsets[(dx, dy)]["id"]

        content += f"""
    private static double score{id};
        """.rstrip()

    content += "\n"

    content += f"""
    private static double maxScore;

    public Dijkstra{vision_radius}(RobotController rc) {{
        Dijkstra{vision_radius}.rc = rc;

        mapWidth = rc.getMapWidth();
        mapHeight = rc.getMapHeight();
    }}

    @Override
    public Direction getBestDirection(MapLocation target, Direction blockedDirection) throws GameActionException {{
        myLocation = rc.getLocation();
        myX = myLocation.x;
        myY = myLocation.y;
        xOffset = mapWidth - myX;
        yOffset = mapHeight - myY;
    """.rstrip()

    content += "\n"

    for (dx, dy) in offsets_by_distance:
        id = offsets[(dx, dy)]["id"]
        previous_id = offsets[(dx, dy)]["previous_id"]
        direction_from_previous = offsets[(dx, dy)]["direction_from_previous"]

        if distance(dx, dy) <= 2:
            location = f"rc.adjacentLocation({direction_from_previous})"
        else:
            location = f"location{previous_id}.add({direction_from_previous})"

        content += f"""
        location{id} = {location};
        distance{id} = 1_000_000.0;
        """.rstrip()

    content += "\n"

    for (dx, dy) in offsets_by_distance:
        id = offsets[(dx, dy)]["id"]
        predecessors = offsets[(dx, dy)]["predecessors"]

        weight = f"1.0 + rc.senseRubble(location{id})"

        if distance(dx, dy) <= 2:
            content += f"""
        if (blockedDirection != {direction(dx, dy)} && rc.canMove({direction(dx, dy)})) {{
            distance{id} = {weight};
            direction{id} = {direction(dx, dy)};
        }}
            """.rstrip()
            continue

        if dx < 0:
            switch_condition_x = "myX"
            cases_x = range(0, abs(dx))
        elif dx > 0:
            switch_condition_x = "xOffset"
            cases_x = range(0, dx + 1)
        else:
            switch_condition_x = None
            cases_x = []

        if dy < 0:
            switch_condition_y = "myY"
            cases_y = range(0, abs(dy))
        elif dy > 0:
            switch_condition_y = "yOffset"
            cases_y = range(0, dy + 1)
        else:
            switch_condition_y = None
            cases_y = []

        if switch_condition_x is None or switch_condition_y is None:
            switch_condition = switch_condition_x or switch_condition_y
            cases = cases_x if switch_condition == switch_condition_x else cases_y

            content += f"""
        switch ({switch_condition}) {{
            """.rstrip()

            for case in cases:
                content += f"""
            case {case}:
                """.rstrip()
            
            content += """
                break;
            default:
            """.rstrip()

            indent = " " * 16
        else:
            content += f"""
        switch ({switch_condition_x}) {{
            """.rstrip()

            for case in cases_x:
                content += f"""
            case {case}:
                """.rstrip()
            
            content += f"""
                break;
            default:
                switch ({switch_condition_y}) {{
            """.rstrip()
            
            for case in cases_y:
                content += f"""
                    case {case}:
                """.rstrip()
            
            content += f"""
                        break;
                    default:
            """.rstrip()

            indent = " " * 24

        content += f"""
{indent}weight = {weight};
        """.rstrip()

        for predecessor in predecessors:
            content += f"""
{indent}if (distance{predecessor} + weight < distance{id}) {{
{indent}    distance{id} = distance{predecessor} + weight;
{indent}    direction{id} = direction{predecessor};
{indent}}}
            """.rstrip()

        if dx == 0 or dy == 0:
            content += """
        }
            """.rstrip()
        else:
            content += """
                }
        }
            """.rstrip()

    content += "\n"

    content += """
        switch (target.x - myX) {
    """.rstrip()

    for current_dx in sorted(set(dx for (dx, dy) in offsets)):
        content += f"""
            case {current_dx}:
                switch (target.y - myY) {{
        """.rstrip()

        for current_dy in sorted(dy for (dx, dy) in offsets if dx == current_dx):
            id = offsets[(current_dx, current_dy)]["id"]
            content += f"""
                    case {current_dy}:
                        return direction{id};
            """.rstrip()

        content += """
                }
                break;
        """.rstrip()

    content += """
        }
    """.rstrip()

    content += "\n"
    
    content += """
        currentDistance = myLocation.distanceSquaredTo(target);
    """.rstrip()

    content += "\n"

    for (dx, dy) in outer_ring_offsets[:-1]:
        id = offsets[(dx, dy)]["id"]

        content += f"""
        score{id} = (currentDistance - location{id}.distanceSquaredTo(target)) / distance{id};
        """.rstrip()

    content += "\n"

    (last_dx, last_dy) = outer_ring_offsets[-1]
    last_id = offsets[(last_dx, last_dy)]["id"]

    score_vars = [f"score{offsets[(dx, dy)]['id']}" for (dx, dy) in outer_ring_offsets[:-1]] + [f"(currentDistance - location{last_id}.distanceSquaredTo(target)) / distance{last_id}"]
    for _ in range(len(score_vars) - 1):
        score_vars = [f"Math.max({score_vars[0]}, {score_vars[1]})"] + score_vars[2:]

    content += f"""
        maxScore = {score_vars[0]};
    """.rstrip()

    content += "\n"

    for (dx, dy) in outer_ring_offsets[:-1]:
        id = offsets[(dx, dy)]["id"]

        content += f"""
        if (maxScore == score{id}) {{
            return direction{id};
        }}
        """.rstrip()

    content += "\n"

    content += f"""
        return direction{last_id};
    }}
}}
    """.rstrip()

    with output_file.open("w+", encoding="utf-8") as file:
        file.write(content.strip() + "\n")

def main():
    for vision_radius in [20, 34, 53]:
        generate_dijkstra(vision_radius)

if __name__ == "__main__":
    main()