Bik*_*nja 8 algorithm path-finding
我需要一个算法,它会给我一条从起始节点到结束节点的路径,但路径必须有一个确切数量的节点,否则路径查找应该失败.
为了扩展,我有一个瓷砖网格.移动只能是紧邻的上,下,左或右平铺(意思是没有对角线移动).瓦片在路径中可以使用和不可以使用的规则有很多,但大多数情况下可以归结为简单的布尔来判断瓦片是否可以使用(这可以在开始算法之前计算出来)但是,给我带来麻烦的是,我有一条路径必须具有的距离,这意味着,从一个瓷砖到相邻瓷砖的每一次移动都是一个距离,整个路径应该有一个指定的距离,不多也不少.此外,一旦瓷砖被踩到(但算法开始时所有瓷砖都可用),它不能再次踩到,有点像玩老蛇游戏你我要注意不要吃自己.
我看过Dijkstra/A*并且我用google搜索算法进行寻路,但据我所知,所有这些算法都集中在最短的路径上,这对我没什么好处.只要遵循上述规则,我不关心它是哪条路径.
我错过了什么,这样的算法和算法是否已经存在,或者是否有一种简单的方法来修改Dijkstra/A*来给出这个结果？由于我不是母语为英语的人,我可能使用了错误的术语,所以我欢迎这种算法的关键字建议.
这里是我的意思,当我说它必须是和确切的距离,并不能使用相同的瓷砖两次.
假设距离必须为7.现在让我们用O标记可以在路径中使用的图块,不能使用的图块和X,S的起点和E的目标.
X X X X X X X X O O E S O O X O O O O O O
如果没有距离限制,可以向左走,问题就解决了.如果有距离限制,但没有"不能踩到相同的瓷砖"限制,可以下降一次,然后向左,然后向右,然后向左,然后向右,然后向左,然后向上并到达目标.由于存在这两种限制,因此需要向右,向下,向左,向左,向上,向右然后才能到达目标.但是,如果情况是这样的话,就没有有效的路径.
X X X X X X X X O O E S O O X X O O O X O
如果它是相关的,我正在用C#开发这个棋盘游戏.
至于最大距离,这是距离所在的范围.玩家将掷骰子并获得数字1-6.如果玩家获得6,他会再次投掷骰子,如果他再次获得6,则一次又一次直到他没有得到6.距离是结果数加上玩家拾取的物品数量,理论上可以最多8,但通常是0-3,maaaybe 4.
另一方面,我刚收到新订单,游戏规则改为允许在相同的路径上两次踩到同一个位置,我相信这个过程很简单,但是我会把这个问题保留为我认为它有很好的答案,可以帮助那些情况下的人.