Instantly share code, notes, and snippets.

@mcneja /dijkstra.py
Last active Apr 16, 2018

Embed
What would you like to do?
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)
@mcneja

This comment has been minimized.

Show comment
Hide comment
@mcneja

mcneja Apr 12, 2018

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

mcneja commented Apr 12, 2018

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-------
--------------------
@mcneja

This comment has been minimized.

Show comment
Hide comment
@mcneja

mcneja 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.

Owner

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

This comment has been minimized.

Show comment
Hide comment
@tstavrianos

tstavrianos 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.

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment