#coding=utf-8
import random
import math
import time
#节点类
class AstarNode:
	def __init__(self):
		self.cost =  random.randint(1, 5) 
		self.g = 1
		self.h = 0
		self.f = 0
		self.x = 0
		self.y = 0 
		self.parent = None
		self.mark = 0
#寻路类
class AStarPath:
	markopen = 1
	markclose =2
	def __init__(self, xwidth, yheight):
		self.width = xwidth
		self.height = yheight
		print(self.__class__)
		self.matrix = self.genMatrix(xwidth,yheight);

	def genMatrix(self,rows,cols):  
	    matrix = [[0 for col in range(cols)] for row in range(rows)]  
	    for i in range(rows):
	        for j in range(cols):
	            anode = AstarNode() 
	            anode.x = i
	            anode.y = j
	            matrix[i][j] = anode
	            print(matrix[i][j].cost),
	        print '\n'
	    return matrix

	def FindPath(self,startNode,endNode):
		opened = [startNode]
		#closed = []
		startNode.parent = None
		newg =0
		AStarPath.markopen +=1
		AStarPath.markclose = AStarPath.markopen+1
		while len(opened) > 0:
			curNode = opened[0]
			for op in opened:
				if op.f < curNode.f :#and op.g < curNode.g:
					curNode = op
			opened.remove(curNode)
			#closed.append(curNode)
			curNode.mark = AStarPath.markclose
			if curNode == endNode:#找到了
				break
			for naber in self.GetNabers(curNode):
				#if naber not in closed: 
				if naber.mark != AStarPath.markclose: 
					dist = 1
					if naber.x != curNode.x and naber.y != curNode.y:
						dist = 1.4
					#if naber in opened :
					if naber.mark == AStarPath.markopen:
						newg = curNode.g + dist + naber.cost
						if newg <= naber.g:
							naber.parent = curNode
							naber.g = newg
							naber.f = naber.g + naber.h
					else:
						naber.h = abs(naber.x - endNode.x) + abs(naber.y - endNode.y)
						naber.g = curNode.g + dist + naber.cost
						naber.f = naber.g + naber.h
						naber.parent = curNode
						opened.append(naber)
						naber.mark =AStarPath.markopen
						
		#if endNode in closed:
		if endNode.mark == AStarPath.markclose:
			ret = []
			curNode = endNode
			while curNode != None:
				ret.append(curNode)
				curNode = curNode.parent
			ret.reverse()
			return ret
		return []

	def GetNabers(self,node):
		nabers = []
		for x in range(-1,2):
			ix = x + node.x
			if ix <0  or self.width <= ix :
				continue
			for y in range(-1,2):
				iy = y + node.y
				if iy <0  or self.height <= iy :
					continue
				if x == y and x == 0: #自己
					continue
				nabers.append(self.matrix[ix][iy])				
		return nabers
	#转换为节点
	def GetNode(self,x,y):
		if x < 0 or x >= self.width:
			return None
		if y < 0 or y > self.height:
			return None
		return self.matrix[x][y]
astar = AStarPath(5,20)
node = astar.GetNode(0,0)
print("******************* node`s nabers *************************")
for n in astar.GetNabers(node):
	print(n.cost),
print '\n'
ctime = time.time()
for i in range(0,19):
	astar.FindPath(node,astar.GetNode(4,19))
path = astar.FindPath(node,astar.GetNode(4,19))
print("******************* Path *************************")
print( time.time() - ctime)
for node in path:
	print(node.cost),
print '\n'
print("******************* FindPath *************************")
for rows in astar.matrix:
	for mnode in rows:
		if mnode in path:
			print("*"),
		else:
			print(mnode.cost),
	print '\n'



# class AstarMap:

# 	AstarNode[] maps
# 	public void Init(int width,int height)
	

# def genMatrix(rows,cols):  
#     matrix = [[0 for col in range(cols)] for row in range(rows)]  
#     for i in range(rows):  
#         for j in range(cols):  
#             print matrix[i][j],  
#         print '\n'
#     return matrix  	


 
# class AStarPathFinder:
# 	private AstarMap _Map
# 	public AStarPathFinder(AstarMap map)
	
# 		_Map = map
	
# 	public AStarPath FindPath(AstarNode start,AstarNode end)
	

	

# 	public int Arm