设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索
查看: 2412|回复: 2

[讨论] A*寻路算法需要用到的优先队列

[复制链接]

Lv3.寻梦者

梦石
0
星屑
1774
在线时间
950 小时
注册时间
2012-7-5
帖子
245
发表于 2016-11-16 19:51:49 | 显示全部楼层 |阅读模式

加入我们,或者,欢迎回来。

您需要 登录 才可以下载或查看,没有帐号?注册会员

x
本帖最后由 浮云半仙 于 2016-11-16 20:04 编辑

RT。A*寻路算法中有一步是取出期望代价最小点。用数组的min方法是很缓慢地,会遍历整个数组才返回最小值。可以使用优先队列来优化这个过程。
下面给出一份用ruby实现的大顶堆(我这个是大顶堆,写A*需要的是小顶堆,把两个数的比较符号反过来就好了...),用法很简单啦,看看下面的那个说明就吼了。
欢迎更神奇的斐波那契堆,配对堆出场(他们两个跑A*貌似会更快哦

RUBY 代码复制下载
  1. class PriorityQueue
  2.     def initialize()
  3.         @heap_size = 0
  4.         @heap_tail = 0
  5.         @heap_data = [0]
  6.     end
  7.     def empty
  8.         @heap_tail == 0
  9.     end
  10.     def size
  11.         @heap_size
  12.     end
  13.  
  14.     def push(value)
  15.         @heap_tail += 1
  16.         @heap_data[@heap_tail] = value
  17.         f = @heap_tail
  18.                 #把新插入的节点往上提
  19.         while f != 1 && value > @heap_data[f>>1]  #可以向上去
  20.             @heap_data[f] = @heap_data[f>>1]
  21.             @heap_data[f>>1] = value
  22.             f >>= 1
  23.         end
  24.     end
  25.     def top
  26.         @heap_data[1]  #最大元素在顶端
  27.     end
  28.     def pop
  29.         @heap_data[1] = @heap_data[@heap_tail]
  30.         f = 1
  31.         tmp = @heap_data[@heap_tail]
  32.         @heap_tail -= 1
  33.         while (f << 1) <= @heap_tail
  34.             d = @heap_data[f<<1] - @heap_data[f<<1|1]
  35.  
  36.             #左右节点都比自己小,终止循环
  37.             if d > 0  
  38.                 break if @heap_data[f<<1] <= tmp
  39.             else
  40.                 break if @heap_data[f<<1|1] <= tmp
  41.             end
  42.  
  43.             if d > 0  #左孩子大就与左孩子交换,否则和右孩子交换
  44.                 @heap_data[f] = @heap_data[f<<1]
  45.                 @heap_data[f<<1] = tmp
  46.                 f <<= 1
  47.             else
  48.                 @heap_data[f] = @heap_data[f<<1|1]
  49.                 @heap_data[f<<1|1] = tmp
  50.                 f = f<<1|1
  51.             end
  52.         end
  53.     end
  54. end
  55.  
  56. #test
  57. q = PriorityQueue.new
  58. gets.split.map{|e| e.to_i}.each {|e| q.push(e)}
  59. while !q.empty
  60.     puts q.top
  61.     q.pop
  62. end

评分

参与人数 2星屑 +285 收起 理由
唯道集虚 + 200 精品文章
kuerlulu + 85 塞糖

查看全部评分

tan(pi/2)

Lv3.寻梦者 (版主)

梦石
0
星屑
3085
在线时间
740 小时
注册时间
2015-2-28
帖子
816

开拓者

发表于 2016-11-16 20:00:14 | 显示全部楼层
本帖最后由 唯道集虚 于 2016-11-17 20:12 编辑

记得外站有一个很著名的寻路脚本(好像是Khas写的),我记得好像也有用优先排列?(

不过话说目前仍没有更改的主题标签问题……是我的失误。这里表示很抱歉~我这里会尽快联系安安的。
器识为先,文艺其从。
回复 支持 反对

使用道具 举报

Lv5.捕梦者 (暗夜天使)

只有笨蛋才会看到

梦石
1
星屑
20840
在线时间
9326 小时
注册时间
2012-6-19
帖子
7105

开拓者短篇九导演组冠军

发表于 2016-11-17 17:30:04 | 显示全部楼层
想起了自己以前a*的二叉堆实现,但是实际测试的时候发现速度不如已有二叉堆a*的速度快……
  1. class Heap < Array  
  2.   def [](index); index == 0 ? nil : super(index - 1); end
  3.   def []=(index,value); return if index == 0; super(index - 1, value); end
  4.   def initialize *args; super *args; @index = 0; end
  5.   def value(ele); return ele.value; end
  6.   def push(ele)
  7.     child_index = (@index += 1)
  8.     loop do      
  9.       parent = self[ (parent_index = child_index / 2) ]
  10.       break unless parent
  11.       break if value(parent) <= value(ele)
  12.       self[child_index] = parent
  13.       child_index = parent_index
  14.     end
  15.     self[child_index] = ele
  16.   end
  17.   def shift
  18.     result = self[1]; self[1] = self.pop
  19.     @index -= (parent = 1)   
  20.     loop do
  21.       child1 = ( child2 = parent * 2 ) + 1
  22.       break if @index < child1
  23.       if @index < child2 then child = child1
  24.       else child = value(self[child1]) < value(self[child2]) ? child1 : child2
  25.       end
  26.       break if value(self[parent]) <= value(self[child])
  27.       self[parent], self[child] = self[child], self[parent]
  28.       parent = child
  29.     end
  30.     return result
  31.   end  
  32. end
复制代码

评分

参与人数 1星屑 +100 收起 理由
唯道集虚 + 100 null

查看全部评分

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:[email protected]|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2024-3-29 17:52

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表