MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_NextPart_01C7AE6E.0E9DB2C0" 此文档为“单个文件网页”，也称为“Web 档案”文件。如果您看到此消息，但是您的浏览器或编辑器不支持“Web 档案”文件。请下载支持“Web 档案”的浏览器，如 Microsoft Internet Explorer。 ------=_NextPart_01C7AE6E.0E9DB2C0 Content-Location: file:///C:/2C3B5C92/AmitAStar.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" Amit's A star Page中译文 - GameRes.com

GameRes游戏开发资源网= http://www.gameres.com

 

Amit= 's A star Page中译= 文

 

译序=

这篇文章很适合= A*算法的初&#= 23398;者，可惜网上没找到翻෻= 3;版的。本着好东西不&= #25954;独享的想法，也为= 102;锻炼一下英文，本人= ;译了这篇文章。

由于本人英文水= 平非常有限，六级考= 0102;两次加一块不超过370分，= 因此本译文难免存在= 8382;题。不过也算是抛ం= 2;引玉，希望看到有更&= #22810;的游戏开发方面的= 248;秀译作出现，毕竟中= ;文的优秀资料太少了&#= 65292;中国的游戏开发者į= 40;路不好走。

本人能力有限，= 译文中有小部分词句= 3454;在难以翻译，因此ੀ= 2;时保留英文原文放在&= #35793;文中。对于不敢确= 450;翻译是否准确的词句= ;，本人用圆括号保留&#= 20102;英文原文，读者可É= 97;对照着加以理解。<= /p>

A*算法本身&#= 26159;很简单的，因此原ă= 91;中并没有过多地讨论= A*算法本身&#= 65292;而是花了较大的篇ñ= 33;讨论了用于保存OPEN和<= span lang=3DEN-US>CLOSED集的= 数据结构，以及A*算法的变&#= 31181;和扩展。

编程实现A*是简单的，读者= 可以用STL对本= 文中的伪代码加以实= 9616;（本人已花一天时໾= 8;实验过基本的A*搜索）。但是最= 重要的还是对A*本身的理&#= 35299;，这样才可以在自ð= 49;的游戏中处理各种千= 变万化的情况。

翻译本文的想法= 产生于2006年<= span lang=3DEN-US>5月，实际&#= 23436;成于2007年<= span lang=3DEN-US>4月到6月，非常&#= 24813;愧。

最后，本译文仅= 供交流和参考ᦁ= 2;对于因本译文放到网&= #19978;而产生的任何问题A= 292;本人不负任何责任。= ;

　　= 　　　　　　　　　= 2288;　　　　　　　　ӌ= 8;　　　　　蔡鸿于南&= #24320;大学软件学院

　　= 　　　　　　　　　= 2288;　　　　　　　　ӌ= 8;　　　　　　      2007年6月9日

原文地址：http://theory.stanford.edu/~amitp/GameProgramming/

相关链接：http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html#Pat= hs

 

我们尝试解决的= 问题是把一个游戏对= 5937;（game object）从= 出发点移动到目的地= 2290;路径搜索(Pathfinding)的目= 标是找到一条好的路= 4452;——避免障碍物、敌= 人，并把代价（燃料= 5292;时间，距离，装备ᦁ= 2;金钱等）最小化。运&= #21160;（Movement）的= 目标是找到一条路径= 4182;且沿着它行进。把ࠥ= 1;注的焦点仅集中于其&= #20013;的一种方法是可能= 340;。一种极端情况是，= ;当游戏对象开始移动&#= 26102;，一个老练的路径Ā= 28;索器（pathfinder）外= 加一个琐细的运动算= 7861;（movement algorithm）可= 以找到一条路径，游= 5103;对象将会沿着该路঍= 2;移动而忽略其它的一&= #20999;。另一种极端情况= 159;，一个单纯的运动系= ;统（movement-only system）将不会搜索一条ū= 35;径（最初的“路径”&#= 23558;被一条直线取代）ʌ= 92;取而代之的是在每一= 个结点处仅采取一个= 7493;骤，同时考虑周围௚= 0;环境。同时使用路径&= #25628;索(Pathfinding)和运= 动算法（movement algorithm）将= 会得到最好的效果。

 

1 导言= ;... 5

1.1 算ૢ= 1;... 6

1.2 Dijkstra算ૢ= 1;与最佳优先搜索... 6

1.3 A*算ૢ= 1;... 9

2 启发式算法... 11

2.1 A*对࡫= 1;发式函数的使用... 11

2.2 速ॷ= 0;还是精确度？... 11

2.3 衡ດ= 7;单位... 12

2.4 精ఋ= 0;的启发式函数... 12

2.4.1 预计算的精确启ࡡ= 7;式函数... 12

2.4.2 线性精确启发式౛= 9;法... 13

2.5 网੬= 4;地图中的启发式算法<= /span>... 13

2.5.1 曼哈顿距离... 13

2.5.2 对角线距离... 14

2.5.3 欧几里得距离= ... 14

2.5.4 平方后的欧几里এ= 1;距离... 15

2.5.5 Breaking ties 15

2.5.6 区域搜索... 19

3 Implementation notes 19

3.1 概略... 19

3.2 源代码... 20

3.3 集合的表示... 20

3.3.1 未排序数组或链ඤ= 0;... 21

3.3.2 排序数组... 21

3.3.3 排序链表... 21

3.3.4 排序跳表... 21

3.3.5 索引数组... 21

3.3.6 哈希表... 22

3.3.7 二元堆... 22

3.3.8 伸展树... 22

3.3.9 HOT队列... 23

3.3.10 比较... 23

3.3.11 混合实现... 24

3.4 与游戏循环的交ߛ= 4;... 24

3.4.1 提前退出... 24

3.4.2 中断算法... 24

3.4.3 组运动... 25

3.4.4 细化... 25

4 A*算法的变种... 25

4.1 beam search. 25

4.2 迭代深化... 25

4.3 动态衡量... 26

4.4 带宽搜索... 26

4.5 双向搜索... 26

4.6 动态A*与终身计划A*. 27

5 处理运动障碍物... 27

5.1 重新计算路径= ... 27

5.2 路径拼接... 28

5.3 监视地图变化= ... 29

5.4 预测障碍物的运ࡄ= 0;... 29

6 预计算路径的空间代= 价... 29

6.1 位置VS方向... 29

6.2 路径压缩... 30

6.2.1 位置存储... 30

6.2.2 方向存储... 30

6.3 计算导航点... 31

6.4 极限路径长度= ... 31

6.5 总结... 31


1 <= span style=3D'font-size:12.0pt;line-height:125%;font-family:SimSun;mso-ascii-fon= t-family: "Times New Roman";mso-hansi-font-family:"Times New Roman"'>导言=

　z= 88;移动一&= #20010;简单的物体（object）看起来是容= 131;的。而路径搜索是复= ;杂的。为什么涉及到&#= 36335;径搜索就产生麻烦É= 02;？考虑以下情况：

　z= 88;物体（<= span lang=3DEN>unit）最初位于地ࢳ= 0;的底端并且尝试向顶&= #37096;移动。物体扫描的= 306;域中(粉红色部分)= 没有任何东西显示= 427;不能向上移动，因此= ;它持续向上移动。在&#= 38752;近顶部时，它探测Ò= 40;一个障碍物然后改变= 移动方向。然后它沿= 0528;U形障碍物找到它&= #30340;红色的路径。相反= 340;，一个路径搜索器（= ;pathfinder）将会扫描一= 个更大的区域（淡蓝= 3394;部分），但是它能ࠉ= 0;到不让物体(unit)走向凹形障碍= 289;而找到一条更短的路= ;径(蓝色路径）。

　　然而你可以扩展&= #19968;个运动算法，用于= 545;付上图所示的障碍物= ;。或者避免制造凹形&#= 38556;碍， 或者把凹形出口标识= 0026;危险的(只有当目的地在&= #37324;面时才进去):

　　比起&#= 19968;直等到最后一刻才Ö= 57;现问题，路径搜索器= 让你提前作出计划。不४= 2;路径搜索的运动(movement)可以= 在很多种情形下工作= 5292;同时可以扩展到更ࣩ= 0;的情形，但是路径搜&= #32034;是一种更常用的解= 915;更多问题的方法。=

1.1 算法<= /span>

　　计算&#= 26426;科学教材中的路径Ā= 28;索算法在数学视角的= 图上工作——由边联ń= 67;起来的结点的集合。= 一个基于图块(tile)拼接的游戏地图= 可以看成是一个图，每个图块(tile)是一个结点，并= 在每个图块之间ஹ= 1;一条边：

　　目前&#= 65292;我会假设我们使用É= 08;维网格(grid)。稍= 后我将讨论如何在你= 0340;游戏之外建立其他౲= 7;型的图。

　　许多AI领域或算&#= 27861;研究领域中的路径Ā= 28;索算法是基于任意<= span lang=3DEN-US>(arbitrary)的图= 设计的，而不是基于= 2593;格(grid-based)的图= 。我们可以找到一些= 3021;使用网格地图的特ঝ= 5;的东西。有一些我们&= #35748;为是常识，而算法= 182;不理解。例如，我们= ;知道一些和方向有关&#= 30340;东西：一般而言，å= 14;果两个物体距离越远= ，那么把其中一个物= 0307;向另一个移动将花ว= 4;多的时间；并且我们&= #30693;道地图中没有任何= 192;密通道可以从一个地= ;点通向另一个地点。&#= 65288;我假设没有，如果ć= 77;的话，将会很难找到= 一条好的路径，因为= 0320;并不知道要从何处ঀ= 0;始。）

1.2 Dijkstra算= 861;与最佳优先搜索<= span lang=3DEN-US style=3D'font-size:12.0pt;line-height:125%;font-family:SimSun'= >

ӌ= 8;　Dijkstra算法从物体所&#= 22312;的初始点开始，访ſ= 82;图中的结点。它迭代= 检查待检查结点集中= 0340;结点，并把和该结୅= 7;最靠近的尚未检查的&= #32467;点加入待检查结点&= 598;。该结点集从初始结= ;点向外扩展，直到到&#= 36798;目标结点。Dijkstra算法保证能找&#= 21040;一条从初始点到目Ċ= 31;点的最短路径，只要= 所有的边都有一个非= 6127;的代价值。（我说“= ;最短路径”是因为经= 4120;会出现许多差不多௾= 1;的路径。）在下图中&= #65292;粉红色的结点是初= 987;结点，蓝色的是目标= ;点，而类菱形的有色&#= 21306;域（注：原文是teal areas）则是Dijkstra= 算法扫描过的区域 = 290;颜色最淡的区域是那= ;些离初始点最远的，&#= 22240;而形成探测过程（exploration）的边境（frontier）：=

ӌ= 8;　最佳优先搜索（BFS）算法按照类似= ;的流程运行，不同的&#= 26159;它能够评估（称为×= 51;发式的）任意结点到= 目标点的代价。与选= 5321;离初始结点最近的ಮ= 7;点不同的是，它选择&= #31163;目标最近的结点。BFS不能保证找到一= ;条最短路径。然而，&#= 23427;比Dijkstra算法快的多，&#= 22240;为它用了一个启发ó= 35;函数（heuristic function）快速地导= 向目标结点。例如，= 2914;果目标位于出发点௚= 0;南方，BFS将趋向于导向南= ;方的路径。在下面的&#= 22270;中，越黄的结点代ŝ= 20;越高的启发式值（移= 动到目标的代价高）= 5292;而越黑的结点代表ว= 4;低的启发式值（移动&= #21040;目标的代价低）。$= 825;表明了与Dijkstra 算法相比，BFS运行得更快。

ӌ= 8;　然而，这两个例子&= #37117;仅仅是最简单的情= 917;——地图中没有障碍&= #29289;，最短路径是直线= 340;。现在我们来考虑前= ;边描述的凹型障碍物&#= 12290;Dijkstra算法运行得较&#= 24930;，但确实能保证找Ò= 40;一条最短路径：

&= #12288;　另一方面，BFS运行得= ;较快，但是它找到的&#= 36335;径明显不是一条好į= 40;路径：

ӌ= 8;　问题在于BFS是基于贪心策略= ;的，它试图向目标移&#= 21160;尽管这不是正确的ū= 35;径。由于它仅仅考虑= 到达目标的代价，而= 4573;略了当前已花费的ߣ= 5;价，于是尽管路径变&= #24471;很长，它仍然继续$= 208;下去。

　　&#= 32467;合两者的优点不是ć= 56;好吗？1968年发明的A*算法就是把启发式方= 法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一&#= 36215;的算法。有点不同į= 40;是，类似BFS的启发式方法经= ;常给出一个近似解而&#= 19981;是保证最佳解。然Ň= 80;，尽管A*基于无法保证最佳解的启发ঁ= 5;方法，A*却能保证找到一= 条最短路径。

1.3 A*算法<= /span>

　　我将&#= 38598;中讨论A*算法。A*是路径搜&#= 32034;中最受欢迎的选择ʌ= 92;因为它相当灵活，并= 且能用于多种多样的= 4773;形之中。

　　和其&#= 23427;的图搜索算法一样ʌ= 92;A*潜在地搜&#= 32034;图中一个很大的区à= 95;。和Dijkstra一样= ，A*能用于搜&#= 32034;最短路径。和BFS一样= ，A*能用启发&#= 24335;函数（注：原文为heuristic）引= 导它自己。在简单的= 4773;况中，它和BFS一样= 快。

　　在凹&#= 22411;障碍物的例子中，A*找到一条&#= 21644;Dijkstra算法= 一样好的路径：

　　成功&#= 30340;秘决在于，它৚= 6;Dijkstra算法= （靠近初始点的结点= 5289;和BFS算法= （靠近目标点的结点= 5289;的信息块结合起来。ࢷ= 2;讨论A*的标准术&#= 35821;中，g(n)表示= 从初始结点到任意结= 8857;n的代价，h(n)表示= 从结点n到目标点&#= 30340;启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示= 远离目标的结点而teal(g)表示= 远离初始点的结点。= 4403;从初始点向目标点ల= 7;动时，A*权衡这两&#= 32773;。每次进行主循环ą= 02;，它检查f(n)最小= 的结点n，其中f(n) =3D g(n) + h(n)。<= /p>

2 启发式算法

　　启发&#= 24335;函数h(n)告诉= A*从任意结&#= 28857;n到目标结&#= 28857;的最小代价评估值z= 90;选择一个好的启发式= 函数是重要的。

2.1 A*对启发式函数&#= 30340;使用

　　启发&#= 24335;函数可以控制A*的行为：

　　所以&#= 25105;们得到一个很有趣į= 40;情况，那就是我们可= 以决定我们想要从A*中获得什&#= 20040;。理想情况下（注ʍ= 06;原文为At exactly the right point），我们想最快地ô= 71;到最短路径。如果我= 们的目标太低，我们= 0173;会得到最短路径，ߎ= 1;过速度变慢了；如果&= #25105;们的目标太高，那= 105;们就放弃了最短路径= ;，但A*运行得更&#= 24555;。

在游戏中，A*的这个特&#= 24615;非常有用。例如，Ë= 20;会发现在某些情况下= ，你希望得到一条好= 0340;路径（"good" path）而不是一条完美į= 40;路径（"perfect" path）。为了权衡g(n)和<= span lang=3DEN-US>h(n)，你= 可以修改任意一个。

注:在学术上，如果= 启发式函数值是对实= 8469;代价的低估，A*算法被称&#= 20026;简单的A算法（原&#= 25991;为simply A）。= 然而，我继续称之为A*，因为在&#= 23454;现上是一样的，并Ç= 88;在游戏编程领域并不= 区别A和= A*。

2.2 速度还是精确&#= 24230;？

　　A*改变它自&#= 24049;行为的能力基于启Ö= 57;式代价函数，启发式= 函数在游戏中非常有= 9992;。在速度和精确度ߔ= 3;间取得折衷将会让你&= #30340;游戏运行得更快。= 312;很多游戏中，你并不= ;真正需要得到最好的&#= 36335;径，仅需要近似的ì= 01;足够了。而你需要什= 么则取决于游戏中发= 9983;着什么，或者运行ଅ= 6;戏的机器有多快。

　　假设&#= 20320;的游戏有两种地形ʌ= 92;平原和山地，在平原= 中的移动代价是1而在山地&#= 21017;是3。A* is going to search three times as far along flat land as it= does along mountainous land. 这是因为有可能= 有一条沿着平原到山= 2320;的路径。把两个邻৶= 9;点之间的评估距离设&= #20026;1.5可以= 加速A*的搜索过&#= 31243;。然后A*会将3和= 1.5比较，这并不比把3和= 1比较差。It is not as dissatisfied with mountainous terrain, so it won't spend as much = time trying to find a way around it. Alternatively, you can speed up up A*'s sea= rch by decreasing the amount it searches for paths around mountains―just = tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Eith= er approach gives up ideal paths to get something quicker.

速度和精确度之间į= 40;选择前不是静态的。= 你可以基于CPU的速= 度、用于路径搜索的= 6102;间片数、地图上物߮= 7;（units）的= 数量、物体的重要性= 2289;组（group）的= 大小、难度或者其他= 0219;何因素来进行动态௚= 0;选择。取得动态的折&= #34935;的一个方法是，建= 435;一个启发式函数用于= ;假定通过一个网格空&#= 38388;的最小代价是1，然后建&#= 31435;一个代价函数（cost function）用= 于测量（scales）：=

g’(n) =3D 1 + alpha * (= g(n) – 1 )

　　如果alpha是<= span lang=3DEN-US>0，则改进&#= 21518;的代价函数的值总ą= 59;1。这种情&#= 20917;下，地形代价被完Ð= 40;忽略，A*工作变成&#= 31616;单地判断一个网格Ö= 87;否通过。如果alpha是<= span lang=3DEN-US>1，则最初&#= 30340;代价函数将起作用ʌ= 92;然后你得到了A*的所有优&#= 28857;。你可以设置alpha的值= 为0到= 1的任意值。

　　你也&#= 21487;以考虑对启发式函ă= 68;的返回值做选择：绝= 对最小代价或者期望= 6368;小代价。例如，如ੜ= 4;你的地图大部分地形&= #26159;代价为2的草地，&#= 20854;它一些地方是代价È= 26;1的道路，&#= 37027;么你可以考虑让启Ö= 57;式函数不考虑道路，= 而只返回2*距离。

　　速度&#= 21644;精确度之间的选择ñ= 82;不是全局的。在地图= 上的某些区域，精确= 4230;是重要的，你可以࣌= 2;于此进行动态选择。&= #20363;如，假设我们可能= 312;某点停止重新计算路= ;径或者改变方向，则&#= 22312;接近当前位置的地Ą= 41;，选择一条好的路径= 则是更重要的，因此= 0026;何要对后续路径的౹= 4;确度感到厌烦？或者&= #65292;对于在地图上的一= 010;安全区域，最短路径= ;也许并不十分重要，&#= 20294;是当从一个敌人的Ĉ= 49;庄逃跑时，安全和速= 度是最重要的。（译= 2773;注：译者认为这里১= 1;的是，在安全区域，&= #21487;以考虑不寻找精确= 340;最短路径而取近似路= ;径，因此寻路快；但&#= 22312;危险区域，逃跑的ê= 33;全性和逃跑速度是重= 要的，即路径的精确= 4230;是重要的，因此可ߣ= 7;多花点时间用于寻找&= #31934;确路径。）

2.3 衡量单位

　A*计算f(n) =3D g(n) = + h(n)。为了对这两个= 值进行相加，这两个值必须使用相ࡧ= 6;的衡量单位。如果g(n)用小= 时来衡量而h(n)用米= 来衡量，那么A*将会认为g或者h太大或者&#= 22826;小，因而你将不能ô= 71;到正确的路径，同时= 你的A*算法将运&#= 34892;得更慢。

2.4 精确的启发式&#= 20989;数

