Instantly share code, notes, and snippets.

mcneja/dijkstra.py Last active Apr 16, 2018

Dijkstra fill in Python
 import heapq maxDistance = 2000 def computeDistanceMap(costMap, starts): sizeY = len(costMap) sizeX = len(costMap[0]) distMap = [[maxDistance for x in range(sizeX)] for y in range(sizeY)] # Starting positions have a distance of zero and are scheduled # for visiting at that distance pq = [] for posStart in starts: heapq.heappush(pq, (0, posStart)) while pq: dist, pos = heapq.heappop(pq) # Has this node already been visited? if distMap[pos[1]][pos[0]] <= dist: continue # Visit this node distMap[pos[1]][pos[0]] = dist # Schedule neighbors for visiting for dPos in [(-1, 0), (1, 0), (0, -1), (0, 1)]: posNew = (pos[0] + dPos[0], pos[1] + dPos[1]) if posNew[0] < 0 or posNew[0] >= sizeX: continue if posNew[1] < 0 or posNew[1] >= sizeY: continue distNew = dist + costMap[posNew[1]][posNew[0]] if distNew >= distMap[posNew[1]][posNew[0]]: continue heapq.heappush(pq, (distNew, posNew)) return distMap # Test impassableCost = 2000 passableCost = 1 def costForChar(c): return impassableCost if c == 'X' else passableCost def parseInputMap(mapIn): return [[costForChar(c) for c in row] for row in mapIn.split()] def printDistanceMap(distMap): for row in distMap: for dist in row: if dist == maxDistance: c = '-' else: c = chr(dist % 10 + ord('0')) print(c, end='') print('') inputMap=''' XXXXXXXXXXXXXXXXXXXX X.........X........X XXXXXXXXX.X...XX...X X.........X...XX...X X.X.......X...XX...X X.X.......X........X X.XXXXXX.....XXXXXXX X......X.....X.....X X......X.....X.....X XXXXXXXXXXXXXXXXXXXX ''' costMap = parseInputMap(inputMap) distMap = computeDistanceMap(costMap, [(1,1),(18,1)]) printDistanceMap(distMap)
Owner Author

mcneja commented Apr 12, 2018 • edited

 Output from this sample is: ``````-------------------- -012345678-76543210- ---------9-876--321- -876543210-987--432- -9-7654321-098--543- -0-8765432-10987654- -1------43321------- -234567-54432------- -345678-65543------- -------------------- ``````
Owner Author

mcneja commented Apr 12, 2018

 In the example there are only two costs (passable/impassable) but there could be varying movement costs. The distance field would then be more properly called a total-cost-to-reach field or something like that. Note that the impassableCost and the maxDistance can be the same thing and just need to be bigger than the largest valid distance in the map, while not being so big that math overflow is a problem. The next step up is to use the fast marching method to compute the distance field. This is a relatively simple modification to the algorithm that produces distances that approximate straight-line motion across open space.

tstavrianos commented Apr 16, 2018

 Although in theory in should be faster, in practice in csharp using a priority queue (FastPriorityQueue from https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp) its slower for the map in your example. This might be csharp specific though but it could be that after a certain map size, the priority queue will be faster than going through the entire map.