Dijkstra fill in Python

dijkstra.py

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)

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

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.

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.