　　如果&#= 20320;的启发式函数精确ß= 20;等于实际最佳路径（= optimal path），= 如下一部分的图中所= 1034;，你会看到此时A*扩展的结&#= 28857;将非常少。A*算法内部&#= 21457;生的事情是：在每Ç= 68;结点它都计算f(n) =3D g(n) + h(n)。当= h(n)精确= 地和g(n)匹配= （译者注：原文为match）时= ，f(n)的值= 在沿着该路径时将不= 0250;改变。不在正确路঍= 2;（right path）上= 的所有结点的f值均大于&#= 27491;确路径上的f值（译者&#= 27880;：正确路径在这里ò= 12;该是指最短路径）。= 如果已经有较低f值的结点&#= 65292;A*将不考虑f值较高的&#= 32467;点，因此它肯定不Ê= 50;偏离最短路径。

2.4.1 预计算的精确启= 发式函数

　　构造&#= 31934;确启发函数的一种Ą= 41;法是预先计算任意一= 对结点之间最短路径= 0340;长度。在许多游戏௚= 0;地图中这并不可行。&= #28982;后，有几种方法可= 197;近似模拟这种启发函= ;数：

  • Fit a coarse grid on top of= the fine grid. Precompute the shortest path between any pair of coarse grid locations.
  • Precompute the shortest path between any pair of waypoin= ts. This is a generalization of the coarse grid approach.

　　（译者= ;：此处不好翻译，暂&#= 26102;保留原文）

然后添加一个启= 发函数h’用于评估从任意߮= 1;置到达邻近导航点（<= /span>waypoints）的= 代价。（如果愿意，= 1518;者也可以通过预计౛= 9;得到。）最终的启发&= #24335;函数可以是：

h(n) =3D = h'(n, w1) + distance(w1, w2), h'(w2, goal)

或者如果&#= 20320;希望一个更好但是ć= 56;昂贵的启发式函数，= 则分别用靠近结点和= 0446;标的所有的w1,w2对对= 上式进行求值。（译= 2773;注：原文为or if you want a better but more expensive heuristic, evaluate= the above with all pairs w1, w2 that are close to the node and the goal, respectively.）

2.4.2 线性精确启发式= 算法

　　在特&#= 27530;情况下，你可以不Ű= 90;过预计算而让启发式= 函数很精确。如果你= 6377;一个不存在障碍物ࡴ= 4;slow地形= ，那么从初始点到目= 6631;的最短路径应该是ߌ= 8;条直线。

　　如果&#= 20320;正使用简单的启发ó= 35;函数（我们不知道地= 图上的障碍物），则= 3427;应该和精确的启发ঁ= 5;函数相符合（译者注&= #65306;原文为match）。= 如果不是这样，则你= 0250;遇到衡量单位的问ག= 4;，或者你所选择的启&= #21457;函数类型的问题。

2.5 网格地图中的&#= 21551;发式算法

　　在网&#= 26684;地图中，有一些众û= 52;周知的启发式函数。=

2.5.1 曼哈顿距离

