javascript - 用于在网格中的所需位置周围查找空单元格的算法

Question

我将使用所附图片描述我的问题:

绿色 block 是我的游戏实体的起始位置。接下来我想把它移动到橙色方 block 标记的位置。但与此同时，我假设悬浮是不可能的或者/&这个 block 是一堵墙。无论哪种情况，去那里都是不可能的。所以我需要想办法找到第一个可用位置(尽可能靠近橙色方 block )让我的实体移动(在这种情况下，它要么是灰色列的顶部，要么指向橙色下方的两行正方形)。

我有一个描述网格的二维数组，其中 1 是一面墙，0 是空白空间。

data = [
    [1,1,1,1,...],
    [1,0,0,0,0,...],
    [1,0,0,...],
    ...
]

我正在以这种方式考虑解决方案(例如，我可以在 1. 处检查我的单元格下方是否有地板并结束算法，或者如果没有则继续单元格 2。 ) 但我想不出一种有效(且轻松)执行此操作的方法。

有没有人知道如何解决这个问题？我不太确定我应该向谷歌询问什么算法:)

Answer 1

您正在寻找 Q 学习算法。这是强化学习的一种形式。这是一个http://en.wikipedia.org/wiki/SARSA

基本上，您在源和目标之间多次运行模拟，并且每次都越来越接近发现目标。