返回

云风，你好，看了你的A*算法的文章。我有几点看法：
1、队列用二叉树可能比用链表更快吧，当节点很多很多的时候，要把一个新节点加入队列，用链表查找插入的位置会很慢。
2、对于基于格子的游戏来说，可以预先生成路径，这样寻路的时候可以极大的提高效率。我的想法是，把每个交界处的凸顶点作为一个节点，寻路的时候再加入两个节点（开始移动节点、目标节点）。例如你提供的地图，我们可以预先生成的节点如下图：
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
o                                                                             o
o                           n              n                                  o
o   s                        oooooooooooooo                                   o
o          n                              o                                   o
ooooooooooo     n       n   n             o      n        n                   o
o   n     o      ooooooo   n oooooooooooooo       oooooooo                    o
o    oooooo      o     oooo n              n      o  nn  o                    o
o   n      n     o   nn   o                       ooo  ooo                    o
o                oooo  oooo     n                n   nn   n                   o
o               n    nn    n     oooooooooooooooooooooooooooooooooooooooooooooo
o                               n                                             o
o                                                                             o
o                                           n                                 o
oooooooooooooooooooooooooooooooooooooooooooo                       n          o
o       o  n       n                        n           n        n  ooooooooooo
o       o   ooooooo                                      oooooooo  n          o
o       o  n      o       n          n                   o      o             o
o       ooooooooooo        oooooooooo  n                 o      o             o
o      n           n       oe   n   ooo                  o      o             o
o                          ooooo      o                  o      o             o
o                         n   n n     o                  o     n n            o
o                              o      o                  o                    o
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

名字: 自动排版 密码:

• 那个程序只是为了说明大概算法，具体的优化方法可以很多 :) - 回复 | (857) | 云风 | 2005-12-10 03:25:58

  • 此贴被删除

• 彙報vvghgvvvvbjhb uhuyhuhhuhhhbyv呼喚uyhgggyuuhuhhuyggggytg哈巴狗廣告部愉悅感uygggbbgggb硬骨魚咕咕咕ubbbvgvgvghbbgv黑更半夜vggggbb殯儀館vgvbhbhb - 回复 | (854) | 舒坤鵬 | 2005-12-09 10:30:20

• 我最近写了个A*，发现map(二叉树)没有链表好，要知道每次取出节点扩展都会造成map结构改变. 目前采用的是优先级队列（用了堆），速度是最快的。

  我在读入地图时就把所有节点都构造出来了（虽然有点占空间），寻路时就只传地址，感觉比寻路时才构建节点快得多。 - 回复 | (723) | sf.tk | 2005-07-25 11:57:48

  • vgf - 回复 | (737) | xcc | 2005-08-02 06:26:22

• ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
  o                                                                             o
  o                           n              n                                  o
  	『More Lines』

  - 回复 | (639) | Atry | 2005-03-27 09:21:49