Python游戏中地图的最短路径求解

简介：
本篇文章探讨了如何在Python游戏开发中运用算法寻找地图上的最短路径，详细介绍了解决方案及其实现方法。 一．题目要求：根据给定的图完成游戏地图从起点到目标点最短路径寻找问题。 二．设计思路： 首先对游戏地图进行设定，使用矩阵来模拟游戏的地图结构。将可以通过的位置赋值为0，障碍物区域赋值为无穷大（inf）。考虑到地图的实际大小和范围，起始点与终点分别被赋予特定的数值99以示区分。 从起点A开始逐步向外层扩展路径长度，每增加一层pathlen就加一。通过一个列表Q来存储需要进行下一步探索的节点，并用另一个列表P记录当前正在探索的所有可能位置。 当搜索到目标点B时即视为找到一条可行路径；如果在尝试所有可能性后仍未发现从起点A到达终点B的方法，则意味着两者之间没有通路可寻。 为了确定最短路径，我们从终点B开始回溯，在其周围八个方向上寻找标记值小于当前节点的相邻位置，并逐步向初始点推进直到找到标记为1的位置为止。