2

我将使用附图描述我的问题：

网格

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

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

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

我正在以这种方式考虑解决方案（例如，我可以检查1.我的单元格下方是否是地板并结束算法，或者如果不是单元格则继续2.）但我想不出一种有效的方法（并且很容易）。

在此处输入图像描述

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

4

2 回答 2

1

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

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

于 2013-05-24T01:26:11.730 回答
0

如果值得麻烦的话，我认为您可以将元胞自动机用于您的案例。它本身不是人工智能，易于实现，您可以使用一种逻辑替换 A* 以及最终的定位问题。

考虑游戏实体周围的八个邻域单元。每个单元格可以是空闲的或阻塞的（0 或 1）。邻域将有 2^8 种组合，但您可能需要也可能不需要为 CA 使用那么多规则。

尝试研究一下：http ://www.cs.sun.ac.za/rw711/2012term1/documents/CABehringPathPlanning.pdf 他们为机器人中的路径规划实施了 CA，您可以对其进行调整以满足您的需要。

优点是，通过适当的规则集，只有当游戏实体到达目标周围的适当位置（最接近目标且不悬浮）时，您的 CA 才会终止。

您还可以在系统上实现多个规则集，从而使其更加健壮。

于 2013-05-24T07:55:42.697 回答