View Single Post
Old October 1, 2019, 02:26   #10
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,918
Derakon is on a distinguished road
So, here's generally how I'd go about implementing that kind of heat map:
Code:
cell_stack = [player_pos]
next_stack = set()
depth = 0
while cell_stack or next_stack:
  if not cell_stack:  # Done processing this depth, move to the next
    depth++
    cell_stack = list(next_stack)
    next_stack = set()
  pos = cell_stack.pop()
  if map[pos] > depth:  # Haven't processed this cell before
    map[pos] = depth
    for neighbor in neighbors(pos):
      if (neighbor is traversible and map[neighbor] > depth):
        next_stack.add(neighbor)
In other words, you have a stack of cells to process that are at the same "depth" (distance from the player), and a stack of cells that will be at the next depth. All neighbors of cells in the current stack that have not yet been processed get added to the next stack. Once the current stack is empty, increment depth and start processing the next stack instead.

Note that next_stack is actually a set, so that any cell can only be added to it at most once. I convert to a list when next_stack becomes the current stack for easier popping. I also check whether a cell has been processed both before adding it to a stack and after popping it. The former helps keep the stack size down, the latter accounts for the potential that there's multiple ways to reach a cell...though it might not be necessary in this case.
Derakon is online now   Reply With Quote