前言
在游戏中，我们经常想要找到从一个位置到另一个位置的路径。我们不仅试图找到最短的距离;我们还想考虑旅行时间。要找到此路径，我们可以使用图形搜索算法，该算法在地图表示为图形时起作用。 A *是图搜索的热门选择。广度优先搜索是最简单的图搜索算法，所以让我们从那里开始说起，然后慢慢到A *。
表达地图
研究算法时要做的第一件事就是理解数据。输入是什么？什么是输出？
输入：图形搜索算法，包括A *，以“图形”作为输入。图表是一组位置
（“节点”）和它们之间的连接（“边缘”）。这是我给A *的图表：
A *没有看到任何其他内容。它只能看到图表。它不知道某物是在室内还是在室外，或者它是房间还是门口，或者有多大的区域。它只看到图表！
输出：A *找到的路径由图形节点和边缘组成。边缘是抽象的数学概念。A *会告诉您从一个位置移动到另一个位置，但它不会告诉您如何。请记住，它对房间或门没有任何了解;所有它看到的是图表。您必须决定A *返回的图形边缘是指从一个瓷砖移动到另一个瓷砖，还是沿着直线行走，打开一扇门，游泳或沿着弯曲的路径行进。
权衡：对于任何给定的游戏地图，有许多不同的方法可以使路径查找图给予A *。上面的地图使大多数门口成为节点;如果我们进入边缘的道路怎么办？如果我们使用寻路网格怎么办？
寻路图不必与游戏地图使用的图相同。网格游戏地图可以使用非网格路径寻找图，反之亦然。 A *运行速度最快，图形节点最少;网格通常更容易使用，但会产生大量节点。此页面包含A *算法，但不包括图形设计;有关图表的详情，请参阅我的其他页面。对于页面其余部分的解释，我将使用网格，因为它更容易可视化概念。
算法
有很多算法在图表上运行。我将介绍这些：
广度优先搜索：在所有方向上均匀探索。这是一种非常有用的算法，不仅适用于常规路径查找，还适用于程序图生成，流场寻路，距离图和其他类型的地图分析。
Dijkstra的算法：（也称为统一成本搜索）允许我们优先考虑要探索的路径。它不是平等地探索所有可能的路径，而是倾向于降低成本路径。我们可以分配更低的成本来鼓励在道路上行驶，更高的成本来避免森林，更高的成本来阻止靠近敌人，以及更多。当移动成本变化时，我们使用它而不是广度优先搜索。
A *是Dijkstra算法的修改，针对单个目的地进行了优化。 Dijkstra的算法可以找到所有位置的路径; A *查找到一个位置的路径，或几个位置中最近的路径。它优先考虑似乎更接近目标的路径。
我将从最简单的广度优先搜索开始，一次添加一个功能将其转换为A *。
广度优先搜索（Breadth First Search）
所有这些算法的关键思想是我们跟踪一个称为前沿的扩展环。在网格上，此过程有时称为“泛洪填充”，但相同的技术适用于非网格。启动动画以查看边界如何展开：
我们如何实现这个？重复这些步骤，直到边界为空：
从边界中挑选并移除一个位置。
通过查看邻居来扩展它。我们尚未访问的任何邻居，我们添加到边界，也添加到访问集。
让我们近距离看到这一点。磁贴按照我们访问它们的顺序编号。逐步查看扩展过程：
It’s only ten lines of (Python) code:
frontier= Queue()frontier.put(start
)visited= {}visited[start] = Truewhile notfrontier.empty():current=frontier.get() fornextin graph.neighbors(current): ifnextnot invisited:frontier.put(next)visited[next] = True
此循环是此页面上图搜索算法的精髓，包括A *。但是我们如何找到最短的路径呢？循环实际上并不构造路径;它只告诉我们如何访问地图上的所有内容。这是因为广度优先搜索不仅可以用于寻找路径，还可以用于其中。在本文中，我展示了它如何用于塔防，但它也可以用于距离地图，程序地图生成和许多其他事情。虽然我们想用它来查找路径，但是让我们修改循环以跟踪我们来自每个访问过的位置的位置，并将访问集重命名为came_from表（表的键是访问集）：
网友评论