#?-*-?coding:?utf-8?-*-
“““
Created?on?Fri?Apr?19?16:25:45?2019

@author:?Yuming
“““
from?Node?import?Node
import?copy

def?showMap（node）:
????print（“代價:“node.g）
????print（“啟發性信息:“node.h）
????print（“估價函數:“node.g+node.h）
????for?x?in?range（0?3）:
????????for?y?in?range（0?3）:
????????????print（node.array2d[x][y]?end=‘‘）
????????print（“?“）
????print（“--------“）
????return;

def?move（array2d?srcX?srcY?drcX?drcY）:
????temp?=?array2d[srcX][srcY]
????array2d[srcX][srcY]?=?array2d[drcX][drcY]
????array2d[drcX][drcY]?=?temp
????return?array2d;

class?Astar:
????
????def?__init__（self?startNode?endNode）:
????????“““?
????????startNode:??尋路起點?
????????endNode:????尋路終點?
????????“““??
????????#開放列列表
????????self.openList?=?[]
????????#封閉列表??
????????self.closeList?=?[]
????????#起點??
????????self.startNode?=?startNode
????????#終點
????????self.endNode?=?endNode?
????????#當前處理的節點
????????self.currentNode?=?startNode
????????#最后生成的路徑
????????self.pathlist?=?[]
????????#step步
????????self.step?=?0
????????
????def?getMinFNode（self）:
????????“““?
????????獲得openlist中f（x）最小的節點
????????“““??
????????nodeTemp?=?self.openList[0]??
????????for?node?in?self.openList:??
????????????if?node.g?+?node.h?????????????????nodeTemp?=?node??
????????return?nodeTemp

????def?nodeInOpenlist（selfnode）:
????????“““
????????判斷結點是否在開放列表
????????“““
????????for?nodeTmp?in?self.openList:??
????????????if?nodeTmp.array2d?==?node.array2d:??
????????????????return?True??
????????return?False

????def?nodeInCloselist（selfnode）:
????????“““
????????判斷結點是否在封閉列表
????????“““
????????for?nodeTmp?in?self.closeList:??
????????????if?nodeTmp.array2d?==?node.array2d:??
????????????????return?True??
????????return?False

????def?endNodeInOpenList（self）:??
????????“““
????????目標狀態是否在開放列表中
????????“““
????????for?nodeTmp?in?self.openList:??
????????????if?nodeTmp.array2d?==?self.endNode.array2d:??
????????????????return?True??
????????return?False

????def?getNodeFromOpenList（selfnode）:??
????????“““
????????返回輸入狀態在開放列表的代價，啟發性信息
????????“““
????????for?nodeTmp?in?self.openList:??
????????????if?nodeTmp.array2d?==?node.array2d:??
????????????????return?nodeTmp??
????????return?None

????def?searchOneNode（selfnode）:
????????“““?
????????將移動后的狀態放入開放列表
????????“““??
????????#忽略封閉列表
????????if?self.nodeInCloselist（node）:??
????????????return??
????????#G值計算?
????????gTemp?=?self.step

????????#如果不在openList中，就加入openlist??
????????if?self.nodeInOpenlist（node）?==?False:
????????????node.setG（gTemp）
????????????#H值計算?
????????????node.setH（self.endNode）;
????????????self.openList.append（node）
????????????node.father?=?self.currentNode
????????#如果在openList中，判斷currentNode到移動后結點的G是否更小
????????#如果更小，就重新計算g值，并且改變父結點?
????????else:
????????????nodeTmp?=?self.getNodeFromOpenList（node）
????????????if?self.currentNode.g?+?gTemp?????????????????nodeTmp.

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????1513??2019-04-21?14:26??Node.py
?????文件????????1031??2019-04-21?16:48??main.py
?????文件????????6048??2019-04-21?16:46??Algorithm.py