数字华容道AI解题原创

大家好，我是维卡，上期视频做了用open c a做的数字华容道游戏，本期在这个基础上我们提升一点难度来实现数字华容道的I自动还原。现在视频中播放的就是AI自动还原的过程，绿色的点是当前还原的数字起点，黄色的是终点，白色即是可行动的路径。数字还容到基本还原的方法网上会有不少讲解，而要在程序中实现数字移动的指定区域，最核心的就是路径规划的算法。数字华容道的路径规划算法也是基于A心算法原理实现的，只不过不会存在斜线移动的情况。关于A心算法和GPS跳点巡路算法的讲解及源码可以看我公众号里路径规划的相关文章，接下来看一下在当前这个四乘四的格中。

规划从数字13到数字六的路径，我们需要定义一个开启列表和一个关闭列表。每次从开启列表中取出到达终点使用的体力最少的数字。体力的计算公式是F等于G加H，其中这是从起点到当前节点消耗的体力，H为当前节点到终点需要的体力。第一步，将起点13存放到开启列表中，首先检测开启列表中体力最少的点，因为里面只有一个13，所以取出13后先存放到关闭列表中，检测13上、下、左、右四个可移动的点，排除掉超出地图范围和已经在关闭列表中还有地图的障碍点中存放的点，得到了九和十四两个数字是可以移动的，九和14的负节点就是13，然后再分别计算出九和14的体力值。

存放到开启列表中，这里面九和14计算的F值实际上是一样的，所以我在算法中加入了优先移动方向的参数，默认是往上移动，每移动一格消耗的体力为一，而属于优先移动方向的消耗体力为0.9，这样最后计算F体力数字九会比14少。然后再从开启列表中查找F值最小的点为数字九，取出数字九在存放到关闭列表中，重复这样的方式，直到开启列表中出现终点六后，通过终点六一步一步的向上反推，就可以生成当前的行动路径。路径规划的算法说完，我们来看看程序中的具体实现，计算出当前要还原数字的新增路径后，需要实现空白格及数字零移动到当前还原数字的下一步。

骨格中，所以计算零到数字下一格的路径中，需要把当前要还原的数字所在的位置设置成障碍点，不允许移动。当零移动到指定位置后，解除当前数字位置的障碍点，然后再和零进行位置互换，通过这个方式是当前的数字最终按路径的规划移动到指定的位置。解题过程中会遇到一些特殊问题，像现在数字四按照规划路线移动到第二行最后的位置时，此时数字一二三都已经是障碍点，不允许移动了，所以空白格也就是数字零没有路径可以移动到数字七的位置，这时就进入特殊处理，将原来数字123的障碍点取消，通过左移的方式把数字四先还原回去后，再将数字123移动回来。第二行数字八的处理方式和四的处理方式。

是一样的，最后两行的处理主要是把九和十移动到左边，12和11移动到右边后就是固定的还原套路了。想了解的可以直接下载我的源码看看是如何实现的。为了体现还原的每一步过程，代码中每行动一步都将图像显示出来，并做了200毫秒的延时。把还原的过程显示关闭后，经过多次测试，平均速度在0.05秒以内，速度还是比较快的，是时候表演真正的技术了。