标准的启发式函数ą= 59;曼哈顿距离（Manhattan distance）。= 考虑你的代价函数并= 5214;到从一个位置移动࠸= 0;邻近位置的最小代价<= /span>D。因此，&#= 25105;的游戏中的启发式Ñ= 89;数应该是曼哈顿距离= 的D倍：

       H(n) =3D D * (abs ( n.x – goal.x ) + abs ( n.y &= #8211; goal.y ) )

你应该使用&= #31526;合你的代价函数的"= 913;量单位。

(Note: the above image has a tie-breaker<= /span> added to the heuristic.}

（译者= ;注：曼哈顿距离——<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>两点在= ;南北方向上的距离加&#= 19978;在东西方向上的距ķ= 63;，即D（I，J）=3D|XI-XJ|+|YI-YJ|。对于= ;一个具有正南正北、&#= 27491;东正西方向规则布ì= 16;的城镇街道，从一点= 到达另一点的距离正= 6159;在南北方向上旅行௚= 0;距离加上在东西方向&= #19978;旅行的距离因此曼= 704;顿距离又称为出租车= ;距离，曼哈顿距离不&#= 26159;距离不变量，当坐Ċ= 31;轴变动时，点间的距= 离就会不同——<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>百度知= ;道）

2.5.2 对角线距离

如果在你的&= #22320;图中你允许对角运= 160;那么你需要一个不同= ;的启发函数。（4 east, 4 north= ）的= 曼哈顿距离将变= 成8*D。然= 而，你可以简单地移= 1160;（4 northeast）代= 替，所以启发函数应= 5813;是4*D。这= 个函数使用对角线，= 0551;设直线和对角线的ߣ= 5;价都是D：

h(n) =3D D * max(abs(n.x - goal.x)= , abs(n.y - goal.y))

如果对角线&= #36816;动的代价不是D，但类= ;似于D2 =3D sqrt(2) * D，则上= ;面的启发函数不准确&#= 12290;你需要一些更准确ʌ= 88;原文为sophisticated）的东= ;西：

h_diagonal(n) =3D min(abs(= n.x - goal.x), abs(n.y - goal.y))

h_straight(n) =3D (abs(n.x= - goal.x) + abs(n.y - goal.y))

h(n) =3D D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

这里，我们&= #35745;算h_diagonal(n)：沿= 着斜线可以移动的步= 5968;；h_straight(n)：曼= 哈顿距离；然后合并= 6825;两项，让所有的斜ಬ= 7;步都乘以D2，剩下的&#= 25152;有直线步(注意这= ;里是曼哈顿距离的步&#= 25968;减去2倍的斜= ;线步数)都乘以D。

2.5.3 欧几里得距离<= /span>

如果你的单&= #20301;可以沿着任意角度= 227;动（而不是网格方向= ;），那么你也许应该&#= 20351;用直线距离：

h(n) =3D D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

然而，如果&= #26159;这样的话，直接使= 992;A*时将会= ;遇到麻烦，因为代价&#= 20989;数g不会= match启发函= ;数h。因为= ;欧几里得距离比曼哈༿= 9;距离和对角线距离都&= #30701;，你仍可以得到最= 701;路径，不过A*将运行= ;得更久一些：

2.5.4 平方后的欧几里得距离=

我曾经看到&= #19968;些A*的网页= ;，其中提到让你通过&#= 20351;用距离的平方而避Ð= 13;欧几里得距离中昂贵௚= 0;平方根运算：

h(n) =3D D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

不要这样做&= #65281;这明显地导致衡量= 333;位的问题。当A*计算= f(n) =3D g(n) + h(n)，距离= ;的平方将比g的代价大很&= #22810;，并且你会因为启= 457;式函数评估值过高而= ;停止。对于更长的距&#= 31163;，这样做会靠近g(n)的极端= ;情况而不再计算任何&#= 19996;西，A*退化成= ;BFS：

2.5.5 Breaking ties<= span lang=3DEN-US style=3D'font-size:12.0pt;line-height:125%'>=

导致低性能&= #30340;一个原因来自于启= 457;函数的ties（注：= ;这个词实在不知道应&#= 35813;翻译为什么）。当ĉ= 76;些路径具有相同的<= span lang=3DEN style=3D'color:black;mso-ansi-language:EN'>f值的时= ;候，它们都会被搜索&#= 65288;explored），尽= ;管我们只需要搜索其&#= 20013;的一条：

Ties in f values.

为了解决这&= #20010;问题，我们可以为= 551;发函数添加一个附加= ;值（译者注：原文为small tie breaker）。附= ;加值对于结点必须是&#= 30830;定性的（也就是说ʌ= 92;不能是随机的数），= 而且它必须让f值体现= ;区别。= ;因为A*对f值排序= ;，让f值不同= ;意味着只有一个"equivalent"= 的f值会被= ;检测。

一种添加附&= #21152;值的方式是稍微改= 464;（译者注：原文为= nudge）h的衡量= ;单位。如果我们减少&#= 34913;量单位（译者注：Ö= 07;文为scale it downwards），那= ;么当我们朝着目标移&#= 21160;的时候f将逐渐= ;增加。很不幸，这意&#= 21619;着A*倾向于= ;扩展到靠近初始点的&#= 32467;点，而不是靠近目Ċ= 31;的结点。我们可以增= 加衡量单位（译者注= 5306;原文为scale it downwards sca= le h upwards slightly）（甚至是0.1%），= A*就会倾= ;向于扩展到靠近目标&#= 30340;结点。

heuristic *=3D (1.0 + p)

选择因子p使得= p < 移动一= ;步（step）的最= ;小代价 / 期望的= ;最长路径长度。假设&#= 20320;不希望你的路径超Ű= 07;1000步（= step），你= ;可以使p =3D 1 / 1000<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>。添加= ;这个附加值的结果是&#= 65292;A*比以前= ;搜索的结点更少了。

Tie-break= ing scaling added to heuristic.

当存在障碍&= #29289;时，当然仍要在它= 204;周围寻找路径，但要= ;意识到，当绕过障碍&#= 29289;以后，A*搜索的= ;区域非常少：

Tie-break= ing scaling added to heuristic, works nicely with obstacles.<= /p>

Steven van Dijk建议，一个&= #26356;直截了当的方法是= 226;h传递到= ;比较函数（comparison function）。当= ;f值相等= ;时，比较函数检查h，然后= ;添加附加值。

一个不同的&= #28155;加附加值的方法是A= 292;倾向于从初始点到目= ;标点的连线（直线）&#= 65306;

dx1 =3D current.x - goal.x

dy1 =3D current.y - goal.y

dx2 =3D start.x - goal.x

dy2 =3D start.y - goal.y

cross =3D abs(dx1*dy2 - dx2*dy1)=

heuristic +=3D cross*0.001

这段代码计&= #31639;初始-目标向= ;量（start to goal vector）和当= ;前-目标向= ;量（current point to goal = vector）的向= ;量叉积（vector cross-product）。= When these vectors don= 't line up, the cross product will be larger.结果是，这&= #27573;代码选择的路径稍= 494;倾向于从初始点到目= ;标点的直线。当没有&#= 38556;碍物时，A*不仅搜= ;索很少的区域，而且&#= 23427;找到的路径看起来非常棒：

Tie-break= ing cross-product added to heuristic, produces pretty paths.<= /p>

然而，因为&= #36825;种附加值倾向于从= 021;始点到目标点的直线= ;路径，当出现障碍物&#= 26102;将会出现奇怪的结ĉ= 24;（注意这条路径仍是= 最佳的，只是看起来= 4456;奇怪）：

Tie-break= ing cross-product added to heuristic, less pretty with obstacles.

为了交互地&= #30740;究这种附加值方法= 340;改进，请参考James Macgill的A*确applet（http://www.ccg.leeds.a= c.uk/james/aStar/ &= #65289;[如果链= ;接无效，请使用这个&#= 38236;像（http://www.vision.ee.e= thz.ch/~buc/astar/AStar.html）]（译者= ;注：两个链接均无效）Ӎ= 0;使用“Clear”以清= 除地图，选择地图对= 5282;的两个点。当你使ஷ= 2;“Classic A*”方法= ，你会看到附加值的= 5928;果。当你使用“Fudge”方法= ，你会看到上面给启= 1457;函数添加叉积后的效果Ӎ= 0;

然而另一种&= #28155;加附加值的方法是A= 292;小心地构造你的A*优先队= ;列，使新插入的具有&#= 29305;殊f值的结= ;点总是比那些以前插&#= 20837;的具有相同f值的旧= ;结点要好一些。

你也许也想&= #30475;看能够更灵活地（#= 793;者注：原文为sophisticated）添加= ;附加值的AlphA*算法（= ;http://home1.stofanet.= dk/breese/papers.html），不= ;过用这种算法得到的&#= 36335;径是否能达到最佳É= 73;在研究中。AlphA*具有较= ;好的适应性，而且可&#= 33021;比我在上面讨论的ƀ= 68;加值方法运行得都要= 好。然而，我所讨论= 0340;附加值方法非常容ਵ= 1;实现，所以从它们开&= #22987;吧，如果你需要得= 040;更好的效果，再去尝= ;试AlphA*。

2.5.6 区域搜索

&= #12288;　如果你想搜索邻近目标的任意Ç= 81;确定结点，而不是某= 个特定的结点，你应= 5813;建立一个启发函数h&= #8217;(x)，使得= ;h&= #8217;(x)为h1(x), h2(x), h3(x)。。。的最小值，Ň= 80;这些h1, h2, h3是邻= 近结点的启发函数。= 8982;而，一种更快的方ૢ= 1;是让A*仅搜索目&#= 26631;区域的中心。一旦Ë= 20;从OPEN集合= 中取得任意一个邻近= 0446;标的结点，你就可ߣ= 7;停止搜索并建立一条&= #36335;径了。

3 Implementation notes=

3.1 概略=

&= #12288;　如果不考虑具体= 454;现代码，A*算法是= ;相当简单的。有两个&#= 38598;合，OPEN集和= CLOSED集。其= ;中OPEN集保存= ;待考查的结点。开始&#= 26102;，OPEN集只包= ;含一个元= ;素：初始结点。CLOSED集保存= ;已考查过的结点。开&#= 22987;时，CLOSED集是空= ;的。如果绘成图，OPEN集就是= ;被访问区域的边境（frontier）而= CLOSED集则是= ;被访问区域的内部（interior）。每= ;个结点同时保存其父&#= 32467;点的指针因此我们Ö= 87;以知道它是如何被找= 到的。

&= #12288;　在主循环中重复= 320;从OPEN集中取= ;出最好的结点n（f值最小= ;的结点）并检查之。&#= 22914;果n是目标= ;结点，则我们的任务&#= 23436;成了。否则，结点n被从= OPEN集中删= ;除并加入CLOSED集。然= ;后检查它的邻居n&= #8217;。如果= ;邻居n&= #8217;在CLOSED集中，= ;那么它是已经被检查&#= 36807;的，所以我们不需Š= 01;考虑它*；如果= ;n&= #8217;在OPEN集中，= ;那么它是以后肯定会&#= 34987;检查的，所以我们Ĩ= 16;在不考虑它*。否则= ;，把它加入OPEN集，把= ;它的父结点设为n。到达= ;n&= #8217;的路径= ;的代价g(n’)，设定= ;为g(n) + movementcost(n,= n’)。

(*)这里我忽略了Ç= 68;个小细节。你确实需= 要检查结点的g值是否= ;更小了，如果是的话&#= 65292;需要重新打开（re-open）它。= ;

OPEN =3D priority queue containing START

CLOSED =3D empty set

while lowest rank in OPEN is not the GOAL:

  current= =3D remove lowest rank item from OPEN

  add cur= rent to CLOSED

  for nei= ghbors of current:

    co= st =3D g(current) + movementcost(current, neighbor)

    if= neighbor in OPEN and cost less than g(neighbor):

      remove neighbor from OPEN, because new path is better<= o:p>

    if= neighbor in CLOSED and cost less than g(neighbor): **

      remove neighbor from CLOSED

    if= neighbor not in OPEN and neighbor not in CLOSED:

      set g(neighbor) to cost

      add neighbor to OPEN

      set priority queue rank to g(neighbor) + h(neighbor)

      set neighbor's parent to current

 

reconstruct reverse path from goal to start

by following parent pointers

(**) This should never happen if you have an admissib= le heuristic. However in games we often have inadmissible heuristics.

3.2 源代= 码

我自己= ;的（旧的）C++A*代码是= ;可用的：path.cpp (http://theory.stanford.edu/~amitp/ GameProgramming/path.cpp)和path.h (http://theory.stanford.edu/~amitp/GameProgramming/ path.h)，但是= ;不容易阅读。还有一&#= 20221;更老的代码（更慢į= 40;，但是更容易理解）= ，和很多其它的A*实现一= ;样，它在Steve Woodcock'= 的游戏= ;AI页面（= ;http://www.gameai.com/ai.html）。=

在网上= ;，你能找到C，C++，Visual Basic ，Java(http://www.cuspy.= com/software/pathfinder/ doc/)&= #65292;Flash/Director/Lingo, = C#(http://www.c= odeproject.com/csharp/CSharpPathfind.asp), Delphi, Lisp, Python, Perl, 和Prolog 实现的= ;A*代码。= ;一定的阅读Justin Heyes-Jones的C++实现（= ;http://www.geocities.com/jheyesjo= nes/astar.html）。=

3.3 集合= 的表示

你首先= ;想到的用于实现OPEN集和= CLOSED集的数= ;据结构是什么？如果&#= 20320;和我一样，你可能ø= 19;到“数组”。你也可&#= 33021;想到“链表”。我们= ;可以使用很多种不同&#= 30340;数据结构，为了选ý= 21;一种，我们应该考虑= 我们需要什么样的操= 0316;。

在OPEN集上我= ;们主要有三种操作：&#= 20027;循环重复选择最好į= 40;结点并删除它；访问= 邻居结点时需要检查= 3427;是否在集合里面；෹= 5;问邻居结点时需要插&= #20837;新结点。插入和删&= 500;最佳是优先队࠵= 5;（http://members.xoom.co= m/killough/heaps.html）的典= ;型操作。

选择哪= ;种数据结构不仅取决&#= 20110;操作，还取决于每ķ= 81;操作执行的次数。检= 查一个结点是否在集= 1512;中这一操作对每个ඪ= 7;访问的结点的每个邻&= #23621;结点都执行一次。= 024;除最佳操作对每个被= ;访问的结点都执行一&#= 27425;。被考虑到的绝大ä= 10;数结点都会被访问；= 不被访问的是搜索空= 8388;边缘（fringe）的结点。当ť= 80;估数据结构上面的这= 些操作时，必须考虑fringe(F)的最大= ;值。

另外，= ;还有第四种操作，虽&#= 28982;执行的次数相对很ë= 69;，但还是必须实现的= 。如果正被检查的结= 8857;已经在OPEN集中（= ;这经常发生），并且&#= 22914;果它的f值比已= ;经在OPEN集中的= ;结点要好（这很少见&#= 65289;，那么OPEN集中的= ;值必须被调整Ӎ= 0;调整操作包括删除结&= #28857;（f值不是= ;最佳的结点）和重插&#= 20837;。这两个步骤必须ŝ= 87;最优化为一个步骤，= 这个步骤将移动结点= 2290;

3.3.1 未排序数组或链= 表

最简单= ;的数据结构是未排序&#= 25968;组或链表。集合关Ŀ= 95;检查操作（Membership test= ）很慢= ;，扫描整个结构花费O(F)。插入= ;操作很快，添加到末&#= 23614;花费O(1)。查找= ;最佳元素（Finding the best eleme= nt）很慢= ;，扫描整个结构花费O(F)。对于= ;数组，删除最佳元素&#= 65288;Removing the best elem= ent）花费= ;O(F)，而链= ;表则是O(1)。调整= ;操作中，查找结点花&#= 36153;O(F)，改变= ;值花费O(1)。

3.3.2 排序数组

为了加= ;快删除最挂操作，可&#= 20197;对数组进行排序。Ɓ= 98;合关系检查操作将变= 成O(log F)，因为= ;我们可以使用折半查&#= 25214;。插入操作会很慢ʌ= 92;为了给新元素腾出空= 间，需要花费 O(F)以移动= ;所有的元素。查找最&#= 20339;元素操作会很快，Þ= 40;为它已经在末尾了所= 以花费是O(1)。如果= ;我们保证最佳排序至&#= 25968;组的尾部（best sorts to the end of the array），删除最佳Ð= 03;素操作花费将是O(1)。调整= ;操作中，查找结点花&#= 36153;O(logF)，改变= ;值/位置花= ;费O(F)。

3.3.3 排序链表

在排序= ;数组中，插入操作很&#= 24930;。如果使用链表则Ö= 87;以加速该操作。集合= 关系检查操作很慢，= 8656;要花费O(F)用于扫= ;描链表。插入操作是&#= 24456;快的，插入新元素Ö= 82;花费O(1)时间，= ;但是查找正确位置需&#= 35201;花费O(F)。查找= ;最佳元素很快，花费O(1)时间，= ;因为最佳元素已经在&#= 34920;的尾部。删除最佳Ð= 03;素也是O(1)。调整= ;操作中，查找结点花&#= 36153;O(F)，改变= ;值/位置花= ;费O(1)。

3.3.4 排序跳表

在未排= ;序链表中查找元素是&#= 24456;慢的。如果用跳表ʌ= 88;http://en.wikipedia.or= g/wiki/Skip_list）代替= ;链表的话，可以加速&#= 36825;个操作。在跳表中ʌ= 92;如果有排序键（sort key）的话= ;，集合关系检查操作&#= 20250;很快：O(log F)。如果= ;你知道在何处插入的&#= 35805;，和链表一样，插Ð= 37;操作也是O(1)。如果= ;排序键是f，查找= ;最佳元素很快，达到O(1)，删除= ;一个元素也是O(1)。调整= ;操作涉及到查找结点&#= 65292;删除结点和重插入z= 90;

如果我= ;们用地图位置作为跳&#= 34920;的排序键，集合关Ŀ= 95;检查操作将是O(log F)。在完= ;成集合关系检查后，&#= 25554;入操作是O(1)。查找= ;最佳元素是O(F)，删除= ;一个结点是O(1)。因为= ;集合关系检查更快，&#= 25152;以它比未排序链表Š= 01;好一些。

如果我= ;们用f值作为= ;跳表的排序键，集合&#= 20851;系检查操作将是O(F)。插入= ;操作是O(1)。查找= ;最佳元素是O(1)，删除= ;一个结点是O(1)。这并= ;不比排序链表好。

3.3.5 索引数组

如果结= ;点的集合有限并且数&#= 30446;是适当的，我们可É= 97;使用直接索引结构，= 索引函数i(n)把结点= ;n映射到= ;一个数组的索引。未&#= 25490;序与排序数组的长ò= 30;等于OPEN集的最= ;大值，和它们不同，&#= 23545;所有的n，索引= ;数组的长度总是等于max(i(n))。如果= ;你的函数是密集的（&#= 27809;有不被使用的索引ʌ= 89;，max(i(n))将是你= ;地图中结点的数目。&#= 21482;要你的地图是网格į= 40;，让索引函数密集就= 是容易的。

假设= i(n)是O(1)的，集= ;合关系检查将花费O(1)，因为= ;我们几乎不需要检查Array[i(n)]是否= 包含任何数据。Insertion is O(1), as = we just ste Array[i(n)].查找和删除最Ë= 39;操作是O(numnodes)，因为= ;我们必须搜索整个结&#= 26500;。调整操作是O(1)。

3.3.6 哈希表

索引数= ;组使用了很多内存用&#= 20110;保存不在OPEN集中的= ;所有结点。一个选择&#= 26159;使用哈希表。哈希ŝ= 20;使用了一个哈希函数= h(n)把地图= ;上每个结点映射到一&#= 20010;哈希码。让哈希表į= 40;大小等于N的两倍= ;，以使发生冲突的可&#= 33021;性降低。假设h(n) &= #26159;O(1)的，集= ;体关系检查操作花费O(1)；插入= ;操作花费O(1)；删除= ;最佳元素操作花费O(numnodes)，因为= ;我们需要搜索整个结&#= 26500;。调整操作花费O(1)。

3.3.7 二元堆

一个二= ;元堆（不要和内存堆&#= 28151;淆）是一种保存在ă= 68;组中的树结构。和许= 多普通的树通过指针= 5351;向子结点所不同，ߚ= 8;元堆使用索引来੣= 7;找子结点。C++ STL包含了= ;一个二元堆的高效实&#= 29616;，我在我自己的A*代码中= ;使用了它。

在二元= ;堆中，集体关系检查&#= 33457;费O(F)，因为= ;你必须扫描整个结构&#= 12290;插入操作花费O(log F)而删= 除最佳操作花费也是O(log F)。<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>调整操= ;作很微妙（tricky），花= ;费O(F)时间找= ;到节点，并且很神奇&#= 65292;只用O(log F)来调整= ;。

我的一= ;个朋友（他研究用于&#= 26368;短路径算法的数据ń= 67;构）说，除非在你的= fringe集里有= ;多于10000个元素= ;，否则二元堆是很不&#= 38169;的。除非你的游戏ß= 20;图特别大，否则你不= 需要更复杂的数据结= 6500;（如multi-level buckets（http://www-cs-students.stanford.e= du/~csilvers/））。= ;你应该尽可能不用Fibonacci 堆（= http://www.star-lab.co= m/goldberg/pub/neci-tr-96-062.ps），因= ;为虽然它的渐近复杂&#= 24230;很好，但是执行起Ĉ= 69;很慢，除非F足够大= ;。

3.3.8 伸展树

堆是一= ;种基于树的结构，它&#= 26377;一个期望的O(log F)代价的= ;时间操作。然而，问&#= 39064;是在A*算法中= ;，通常的情况是，一&#= 20010;代价小的节点被移Ɓ= 00;（花费O(log F)的代价= ;，因为其他结点必须&#= 20174;树的底部向上移动ʌ= 89;，而紧接着一些代价= 小的节点被添加（花= 6153;O(log F)的代价= ;，因为这些结点被添&#= 21152;到底部并且被移动Ò= 40;最顶部）。在这里，= 堆的操作在预期的情= 0917;下和最坏情况下是ߌ= 8;样的。如果我们找到&= #36825;样一种数据结构，= 368;坏情况还是一样，而= ;预期的情况好一些，&#= 37027;么就可以得到改进z= 90;

伸展树= ;（Splay tree）是一= ;种自调整的树结构。&#= 20219;何对树结点的访问ų= 17;尝试把该结点推到树= 的顶部（top）。这= ;就产生了一个缓存效&#= 26524;（"caching" ef= fect）：很= ;少被使用的结点跑到&#= 24213;部（bottom）去了= ;并且不减慢操作（don't slow down operat= ions）。你= ;的splay树有多= ;大并不重要，因为你&#= 30340;操作仅仅和你的“cache size”一样= 慢。在A*中，低= ;代价的结点使用得很&#= 22810;，而高代价结点经ñ= 20;不被使用，所以高代= 价结点将会移动到树= 0340;底部。

使用伸= ;展树后，集体关系检&#= 26597;，插入，删除最佳Ø= 44;调整操作都是期望的= O(log F)（注：= ;原文为expected O(log F) ），最= ;坏情况是O(F)。然而= ;有代表性的是，缓存&#= 36807;程（caching）避免= ;了最坏情况的发生。Dijkstra算法和= ;带有低估的启发函数&#= 65288;underestimating heuris= tic）的= A*算法却= ;有一些特性让伸展树&#= 36798;不到最优。特别是ë= 45;结点n和邻居= ;结点n&= #8217;来说，= ;f(n') >=3D f(n)。<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>当这发= ;生时，也许插入操作&#= 24635;是发生在树的同一ů= 93;结果是使它失去了平= 衡。我没有试验过这= 0010;。

3.3.9 HOT队列

还有一= ;种比堆好的数据ಮ= 7;构。通常你可以限制&= #20248;先队列中值的范围 = 290;给定一个限定的范围= ;，经常会存在更好的&#= 31639;法。例如，对任意Í= 40;的排序可以在O(N log N)时间内= ;完成，但当固定范围&#= 26102;，桶排序和基数排ò= 07;可以在O(N)时间内= ;完成。

我们可= ;以使用HOT（Heap On Top）队列= ;(http://www.star-lab.c= om/goldberg/pub /neci-tr-97-104.ps）来利用f(n') >=3D f(n)，其中n’是n的一个邻&#= 23621;结点。我们删除f(n)值最= 小的结点n，插入满&#= 36275;f(n) <=3D f(n') <=3D f(n) + delta的邻居n'，其中delta <=3D C。<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>常数= C是从一结点到邻近ಮ= 7;点代价改变量的最大&= #20540;。因为f(n)是OPEN集中的= ;最小f值，并= ;且正要被插入的所有&#= 32467;点都小于或等于f(n) + delta，我= 们知道OPEN集中= 的所有f值都不超&#= 36807;一个0..delta的范= 围。在桶/基数排序&#= 20013;，我们可以用“桶”= ;（buckets）对OPEN集中的结点进行= 排序。

使用= K个<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>桶，我= ;们把O(N)的代价= ;降低到平均O(N/K)。通过= ;HOT队列，= ;顶端的桶使用二元堆೎= 0;所有其他的桶都是未&= #25490;序数组。因而，对'= 030;部的桶，集合关系检= ;查代价是预期的O(F/K)，插入= ;和删除最佳是O(log (F/K))。对其= ;他桶，集合关系检查&#= 26159;O(F/K)，插入= ;是O(1)，而删= ;除最佳根本不发生！&#= 22914;果顶端的桶是空的ʌ= 92;那么我们必须把下一个桶即未排ॴ= 7;数组转换为二元堆。&= #36825;个操作（“heapify”）可= 以在O(F/K)时间内= ;完成。在调整操作中&#= 65292;删除是O(F/K)，然后= ;插入是O(log (F/K))或O(1)。

在A*中，我= ;们加入OPEN集中的= ;许多结点实际上根本&#= 26159;不需要的。在这方ƃ= 54;HOT队列很= ;有优势，因为不需要&#= 30340;元素的插入操作只Ŏ= 57;费O(1)时间。= ;只有需要的元素被heapified（代价= ;较低的那些）。唯一一个超过O(1)的操作是从&= #22534;中删除结点，只花$= 153;O(log (F/K))。

另外，= ;如果C比较小= ;，我们可以只让K =3D C，则对= ;于最小的桶，我们甚&#= 33267;不需要一个堆，国È= 26;在一个桶中的所有结= 点都有相同的f值。插= ;入和删除最佳都是O(1)时间！有人&= #30740;究过，HOT队列在= ;至多在OPEN集中有= ;800个结点= ;时和堆一样快，并ߎ= 8;如果OPEN集中至= ;多有1500个结点= ;，则比堆快20%。我期望随&= #30528;结点的增加，HOT队列也= ;更快。

HOT队列的= ;一个简单的变化是一&#= 20010;二层队列（two-level queue= ）：把= ;好的结点放进一个数&#= 25454;结构（堆或数组）Ň= 80;把坏的结点放进另一= 个数据结构（数组或= 8142;表）。因为大多数๢= 7;入OPEN集中的= ;结点都“坏的”，它= 204;从不被检查，因而把= ;它们放进出一个大数&#= 32452;是没有害处的。

3.3.10 比较

注意有= ;一点很重要，我们并&#= 19981;是仅仅关心渐近的Ŝ= 92;为（大O符号）= ;。我们也需要关心小&#= 24120;数（low constant）下的= ;行为。为了说明原因&#= 65292;考虑一个O(log F)的算法= ;，和另一个O(F)的算法= ;，其中F是堆中= ;元素的个数。也许在&#= 20320;的机器上，第一个ļ= 39;法的实现花费10000*log(F)秒，而= ;另一个的实现花费2*F秒。当= ;F=3D256时，第= ;一个算法将花费80000秒而第= ;二个算法花费512秒。在= ;这种情况下，“更快= 221;的算法花费更多的时= ;间，而且只有在当F>200000时才能= ;运行得更快。

你不能= ;仅仅比较两个算法。&#= 20320;还要比较算法的实Ĩ= 16;。同时你还需要知道= 你的数据的大小（size）。在= ;上面的例子中，第一&#= 31181;实现在F>200000时更快= ;，但如果在你的游戏&#= 20013;，F小于= 30000，那么= ;第二种实现好一些。

基本数= ;据结构没有一种是完&#= 20840;合适的。未排序数ń= 52;或者链表使插入操作= 很快而集体关系检查= 1644;删除操作非常慢。৵= 0;序数组或者链表使集&= #20307;关系检查稍微快一= 123;，删除（最佳元素）= ;操作非常快而插入操&#= 20316;非常慢。二元堆让插入ࡴ= 4;删除操作稍微快一些&= #65292;而集体关系检查则= 456;慢。伸展树让所有操= ;作都快一些。HOT队列让= ;插入操作很快，删除&#= 25805;作相当快，而集体Ð= 51;系检查操作稍微快一= 些。索引数组让集体= 0851;系检查和插入操作༣= 0;常快，但是删除操作&= #19981;可置信地慢，同时$= 824;需要花费很多内存空= ;间。哈希表和索引数&#= 32452;类似，但在普通情Ñ= 17;下，它花费的内存空= 间少得多，而删除操= 0316;虽然还是很慢，但ૈ= 4;索引数组要快。

关于更= ;高级的优先队列的资&#= 26009;和实现，请参考Lee Killough的优先= ;队列页面（http://members.xoom.co= m/killough/heaps.html）。=

3.3.11 混合实现

为了得= ;到最佳性能，你将希&#= 26395;使用混合数据结构z= 90;在我的A*代码中= ;，我使用一个索引数&#= 32452;从而集合关系检查ą= 59;O(1)的，一= ;个二元堆从而插入操&#= 20316;和删除最佳都是O(log F)的。对于调&= #25972;操作，我使用索引= 968;组从而花费O(1)时间检= ;查我是否真的需要进&#= 34892;调整（通过在索引ă= 68;组中保存g值），= ;然后在少数确实需要&#= 36827;行调整的情况中，û= 05;使用二元堆从而调整= 操作花费O(F)时间。= ;你也可以使用索引数&#= 32452;保存堆中每个结点į= 40;位置，这让你的调整= 操作变成O(log F)。

3.4 与游= 戏循环的交互

交互式= ;的（尤其是实时的）&#= 28216;戏对最佳路径的计ļ= 39;要求很高。能够得到= 一个解决方案比得到= 6368;佳方案可能更重要Ӎ= 0;然而在所有其他因素&= #37117;相同的情况下，短$= 335;径比长路径好。

一般来= ;说，计算靠近初始结&#= 28857;的路径比靠近目标ń= 67;点的路径更重要一些= 。立即开始原理（The principle of immediate start）：让游戏&= #20013;的物体尽可能快地= 320;始行动，哪怕是沿着= ;一条不理想的路径，&#= 28982;后再计算一条更好į= 40;路径。在实时游戏中= ，应该更多地关注A*的延迟= ;情况（latency）而不是吞吐ŵ= 27;（throughput）。

可以对= ;物体编程让它们根据&#= 33258;己的本能（简单行È= 26;）或者智力（一条预= 先计算好的路径）来= 4892;动。除非它们的智ࡂ= 7;告诉它们怎么行动，&= #21542;则它们就根据自己= 340;本能来行动（这是实= ;际上使用的方法，并&#= 19988;Rodney Brook在他的= ;机器人体系结构中也&#= 29992;到）。和立即计算û= 52;有路径所不同，让游= 戏在每一个，两个，= 5110;者三个循环中搜索ߌ= 8;条路径。让物体在开&= #22987;时依照本能行动(可能仅= ;仅是简单地朝着目标&#= 30452;线前进)，然后= ;才为它们寻找路径。&#= 36825;种方法让让路径搜ŀ= 34;的代价趋于平缓，因= 此它不会集中发生在= 1516;一时刻。

3.4.1 提前退出

可以从= ;A*算法的= ;主循环中提前退出来&#= 21516;时得到一条局部路ô= 52;。通常，当找到目标= 结点时，主循环就退= 0986;了。然而，在此之࠺= 9;的任意结点，可以得&= #21040;一条到达OPEN中当前= ;最佳结点的路径。这&#= 20010;结点是到达目标点į= 40;最佳选择，所以它是= 一个理想的中间结点= 5288;原文为so it's a reasonable p= lace to go&= #65289;。

可以提= ;前退出的情况包括检&#= 26597;了一定数量的结点ʌ= 92;A*算法已= ;经运行了几毫秒时间&#= 65292;或者扫描了一个离Ò= 21;始点有些距离的ಮ= 7;点。当使用路径拼接&= #26102;，应该给被拼接的$= 335;径一个比全路径（= full path）小的= ;最大长度。

3.4.2 中断算法

如果需= ;要进行路径搜索的物&#= 20307;较少，或者如果用É= 10;保存OPEN和CLOSED集的数= ;据结构较小，那么保&#= 23384;算法的状态是可行į= 40;，然后退出到游戏循= 环继续运行游戏。

3.4.3 组运动

路径请= ;求并不是均匀分布的&#= 12290;即时策略游戏中有Ç= 68;个常见的情况，玩家= 会选择多个物体并命= 0196;它们朝着同样的目੧= 1;移动。这给路径搜索&= #31995;统以沉重的负载。

在这种= ;情况下，为某个物体&#= 23547;找到的路径对其它Ĥ= 89;体也是同样有用的。= 一种方法是，寻找一= 6465;从物体的中心到目௚= 0;地中心的路径P。对所= ;有物体使用该路径的&#= 32477;大部分，对每一个Ĥ= 89;体，前十步和后十步= 使用为它自己寻找的= 6335;径。物体i得到一= ;条从它的开始点到P[10]的路径= ;，紧接着是共享的路&#= 24452;P[10..len(P)-10]，最后是从P[len(P)-10]到目= 的地的路径。

为每个= ;物体寻找的路径是较&#= 30701;的（平均步数大约ą= 59;10），而= ;较长的路径被共享。&#= 22823;多数路径只寻找一Ē= 25;并且为所有物体所共= 享。然而，当玩家们= 0475;到所有的物体都沿௬= 8;相同的路径移动时，&= #23558;对游戏失去兴趣。= 026;了对系统做些改进，= ;可以让物体稍微沿着&#= 19981;同的路径运动。一ķ= 81;方法是选择邻近结点= 以改变路径。

另一种= ;方法是让每个物体都&#= 24847;识到其它物体的存ß= 12;（或许是通过随机选= 择一个“领导”物体ʌ= 92;或者是通过选择一个= 能够最好地意识到当= 1069;情况的物体），同ਲ= 2;仅仅为领导寻路。然&= #21518;用flocking算法让= ;它们以组的形式运动&#= 12290;

然而还= ;有一种方法是利用A*算法的= ;中间状态。这个状态&#= 21487;以被朝着相同目标ĸ= 27;动的多个物体共享，= 只要物体共享相同的= 1551;发式函数和代价函ਤ= 8;。当主循环退出时，&= #19981;要消除OPEN和CLOSED集；用= ;A*上一次= ;的OPEN和CLOSED集开始= ;下一次的循环（下一&#= 20010;物体的开始位置）z= 90;（这可以被看成是中= 断算法和提前退出部= 0998;的一般化）

3.4.4 细化

如果地= ;图中没有障碍物，而&#= 26377;不同代价的地形，Ų= 27;么可以通过低估地形= 的代价来计算一条初= 2987;路径。例如，如果ഠ= 9;地的代价是1，山地= ;代价是2，山脉= ;的代价是3，那么= ;A*会考虑= ;通过3个草地= ;以避免1个山脉= ;。通过把草地看成1，山地= ;看成1.1，而山= ;脉看成1.2来计算= ;初始路径，A*将会用= ;更少的时间去设法避&#= 20813;山脉，而且可以更õ= 55;地找到一条路径（这= 接近于精确启发函数= 0340;效果）。一旦找到ߌ= 8;条路径，物体就可以&= #24320;始移动，游戏循环= 601;可以继续了。当多余= ;的CPU时间是= ;可用的时候，可以用&#= 30495;实的移动代价去计ļ= 39;更好的路径。

4 A*算法的变种

4.1 beam search

在A*的主循= ;环中，OPEN集保存= ;所有需要检查的结点&#= 12290;Beam Search是A*算法的= ;一个变种，这种算法&#= 38480;定了OPEN集的尺= ;寸。如果OPEN集变得= ;过大，= ;那些没有机会通向一&#= 26465;好的路径的结点将ŝ= 87;抛弃。缺点是你必须= 让排序你的集合以实= 9616;这个，这限制了可ߵ= 9;选择的数据结构。

4.2 迭代= 深化

迭代深= ;化是一种在许多AI算法中= ;使用的方法，这种方&#= 27861;从一个近似解开始ʌ= 92;逐渐得到更精确的解= 。该名称来源于游戏= 6641;搜索，需要查看前༣= 4;几步（比如在象棋里&= #65289;，通过查看前面更= 810;步来提高树的深度。= ;一旦你的解不再有更多௚= 0;改变或者改善，就可&= #20197;认为你已经得到足= 815;好的解，当你想要进= ;一步精确化时，它不&#= 20250;再有改善。在ID-A*中，深= ;度是f值的一= ;个cutoff。当= f的值太= ;大时，结点甚至将不&#= 34987;考虑（例如，它不Ê= 50;被加入OPEN集中）= ;。第一次迭代只处理很ऴ= 9;的结点。此后每一次&= #36845;代，访问的结点都= 558;增加。如果你发现路= ;径有所改善，那么就&#= 32487;续增加cutoff，否则= ;就可以停止了。更多&#= 30340;细节请参考这些关É= 10;ID-A*的资料= ;：http://www.apl.jhu.edu= /~hall/AI-Programming/IDA-Star.html。

我本人= ;认为在游戏地图中没&#= 26377;太大的必要使用ID-A*寻路。= ;ID算法趋= ;向于增加计算时间而&#= 20943;少内存需求。然而ß= 12;地图路径搜索中，“&= #32467;点”是很小的——它= ;们仅仅是坐标而已。&#= 25105;认为不保存这些结Ġ= 57;以节省空间并不会带= 来多大改进。

4.3 动态= 衡量

在动态= ;衡量中，你假设在开&#= 22987;搜索时，最重要的是讯速移动到ߥ= 9;意位置；而在搜索接&= #36817;结束时，最重要的= 159;移动到目标点。

f(= p) =3D g(p) + w(p) * h= (p)

启发函= ;数中带有一个权值（weight）（= w>=3D1）。当= ;你接近目标时，你降&#= 20302;这个权值；这降低了启发࠲= 9;数的重要性，同时增&= #21152;了路径真实代价的= 456;对重要性。

4.4 带宽= 搜索

带宽搜= ;索（Bandwidth Search）有两个对&= #26377;些人也许有用的特= 615;。这个变种假设h是过高= ;估计的值，但不高于&#= 26576;个数e。如果= ;这就是你遇到的情况&#= 65292;那么你得到的路径į= 40;代价将不会比最佳路= 径的代价超过e。重申= ;一次，你的启发函数&#= 35774;计的越好，最终效ĉ= 24;就越好。

另一个= ;特性是，你可以丢弃OPEN集中的= ;某些结点。当h+d比路径= ;的真实代价高的时候&#= 65288;对于某些d），你= ;可以丢弃那些f值比= OPEN集中的= ;最好结点的f值高至少e+d的结点= ;。这是一个奇怪的特&#= 24615;。对于好的f值你有= ;一个“范围”（"band"），任= ;何在这个范围之外的&#= 32467;点都可以被丢弃掉ʌ= 92;因为这个结点肯定不= 会在最佳路径上。

好奇地= ;（Curiously），你= ;可以对这两种特性使&#= 29992;不同的启发函数，Ň= 80;问题仍然可以得到解= 决。使用一个启发函= 5968;以保证你得到的路঍= 2;不会太差，另一个用&= #20110;检查从OPEN集中去= ;掉哪些结点。

4.5 双向= 搜索

与从开= ;始点向目标点搜索不&#= 21516;的是，你也可以并Ŝ= 92;地进行两个搜索——&#= 19968;个从开始点向目标Ġ= 57;，另一个从目标点向开始点。当द= 7;们相遇时，你将得到&= #19968;条好的路径。

这听起= ;来是个好主意，但我&#= 19981;会给你讲很多内容z= 90;双向搜索的思想是，= 搜索过程生成了一棵= 2312;地图上散开的树。ߌ= 8;棵大树比两棵小树差&= #24471;多，所以最好是使= 992;两棵较小的搜索树。= ;然而我的试验表明，&#= 22312;A*中你得= ;不到一棵树，而只是&#= 22312;搜索地图中当前位ņ= 22;附近的区域，但是又= 不像Dijkstra算法那= ;样散开。事实上，这&#= 23601;是让A*算法运= ;行得如此快的原因—= 212;无论你的路径有多长= ;，它并不进行疯狂的&#= 25628;索，除非路径是疯ĥ= 78;的。它只尝试搜索地= 图上小范围的区域。= 2914;果你的地图很复杂ᦁ= 2;双向搜索会更有用。<= /span>

面对面= ;的方法（The front-to-front variation）把这两种&= #25628;索结合在一起。这= 181;算法选择一对具有最= ;好的g(start,x) + h(x,y) + g(y,goal)的结点，而不是选ý= 21;最好的前向搜索结点= ——g(start,x) + h(x,goal)，或者最好的后向Ā= 28;索结点——g(y,goal) + h(start,y)。

Retargeting方法不= ;允许前向和后向搜索&#= 21516;时发生。它朝着某È= 10;最佳的中间结点运行= 前向搜索一段时间，= 8982;后再朝这个结点运ඡ= 2;后向搜索。然后选择&= #19968;个后向最佳中间结= 857;，从前向最佳中间结= ;点向后向最佳中间结&#= 28857;搜索。一直进行这È= 10;过程，直到两个中间= 结点碰到一块。

4.6 动态= A*与终身计划A*

有一些= ;A*的变种= ;允许当初始路径计算&#= 20986;来之后，世界发生ă= 13;变。D*用于当= ;你没有全局所有信息&#= 30340;时候。如果你没有û= 52;有的信息，A*可能会= ;出错；D*的贡献= ;在于，它能纠正那些&#= 38169;误而不用过多的时ſ= 88;。LPA*用于代= ;价会改变的情况。在A*中，当地图发生改ࡢ= 4;时，路径将变得无效&= #65307;LPA*可以重= ;新使用之前A*的计算= ;结果并产生新的路径&#= 12290;然而，D*和LPA*都需要= ;很多内存——用于运"= 892;A*并保存= ;它的内部信息（OPEN和CLOSED集，路= ;径树，g值），= ;当地图发生改ࡢ= 4;时，D*或者= LPA*会告诉= ;你，是否需要就地图&#= 30340;改变对路径作调整z= 90;在一个有许多运动着= 的物体的游戏中，你= 2463;常不希望保存所有๢= 5;些信息，所以D*和LPA*在这里= ;并不适用。它们是为&#= 26426;器人技术而设计的ʌ= 92;这种情况下只有一个= 机器人——你不需要È= 26;别的机器人寻路而重= 用内存。如果你的游= 5103;只有一个或者少数࠰= 0;个物体，你可以研究&= #19968;下D*或者= LPA*。

5 处理运动障碍物

一个路= ;径搜索算法沿着固定&#= 38556;碍物计算路径，但ą= 59;当障碍物会运动时情= 况又怎样？当一个物= 0307;到达一个特写的位ಾ= 2;，原来的障碍物也许&= #19981;再在那儿了，或者= 968;个新的障碍物也许到= ;达那儿。处理该问题&#= 30340;一个方法是放弃路ô= 52;搜索而使用运动算法= （movement algorithms）替代= ;，这就不能look far ahead<= span style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman";color:black;mso-ansi-language:EN'>；这种= ;方法会在后面的部分&#= 20013;讨论。这一部分将ë= 45;路径搜索方法进行修= 改从而解决运动障碍= 9289;的问题。

5.1 重新= 计算路径

当时间= ;渐渐过去，我们希望&#= 28216;戏世界有所改变。É= 97;前搜索到的一条路径= 到现在也许不再是最= 0339;的了。对旧的路径ஷ= 2;新的信息进行更新是&= #26377;价值的。以下规则= 487;以用于决定什么时候= ;需要重新计算路径：

  • 每N步= ：这保证用于计算路= 4452;的信息不会旧于N步。
  • 任何可以使用额外&#= 30340;CPU时间的时候：= 这允许动态调整路径= 0340;性质；在物体数量ࣩ= 0;时，或者运行游戏的&= #26426;器比较慢时，每个= 289;体对CPU的使用可得到= 减少。
  • 当物体拐弯或者跨&#= 36234;一个导航点（waypoint）= 的时候。
  • 当物体附近的世界&#= 25913;变了的时候。

重计算= ;路径的主要缺点是许&#= 22810;路径信息被丢弃了z= 90;例如，如果路径是<= span lang=3DEN style=3D'color:black;mso-ansi-language:EN'>100步长，= ;每10步重新= ;计算一次，路径的总&#= 27493;数将是100+90+80+70+60+50+40+= 30+20+10 =3D 550&= #12290;对M步长的= ;路径，大约需要计算M^2步。因= ;此如果你希望有许多&#= 24456;长的路径，重计算Ç= 81;是个好主意。重新使= 用路径信息比丢弃它= 6356;好。

5.2 路径= 拼接

当一条= ;路径需要被重新计算&#= 26102;，意味着世界正在ă= 13;变。对于一个正在改= 变的世界，对地图中= 4403;前邻近的区域总是ૈ= 4;对远处的区域了解得&= #26356;多。因此，我们应#= 813;集中于在附近寻找好= ;的路径，同时假设远&#= 22788;的路径不需要重新ť= 45;算，除非我们接近它= 。与重新计算整个路= 4452;不同，我们可以重ਫ= 2;计算路径的前M步：=

  1. 令p[1]= ..p[N]为= 路径（N步）的剩余部= 分
  2. 为p[1]= 到= p[M]计算一条新的= 路径
  3. 把这条新路径拼接&#= 65288;Splice）到旧路径：= 把p[1]..p[M]用= 新的路径值代替

因为= p[1]和p[M]比分开= ;的M步小（= ;原文：Since p[1] and p[M] ar= e fewer than M steps apart&= #65289;，看起来新路径不= 250;很长。不幸的是，新= ;的路径也许很长而且&#= 19981;够好。上面的图显Ķ= 34;了这种情况。最初的= 红色路径是1-2-3-4，褐色= ;的是障碍物。如果我&#= 20204;到达2并且发= ;现从2到达= 3的路径= ;被封锁了，路径拼接&#= 25216;术会把2-3用2-5-3取代，= ;结果是物体沿着路径1-2-5-3-4运动。= ;我们可以看到这不是&#= 19968;条好的路径，蓝色į= 40;路径1-2-5-4是一条= ;更好的路径。

通常可= ;以通过查看新路径的&#= 38271;度检测到坏的路径z= 90;如果这严格大于M，就可= ;能是不好的。一个简&#= 21333;的解决方法是，为Ā= 28;索算法设置一个最大= 路径长度。如果找不= 1040;一条短的路径，算ૢ= 1;返回错误代码；这种&= #24773;况下，用重计算路= 452;取代路径拼接，从而= ;得到路径1-2-5-4.。

对于其= ;它情况，对于N步的路= ;径，路径拼接会计算2N或者= 3N步，这= ;取决于拼接新路径的&#= 39057;率。对于对世界的ă= 13;变作反应的能力而言= ，这个代价是相当低= 0340;。令人吃惊的是这ߑ= 0;代价和拼接的步数M无关。= ;M不影响= ;CPU时间，= ;而控制了响应和路径&#= 36136;量的折衷。如果M太大，= ;物体的移动将不能快&#= 36895;对地图的改变作出反应。如ੜ= 4;M太小，= ;拼接的路径可能太短&#= 20197;致不能正确地绕过Ɓ= 56;碍物；许多不理想的= 路径（如1-2-5-3-4）将被= ;找到。尝试不同的M值和不= ;同的拼接标准(如每= 3/4 M步)，看看哪一种÷= 73;况对你的地图最合适= 。

路径拼= ;接确实比重计算路径&#= 35201;快，但它不能对路ô= 52;的改变作出很好的反ॵ= 2;。经常可以发现这种&= #24773;况并用路径重计算= 469;取代。也可以调整一= ;些变量，如M和寻找= ;新路径的时机，所以&#= 21487;以对该方法进行调ă= 72;(甚至在= ;运行时)以用于= ;不同的情况。

Note：Bryan Stout 有两个= ;算法，Patch-One和Patch-All，他从= ;路径拼接中得到灵感&#= 65292;并在实践中运行得ô= 56;好。他出席了GDC 2007（https://www.cmpevents.= com/GD07/a.asp?option =3DC &V=3D11& SessID=3D4608）；一旦他把ũ= 64;料放在网上，我将链= 接过去。

Implementation Note：

反向保= ;存路径，从而删除路&#= 24452;的开始部分并用不×= 16;长度的新路径拼接将= 更容易，因为这两个= 5805;作都将在数组的末ह= 4;进行。本质上你可以&= #25226;这个数组看成是堆= 632;因为顶部的元素总是= ;下一个要使用的。

5.3 监视= 地图变化

与间隔= ;一段时间重计算全部&#= 25110;部分路径不同的是ʌ= 92;可以让地图的改变触= 发一次重计算。地图= 1487;以分成区域，每个୰= 9;体都可以对某些区域&= #24863;兴趣（可以是包含%= 096;分路径的所有区域，= ;也可以只是包含部分&#= 36335;径的邻近区域）。ô= 03;一个障碍物进入或者= 离开一个区域，该区= 2495;将被标识为已改变ᦁ= 2;所有对该区域感兴趣&= #30340;物体都被通知到，= 152;以路径将被重新计算= ;以适应障碍物的改变&#= 12290;

这种技= ;术有许多变种。例如&#= 65292;可以每隔一定时间Ű= 90;知物体，而不是立即= 通知物体。多个改变= 1487;以成组地触发一个๩= 0;知，因此避免了额外&= #30340;重计算。另一个例= 376;是，让物体检查区域= ;，而不是让区域通知&#= 29289;体。

监视地= ;图变化允许当障碍物&#= 19981;改变时物体避免重ť= 45;算路径，所以当你有= 许多区域并不经常改= 1464;时，考虑这种方法Ӎ= 0;

5.4 预测= 障碍物的运动

如果障= ;碍物的运动可以预测&#= 65292;就能为路径搜索考ŗ= 85;障碍物的未来位置。= 一个诸如A*的算法= ;有一个代价函数用以&#= 26816;查穿过地图上一点į= 40;代价有多难。A*可以被= ;改进从而知道到达一&#= 28857;的时间需求（通过ô= 03;前路径长度来检查）= ，而现在则轮到代价= 0989;数了。代价函数可ߣ= 7;考虑时间，并用预测&= #30340;障碍物位置检查在= 576;个时刻地图某个位置= ;是否可以通过。这个&#= 25913;进不是完美的，然Ň= 80;，因为它并不考虑在= 某个点等待障碍物自= 1160;离开的可能性，同ਲ= 2;A*并不区= ;分到达相同目的地的&#= 19981;同的路径，而是针ë= 45;不同的目的地，所以= 还是可以接受的。

6 预计算路径的空间É= 95;价

有时，= ;路径计算的限制因素&#= 19981;是时间，而是用于ă= 68;以百计的物体的存储= 空间。路径搜索器需= 5201;空间以运行算法和߼= 5;存路径。算法运行所&= #38656;的临时空间（在A*中是= OPEN和CLOSED集）通= ;常比保存结果路径的&#= 31354;间大许多。通过限Ò= 46;在一定的时间计算一= 条路径，可以把临时= 1354;间数量最小化。另ࣨ= 6;，为OPEN和CLOSED&= #38598;所选择的数据= ;结构的不同，最小化临时空间的ఴ= 3;度也有很大的不同。&= #36825;一部分聚集于优化= 992;于计算路径的空间代= ;价。

6.1 位置= VS方向

一条路= ;径可以用位置或者方ࡨ= 1;来表示。位置需要更&= #22810;的空间，但是有一= 010;优点，易于查询路径= ;中的任意位置或者方&#= 21521;而不用沿着路径移Ó= 60;。当保存方向时，只= 有方向容易被查询；= 1482;有沿着整个路径移ࡄ= 0;才能查询位置。在一个典形的网੬= 4;地图中，位置可以被&= #20445;存为两个16位整数= ;，每走一步是32位。而= ;方向是很少的，因此&#= 29992;极少的空间就够了z= 90;如果物体只能沿着四= 个方向移动，每一步= 9992;两位就够了；如果୰= 9;体能沿着6个或者= ;8个方向= ;移动，每一步也只需&#= 35201;三位。这些对于保é= 84;路径中的位置都有明= 显的空间节省。Hannu Kankaanpaa指出可= ;以进一步减少空间需&#= 27714;，那就是保存相对Ą= 41;向（右旋60度）而= ;不是绝对方向（朝北&#= 36208;）。有些相对方向ë= 45;某些物体来说意义不= 大。比如，如果你的= 9289;体朝北移动，那么ߍ= 9;一步朝南移动的可能&= #24615;很小。在只有六种= 041;向的游戏中，你只有= ;五个有意义的方向。&#= 22312;某些地图中，也许Ö= 82;有三个方向（直走，= 左旋60度，右= ;旋60度）有= ;意义，而其它地图中&#= 65292;右旋120度是有= ;效的（比如，沿着陡&#= 23789;的山坡走之字形的ū= 35;径时）。

6.2 路径= 压缩

一旦找= ;到一条路径，可以对&#= 23427;进行压缩。可以用Ç= 68;个普通的压缩算法，= 但这里不进行讨论。= 0351;用特定的压缩算法ࡤ= 7;以缩小路径的存储，&= #26080;论它是基于位置的$= 824;是基于方向的。在做= ;决定之前，考察你的&#= 28216;戏中的路径以确定Ù= 38;种压缩效果最好。另= 外还要考虑实现和调= 5797;，代码量，and whether it really = matters.如果你= ;有300个物体= ;并且在同一时刻只有50个在移= ;动，同时路径比较短&#= 65288;100步），= ;内存总需求大概只有&#= 19981;到50k，总之= ;，没有必要担心压缩&#= 30340;效果。

6.2.1 位置存储

在障碍= ;物比地形对路径搜索&#= 24433;响更大的地图中，ū= 35;径中有大部分是直线= 的。如果是这种情况= 5292;那么路径只需要包ࡪ= 7;直线部分的终止点（&= #26377;时叫waypoints）。此= ;时移动过程将包含检&#= 26597;下一结点和沿着直ń= 47;向前移动。

6.2.2 方向存储

保存方= ;向时，有一种情况是&#= 21516;一个方向保存了很ä= 10;次。可以用简单的方= 法节省空间。

一种方= ;法是保存方向以及朝着该方向移ࡄ= 0;的次数。和位置存储&= #30340;优化不同，当一个= 041;向并不是移动很多次= ;时，这种优化的效果&#= 21453;而不好。同样的，ë= 45;于那些可以进行位置= 压缩的直线来说，方= 1521;压缩是行不通的，ࢰ= 0;为这条直线可能没有&= #21644;正在移动的方向关 = 852;。通过相对方向，你= ;可以把“继续前进”= 403;作可能的方向排除掉= ;。Hannu Kankaanpaa指出，= ;在一个八方向地图中&#= 65292;你可以去掉前，后ʌ= 92;以及向左和向右135度（假= ;设你的地图允许这个&#= 65289;，然后你可以仅用È= 04;个比特保存每个方向= 。

另一种= ;保存路径的方法是变&#= 38271;编码。这种想法是Ë= 51;用一个简单的比特（= 0）保存= ;最一般的步骤：向前&#= 36208;。使用一个“1”表示= 拐弯，后边再跟几个= 7604;特表示拐弯的方向Ӎ= 0;在一个四方向地图中ᦁ= 2;你只能左转和右转，&= #22240;此可以用“10”表示= 左转，“11”表示= 右转。

变长编= ;码比run length encoding更一般= ;，并且可以压缩得更&#= 22909;，但对于较长的直ń= 47;路径则不然。序列（= 向北直走6步，左= ;转，直走3步，右= ;转，直走5步，左= ;转，直走2步）用= ;run length encoding表示是= ;[(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)]。如果每个方×= 21;用2比特，= ;每个距离用8比特，= ;保存这条路径需要40比特。= ;而对于变长编码，你&#= 29992;1比特表= ;示每一步，2比特表= ;示拐弯——[NORTH 0 0 0 0 0 0 10 = 0 0 0 11 0 0 0 0 0 10 0 0]——一共24比特。如果&= #21021;始方向和每次拐弯= 545;应1步，则= ;每次拐弯都节省了一&#= 20010;比特，结果只需要20比特保= ;ढ