1

我正在制作一个类似于Greedy Spiders的游戏。简而言之,这是一款回合制游戏,其中有一只或多只蜘蛛试图接近苍蝇吃掉它们。用户的任务是通过从网上切下一小部分以释放苍蝇或诱捕蜘蛛来防止这种情况发生。有一个提示功能,显示如何完成关卡并释放苍蝇或以尽可能少的切割(移动)捕获蜘蛛。

我正在使用 A* 算法来找到到其中一只苍蝇的最短路径。该算法仍然不是很智能,因为它只找到最短路径并且没有考虑用户的切割。

我想知道的是如何实现提示功能。我现在想的是使用游戏树并重视每个结果并选择最好的,但我不确定这是否是最好的方法。

你会推荐什么来实现这样的功能?

PS。我不是要复制应用程序。我想用自己的努力做一些类似的事情,这样我就可以更好地解决问题。我想要一个想法,而不是解决方案...

4

1 回答 1

2

这是我的猜测。

  1. 在每一回合中,对所有蜘蛛使用 A* 来找到所有蜘蛛到最近的苍蝇的最短路径。以某种方式将所有边存储在某个有序数据结构中,用于每个蜘蛛的每个最短路径。如果蜘蛛有多个路径共享最短路径长度,则存储所有路径。例如,如果蜘蛛有 3 条路径可供 3 种不同的苍蝇使用,并且所有这些路径的长度均为 2,则存储所有这些路径。

  2. 按路径长度“排序”在步骤 1 中找到的路径。找出其中最短的(长度最短的)。我们称这些最短路径为最短路径

  3. 在所有这些最短路径中,尝试找到所有路径中常见(最高频率)的边。告诉玩家切掉那个特定的边缘(如果存在)。如果不存在这样的“共同”边,请告诉玩家在最短路径之一上剪下最后一条边,因为这将提供一次释放一只或多只苍蝇的最大机会。

我没有严格的证据证明这是有效的。作为一名球员,这似乎是一件最理想的事情。

想到在多条最短路径之间找到“共同边”的想法是为了在一个回合内完成几个重要目标,例如一次阻止多个蜘蛛(或一次阻止单个蜘蛛的多条路径)。可能有更高级的算法来做这个特定的事情。否则,如果不存在“共同边缘”(即所有边缘的频率 == 1),最佳策略似乎是慢慢地切掉那些处于最迫在眉睫危险的苍蝇周围的边缘。

于 2013-10-26T03:35:19.107 回答