算法与计算机科学qiao.github.io
PathFinding.js 寻路可视化
PathFinding.js
2014 — 2019，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 PathFinding.js 的交互式可视化页面：在网格上设置起点、终点和障碍，观察不同寻路算法如何一步步搜索并找到路径。它把抽象的寻路过程变成可动手试验的演示。
为什么经久不衰：它把有门槛的算法变成直观的网格实验，既能学习原理，也方便对比不同寻路策略，因此多年来仍值得一玩。
HN 评论精选
用一次性全图 BFS 预计算到目标的路径，可分摊到多帧，并比多敌人逐个 A* 更稳定。
我在自己写的游戏里经常用的一招是：对整个场地做一次不终止的广度优先搜索，得到从任意格子到目标格子的路径数据。好处包括：BFS 很容易拆到多帧执行，摊平访问每个格子的开销；当敌人数量增加但目标数量少时，最坏情况开销降低；实现简单；也可以根据寻路层需要满足的最远距离提前终止；不会出现病态的最坏情况，开阔场地反而是最坏情况。我第一次用在 Robokill，一个常同屏 20+ 敌人追踪玩家的 Flash 游戏，当时估计开销约等于对约 5 个敌人做 A*。在游戏里，常见的最坏情况基本决定一切——稳定 60fps 比偶尔 100fps 掉到 30fps 好得多。
reitzensteinm查看英文原文
One trick I've used quite a bit in games I've written is to do a breadth-first search of the entire playfield, with no termination, resulting in data for how to get from any tile to the destination. This has a few nice advantages: * Breadth first is trivially broken up to iterate over multiple frames, amortizing the cost of visiting each tile * It reduces the worst case as the number of enemies scales up but the destination counts are low. * The implementation in general is very simple * You can still early terminate if you keep track of the farthest distance a pathfinding layer needs to satisfy. * No pathological, worst case situations where a playfield becomes very expensive to pathfind. An open field is the worst case. I first used this in Robokill, a flash game which often had 20+ enemies on the same screen tracking the player. I estimated at the time that it cost about as much as doing A* on ~5 enemies. In games, the worst (common) case is basically all that matters - a constant 60fps is significantly better than 100fps dropping to 30fps occasionally.
递归模式在稍复杂图上性能很差。
递归可视化即使在中等复杂图上也很慢，否则这工具真的很不错。
newbrict查看英文原文
The recursive visualization is really slow on even moderately complex graphs, otherwise it's a really neat tool
评论者推荐 Red Blob Games 的 A* 入门作为权威补充材料。
这几乎可以说是寻路教程/可视化的权威指南（作者用 D3.js 做示例）：http://www.redblobgames.com/pathfinding/a-star/introduction.html
nacs查看英文原文
Pretty much the definitive guide for pathfinding how-to/visualization (the author used D3.js for the examples): http://www.redblobgames.com/pathfinding/a-star/introduction.html
建议增加多算法对比统计和随机迷宫功能。
如果它能同时跑所有算法，并显示每种算法用了多少步、最终路径长度，那就更酷了。再加一个“随机迷宫”按钮也不错。
tlrobinson查看英文原文
It would be cool if it ran all the algorithms and showed you how many steps it took and the final path length for each one. Also, a "random maze" button would be nice.
历次讨论
同类还值得读
位运算技巧集
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编辑精选