Skip to content

Instantly share code, notes, and snippets.

@j-mao
Created January 16, 2021 07:44
Show Gist options
  • Save j-mao/27d9de0a609ae4fd31c89d99be9565cb to your computer and use it in GitHub Desktop.
Save j-mao/27d9de0a609ae4fd31c89d99be9565cb to your computer and use it in GitHub Desktop.
Battlecode 2021 pathfinding lecture
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment