算法与计算机科学redblobgames.com编辑精选
A* 寻路算法入门
Introduction to A*
2014 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 Red Blob Games 出品的 A* 寻路算法入门教程。作者 Amit Patel 用可交互的图示，从广度优先搜索、Dijkstra 算法一步步过渡到 A*，讲清启发式函数如何引导搜索方向、以及它为什么能又快又准。
为什么经久不衰：把抽象的图搜索算法做成了可以动手拖拽、改墙的实时演示，循序渐进、直观透彻，十几年来一直是寻路入门的最佳读物。
HN 评论精选
A* 并非万能，很多场景用更简单的启发式搜索换取速度与内存更划算。
很好的文章——我最近做寻路相关的东西，找到的 A* 资料都不怎么样，而这篇组织得非常好。重要提醒：A* 或其他“最优路径”算法并不总是首选，有些场景下用次优路径换取更快的速度和更少的内存更划算，甚至比文中带 A* 的贪心最佳优先搜索还快。如果用递归回溯配上不错的启发式（比如选离目标直线距离最近的节点），在很多情况下又快又理想，线性时间和内存即可完成；它永远不会“失败”，但在复杂地形下有时会给出很差的路径。在路径是否最优并不关键的场合（比如城镇居民随便走动），这完全够用。当然也可以按需混用多种算法。
gavanwoolery查看英文原文
Excellent article - I recently worked on some pathfinding stuff and the material I found on A* was not that great but this is very well laid out. Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A* shown here. If you use recursive backtracking with a decent set of heuristics (i.e. choose the node with the closest distance to the goal, "as the crow flies"), it can be be fast and ideal in many situations (it will always give an ideal path when there are few hook or concave shapes to deal with, which in many games or applications is often the case). It can be done in linear time and memory - it is important to note the cost of adding and searching nodes in the algorithm as well. It will never "fail" but it will produce very bad paths sometimes in complex situations, although even then it occasionally produces ideal paths. In many situations where having an ideal path is not critical (say, townspeople just walking about doing their business) this can work well. Of course, you can use multiple algorithms or even mix them depending on what you are trying to achieve. RBT can be a good starting point just because it is so easy (maybe the easiest fail-safe algorithm outside of brute force?). Secondary note: it is also good to subdivide your space - it does not need to be something complex like a sparse octree (in fact, that will make it harder to write and get good performance with in many situations). Rather consider something like two levels of nodes. On a 2D map, say you were to divide it into subsets of NxN grids of nodes. Each one of these node grids attaches to its neighbor based on whether or not it is traversable in that direction (i.e. no matter where you enter the node grid, there is a path out in that direction). This allows you to easily find a "high level" path which can be rapidly changed or discarded based on changing circumstances.
文中图示全部可交互，可以自己动手实验。
不太显眼的一点是：这个页面上的所有图示其实都是实时可交互的演示，你可以拖动实体，也可以随意改变墙的形状。
sjwright查看英文原文
It's not immediately obvious, but all the diagrams on that page are actually live and interactive demonstrations. You can move the entities, and you can reshape the walls as much as you like.
细节讲解到位，比如搜索节点与地图坐标的区别；作者还用 6502 汇编亲手实现过 A*。
既然 Amit 本人似乎在读这个帖子——感谢你更新这篇 A* 入门（原本就已经很棒了！），我很喜欢你把算法一块块拆开讲。它核心其实很简单，但初次接触时有些微妙之处很容易忽略，比如“搜索节点”和“地图坐标”的区别（假设是经典 2D 游戏地图）。我今年早些时候用 6502 汇编实现 A* 玩得很开心，先从 Python 写起，一路经 Objective-C、C 降到汇编，最后手工优化关键路径。
MagerValp查看英文原文
Since Amit's apparently here reading, great job on updating your A* introduction (which was already excellent!), I really like how you break it down piece by piece. While it's a very simple algorithm at its core, there are some really subtle nuances that are easy to miss when you first approach it, e.g. the difference between a search node and a map coordinate (assuming classic 2D game maps). I had some fun earlier this year implementing A* in 6502 assembler, starting with Python and working my way down through Objective-C and C before finally hand-optimizing the critical paths in asm. Articles are here for those who enjoy that kind of thing: http://magervalp.github.io/2014/05/02/priority-queue-in-asm.html http://magervalp.github.io/2014/05/07/astar-in-asm.html The code is available on github too: https://github.com/MagerValp/AsmAstar
启发式远不止距离函数，廉价且有信息量的评估函数都可用。
这又是篇好文章，但我觉得关于启发式的一些更广义的思考被略过了。启发式可以比“两点之间的距离”有趣得多。这不算严厉批评——在网格寻路这个语境下，复杂启发式确实未必需要。很久以前我第一次读到 A* 时，记得有例子说国际象棋局面的静态评估函数也可以当作有用的启发式，比如把棋子往棋盘中心发展通常更好。对我来说那是关于启发式的一个“啊哈”时刻：只要代价低、有时还能提供信息，相对于搜索开销就值得用。
dj-wonk查看英文原文
Again, a great article, but I feel like some of the general thinking behind heuristics is getting lost. Heuristics can be significantly more interesting than distance between two points. This isn't a huge criticism. In this context -- pathfinding on a grid -- complicated heuristics may not be needed. When I first read about A* a long time ago I remember, for example, reading about how static summaries of chess board positions may be useful heuristics. Developing pieces towards the center of the board is often better, for example. To me, seeing this was an "ah ha" moment for heuristics: use them if they are cheap and (sometimes) informative, relative to the search cost.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选