从前的一个A*

烁灵 posted @ 2015年3月17日 22:53 in Ruby with tags A* 寻路 练习 , 1301 阅读

以前的一个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)

 

Avatar_small
TNDGE Plus One Previ 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter