以前的一个a*练习,搬过来凑个数……
A*算法描述见这篇博文
ruby代码:
#encoding=utf-8 MAP = [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], ] class Point attr_accessor :x attr_accessor :y attr_accessor :g attr_accessor :h attr_accessor :f attr_accessor :parent def initialize(x, y, parent) self.x = x self.y = y self.parent = parent end def to_s "#{super.to_s}, #{[self.x, self.y, self.g, self.h, self.f]}" end end $open = {} $close = {} def find(sx, sy, ex, ey) startP = Point.new(sx, sy, nil) startP.g = 0 pos = startP while (!$open[[ex, ey]]) do dealAround(pos, ex, ey) # 检查周围元素,计算f pos = getMinFPos end pos = $open[[ex, ey]] path = [] while (pos.parent) do path << [pos.x, pos.y] pos = pos.parent end path << [pos.x, pos.y] for y in 0...MAP.size for x in 0...MAP[0].size print (path.include?([x, y])) ? "☆" : (MAP[y][x] == 0 ? "□" : "■") end print "\r\n" end p path end def getMinFPos return nil if $open.size < 1 minG = $open.values[0].g minGPos = $open.values[0] $open.values.each{|pos| if minG > pos.g minG = pos.g minGPos = pos end } return minGPos end def dealAround(pos, endx, endy) # 将pos加入close列表 $close[[pos.x, pos.y]] = pos # 将pos从open列表中移出 $open.delete([pos.x, pos.y]) # 检查周围元素 [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]].each{|posOffset| # 跳过边界 next if pos.x + posOffset[0] < 0 or pos.y + posOffset[1] < 0 or pos.x + posOffset[0] > MAP[0].size - 1 or pos.y + posOffset[1] > MAP.size - 1 # 跳过不可通行的方块 next if MAP[pos.y + posOffset[1]][pos.x + posOffset[0]] != 0 # 跳过close列表 next if $close[[pos.x + posOffset[0], pos.y + posOffset[1]]] newPos = Point.new(pos.x + posOffset[0], pos.y + posOffset[1], pos) # 计算g if posOffset[0].abs + posOffset[1].abs == 2 # 斜向 newPos.g = pos.g + 14 else newPos.g = pos.g + 10 end # 计算h newPos.h = (endx - newPos.x).abs * 10 + (endy - newPos.y).abs * 10 # 计算f newPos.f = newPos.g + newPos.h # 添加到open列表 if $open[[newPos.x, newPos.y]] # 已存在 thePos = $open[[newPos.x, newPos.y]] tempG = ((thePos.x - pos.x).abs + (thePos.y - pos.y).abs == 2) ? (pos.g + 14) : (pos.g + 10) if tempG < thePos.g # 当前节点使g更小 thePos.g = tempG thePos.f = tempG + thePos.h thePos.parent = pos # 修改父节点为当前节点 end else # 不存在 $open[[newPos.x, newPos.y]] = newPos end } end find(0, 0, 7, 7)
2022年8月22日 02:05
This board oversees a large number of schools in the state of Tamil Nadu, and it makes every effort to give its pupils access to a top-notch education. This board also held 11th-class exams during the current academic year in the state of Tamil Nadu, and all students who registered for those exams are currently awaiting the TN +1 Important Question Paper 2023. TNDGE Plus One Previous Paper 2023 The Directorate of Government Examinations, Tamil Nadu, released the TN 11th Question Paper 2023 for these examinations in May. Approximately 88.1% of the pupils that participated in the tests were successful.