Battlecode 2021 pathfinding lecture

dials_algorithm_pseudocode.txt

DIAL'S ALGORITHM - PSEUDOCODE

Input:
    Source = starting location
    TimeToTravel[u, v] = how long to travel from u to v
    C = maximum possible time a single step takes (for example, 10)

Initialize Q = list of C+1 collections of locations
    If a location we want to expand has distance d, it will be stored in Q[d % (C+1)]
Initialize Expanded = an array of Booleans for the map, all false
Initialize Distance = an array of all infinity (or some big number)


Distance[Source] = 0
Add Source to Q[0]

for (int i = 0; true; i = (i+1) % (C+1))
    // in other words, keep cycling around Q
    // but you should decide when you want to stop

    while Q[i] is not empty:
        Let u = remove any element from Q[i]
        If Expanded[u] is true:
            // Don't expand a location you've already expanded before
            continue

        for each location v that you can reach from u:
            // This is the expand step: we will expand from u to v
            Let T = Distance[u] + TimeToTravel[u, v]
            if T < Distance[v]:
                Distance[v] = T
                Add v to Q[Distance[v] % (C+1)]  // This works because, Distance[v] <= C

        Expanded[u] = true

Output: Distance[]
    You can also keep track of how you got to each location when you Expand.


HOW IS THIS DIFFERENT TO BFS / DIJKSTRA?

Dijkstra: Use a real PriorityQueue instead of Q, which pretends to be a PriorityQueue
    Dial's relies on TimeToTravel being small non-negative integers

BFS: Use a Queue instead of Q, because TimeToTravel is either 1 or infinite