SHARE
TWEET

Dijkstra on a grid

a guest Apr 9th, 2013 142 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import numpy
  2.  
  3.  
  4. ## \param gridMap A Numpy array where 0 represents "open" and any
  5. #         other value represents "closed"
  6. # \param goals A list (set, etc.) of (x, y) tuples representing the goal
  7. #        tiles.
  8. def getHeatMap(gridMap, goals):
  9.     # A Numpy array of integers where each value is
  10.     # the distance the corresponding cell in gridMap is from any goal tile.
  11.     # Start with all non-goal tiles at -1 and all goal tiles at 0.
  12.     heatMap = numpy.ones(gridMap.shape, dtype = numpy.int32) * -1
  13.     for x, y in goals:
  14.         heatMap[(x, y)] = 0
  15.  
  16.     xVals, yVals = numpy.where(gridMap != 0)
  17.     # Maps cells we've seen to their costs. Add unreachable cells here so we
  18.     # never try to reach them.
  19.     cellToCost = dict([((xVals[i], yVals[i]), -1) for i in xrange(len(xVals))])
  20.     # Queue of cells waiting to be scanned.
  21.     cellQueue = []
  22.     # Max values to feed into xrange when getting neighbors.
  23.     maxX = gridMap.shape[0]
  24.     maxY = gridMap.shape[1]
  25.     for x, y in goals:
  26.         cellToCost[(x, y)] = 0
  27.         for xi in xrange(max(0, x - 1), min(maxX, x + 2)):
  28.             for yi in xrange(max(0, y - 1), min(maxY, y + 2)):
  29.                 if (xi, yi) not in cellToCost and gridMap[xi, yi] == 0:
  30.                     cellToCost[(xi, yi)] = 1
  31.                     heatMap[(xi, yi)] = 1
  32.                     cellQueue.append((xi, yi))
  33.  
  34.     while cellQueue:
  35.         pos = cellQueue.pop(0)
  36.         cost = cellToCost[pos]
  37.         # Find all neighbors for whom we have a new route.
  38.         for xi in xrange(max(0, pos[0] - 1), min(maxX, pos[0] + 2)):
  39.             for yi in xrange(max(0, pos[1] - 1), min(maxY, pos[1] + 2)):
  40.                 if (xi, yi) not in cellToCost:
  41.                     cellToCost[(xi, yi)] = cost + 1
  42.                     heatMap[(xi, yi)] = cost + 1
  43.                     cellQueue.append((xi, yi))
  44.     return heatMap
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top