“气味”算法：基于邻域递归计算网格中的值（python）

Question

我正在尝试创建一个算法，对于网格中的任何给定点（2d列表-带有一些障碍物/墙），计算每个网格单元的值。你知道吗

该值取决于从原点穿过“迷宫”的距离。 起始点的值为“1”，对于离开该点的每个单元格，该值将减小（例如0.9）。你知道吗

最终，我将使用这个算法，让吃豆人风格的鬼魂跟随气味轨迹在迷宫中追逐吃豆人（可能不是最好的算法，但我是作为练习来做的，所以请让我们坚持这个）。你知道吗

这是我目前掌握的代码：

我定义了一个函数，用于在网格中查找“最高邻居”（hN），该函数运行良好：

def hN(grid, x, y):
    a = b = c = d = e = f = g = h = 0
    if x > 0 and y > 0: #all the conditions ensure that no error are given at the edges
        a = grid[x-1][y-1]
    if x > 0:
        b = grid[x-1][y]
    if x > 0 and y < len(grid[0]):
        c = grid[x-1][y+1]
    if y > 0:
        d = grid[x][y-1]
    if y < len(grid[0]):
        e = grid[x][y+1]
    if x < len(grid) and y > 0:
        f = grid[x+1][y-1]
    if x < len(grid):
        g = grid[x+1][y]
    if x < len(grid) and y < len(grid[0]):
        h = grid[x+1][y+1]
    return max(a, b, c, d, e, f, g, h)

下面我有“气味填充”功能（气味，因为它将计算一个“气味”，这是更强大的目标旁边-填充，因为我是基于洪水填充）。你知道吗

2部分：第一部分（“works”）是递归部分，第二个函数将被调用，因为它将初始单元格值设置为1

def smellFillWork(grid, smellGrid, x, y):
if grid[x][y] == 1: #base case: the "maze" grid has 1s as walls and 0s as 'floors'.
    return
else: #set the 4 neighbours UP, DOWN, LEFT, RIGHT to *0.9
    if x > 0:
        smellGrid[x-1][y] = hN(smellGrid, x-1, y) * 0.9
    if y > 0:
        smellGrid[x][y-1] = hN(smellGrid, x, y-1) * 0.9
    if x < len(grid)-1:
        smellGrid[x+1][y] = hN(smellGrid, x+1, y) * 0.9
    if y < len(grid[0])-1:
        smellGrid[x][y+1] = hN(smellGrid, x, y+1) * 0.9

#here the recursion is called:
if x > 0:
    smellFillWork(grid, smellGrid, x - 1, y)
if y > 0:
    smellFillWork(grid, smellGrid, x, y - 1)
if x < len(grid) - 1:
    smellFillWork(grid, smellGrid, x + 1, y)
if y < len(grid[0]) - 1:
    smellFillWork(grid, smellGrid, x, y + 1)




def smellFill(grid, smellGrid, x, y):
    smellGrid[x][y] = 1 #set the initial cell at 1
    smellFillWork(grid,smellGrid, x, y) # call the function above

你知道为什么上面的方法不起作用吗？我得到一个无限递归循环。你知道吗

免责声明：我是一个初学者，几乎自学成才，请原谅我的拙劣风格

谢谢

Answer 1

我没有读你写的每一行代码，但是为什么你不写一个距离函数，为网格中的任意一点找到你远离气味源的步数。假设距离函数的输出是n，然后计算0.9 ^ n。你知道吗

如果你想更接近你自己的解决方案，那么我认为你最好避免递归的解决方案。你只需要写一个算法，从产生气味的细胞开始填充细胞。你知道吗

从你的描述来看，障碍物/墙是否重要还不够清楚。你知道吗