游戏寻路 [英] Path finding for games

问题描述

在所有类型的游戏中使用了哪些寻路算法?(无论如何，在字符移动的所有类型中)是否使用过 Dijkstra 的?我并不是真的想编写任何代码；只是做一些研究，不过如果你粘贴伪代码或其他东西，那就没问题了(我可以理解 Java 和 C++).

What are some path finding algorithms used in games of all types? (Of all types where characters move, anyway) Is Dijkstra's ever used? I'm not really looking to code anything; just doing some research, though if you paste pseudocode or something, that would be fine (I can understand Java and C++).

我知道 A* 就像在 2D 游戏中使用的算法.这很好，但是那些不是基于网格的 2D 游戏呢?诸如帝国时代或林克的觉醒之类的东西.没有可导航到的明显方形空间，那么它们有什么作用?

I know A* is like THE algorithm to use in 2D games. That's great and all, but what about 2D games that are not grid-based? Things like Age of Empires, or Link's Awakening. There aren't distinct square spaces to navigate to, so what do they do?

3D 游戏有什么作用?我读过这个东西 http://www.ai-blog.net/archives/000152.html，我听说它是​​该主题的权威，但它并没有真正解释如何，一旦设置了网格，路径查找就完成了.如果他们使用的是 A*，那么在 3D 环境中如何完成这样的事情?样条曲线究竟是如何处理圆角的?

What do 3D games do? I've read this thingy http://www.ai-blog.net/archives/000152.html, which I hear is a great authority on the subject, but it doesn't really explain HOW, once the meshes are set, the path finding is done. IF A* is what they use, then how is something like that done in a 3D environment? And how exactly do the splines work for rounding corners?

推荐答案

Dijkstra 算法计算到图中所有节点的最短路径，这些节点从起始位置可达.对于普通的现代游戏来说，这既不必要又昂贵.

Dijkstra's algorithm calculates the shortest path to all nodes in a graph that are reachable from the starting position. For your average modern game, that would be both unnecessary and incredibly expensive.

您区分了 2D 和 3D，但值得注意的是，对于任何基于图形的算法，搜索空间的维数都没有区别.您链接到的网页讨论了航点图和导航网格；两者都是基于图形的，原则上可以在任意数量的维度上工作.尽管没有可移动到的不同方形空间"，但在 AI 可以移动到的空间中存在着 离散的插槽"，这些空间是游戏设计师精心布置的.

You make a distinction between 2D and 3D, but it's worth noting that for any graph-based algorithm, the number of dimensions of your search space doesn't make a difference. The web page you linked to discusses waypoint graphs and navigation meshes; both are graph-based and could in principle work in any number of dimensions. Although there are no "distinct square spaces to move to", there are discrete "slots" in the space that the AI can move to and which have been carefully layed out by the game designers.

总结一下，A* 实际上是在 3D 游戏中使用的算法，就像在 2D 游戏中一样.让我们看看 A* 是如何工作的:

Concluding, A* is actually THE algorithm to use in 3D games just as much as in 2D games. Let's see how A* works:

1. 开始时，您知道当前位置的坐标，并且你的目标位置.你乐观估计到目的地的距离，例如直线的长度起始位置和目标之间的线.
2. 考虑图中的相邻节点.如果其中之一是您的目标(或包含它，如果是导航网格)，您就完成了.
3. 对于每个相邻节点(在导航网格的情况下，这可以是多边形的几何中心或其他类型的中点)，估计沿那里旅行的相关成本为两个措施的总和:你走过的路径的长度远，以及对距离的另一种乐观估计必须被覆盖.
4. 按照估计成本对上一步中的选项进行排序连同您之前考虑过的所有选项，然后选择估计成本最低的选项.从第 2 步开始重复.

1. At the start, you know the coordinates of your current position and your target position. You make an optimistic estimate of the distance to your destination, for example the length of the straight line between the start position and the target.
2. Consider the adjacent nodes in the graph. If one of them is your target (or contains it, in case of a navigation mesh), you're done.
3. For each adjacent node (in the case of a navigation mesh, this could be the geometric center of the polygon or some other kind of midpoint), estimate the associated cost of traveling along there as the sum of two measures: the length of the path you'd have traveled so far, and another optimistic estimate of the distance that would still have to be covered.
4. Sort your options from the previous step by their estimated cost together with all options that you've considered before, and pick the option with the lowest estimated cost. Repeat from step 2.

有些细节我没有在这里讨论，但这应该足以说明 A* 如何基本上独立于您空间的维数.您还应该能够理解为什么这适用于连续空间.

There are some details I haven't discussed here, but this should be enough to see how A* is basically independent of the number of dimensions of your space. You should also be able to see why this works for continous spaces.

有一些密切相关的算法可以处理标准 A* 搜索中的某些问题.例如，递归最佳优先搜索 (RBFS) 和简化的内存有界 A* (SMA*) 需要更少的内存，而学习实时 A* (LRTA*) 允许代理在计算完整路径之前移动.不知道现在的游戏有没有实际使用这些算法.

There are some closely related algorithms that deal with certain problems in the standard A* search. For example recursive best-first search (RBFS) and simplified memory-bounded A* (SMA*) require less memory, while learning real-time A* (LRTA*) allows the agent to move before a full path has been computed. I don't know whether these algorithms are actually used in current games.

至于圆角，可以使用距离线(圆弧代替圆角)或任何类型的 spline 函数用于全路径平滑.

As for the rounding of corners, this can be done either with distance lines (where corners are replaced by circular arcs), or with any kind of spline function for full-path smoothing.

此外，算法可能依赖于搜索空间上的梯度(其中空间中的每个点都与一个值相关联)，而不是图形.这些可能不会在大多数游戏中应用，因为它们需要更多的时间和内存，但无论如何可能会很有趣.示例包括各种爬山算法(默认情况下是实时的)和潜在字段 方法.

In addition, algorithms are possible that rely on a gradient over the search space (where each point in space is associated with a value), rather than a graph. These are probably not applied in most games because they take more time and memory, but might be interesting to know about anyway. Examples include various hill-climbing algorithms (which are real-time by default) and potential field methods.

也存在从连续空间中程序化获取图的方法，例如 单元分解、Voronoi 骨架化 和 概率路线图骨架化.前者会产生与导航网格兼容的东西(尽管可能很难使它与手​​工制作的导航网格同样有效)，而后两者会产生更像航点图的结果.所有这些，以及潜在场方法和 A* 搜索，都与机器人技术相关.

Methods to procedurally obtain a graph from a continuous space exist as well, for example cell decomposition, Voronoi skeletonization and probabilistic roadmap skeletonization. The former would produce something compatible with a navigation mesh (though it might be hard to make it equally efficient as a hand-crafted navigation mesh) while the latter two produce results that will be more like waypoint graphs. All of these, as well as potential field methods and A* search, are relevant to robotics.

来源:

• 人工智能:现代方法，第 2 版
• 算法设计与分析导论，第二版

• Artificial Intelligence: A Modern Approach, 2nd edition
• Introduction to The Design and Analysis of Algorithms, 2nd edition

这篇关于游戏寻路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！