我正在尝试为我的大学作业实现A星搜索算法,因此我需要从头开始编写代码。但是我在让它正确工作方面遇到了一些困难。
这是我问题的图片:
如您所见,它确实找到了路径,但不是最容易的路径。
这是我的实现方式:
![灰色框=起点,绿色=终点,黄色=path](https://istack.dev59.com/59Pzg.webp)
这是我的实现方式:
public List<node> updateAstar(){
//clear all the lists
openedNodes.Clear();
closedNodes.Clear();
nodesToLook.Clear();
//check if starpos and endpos are okay
if(startPos!=null && endPos!=null){
float F;
node currentNote=Grid.getNodeAtPos(startPos);
openedNodes.Add(currentNote);
int i = 0;
int size = 100;
while(currentNote.type!=tilesType.END){
if(i<=size){ //debugging purpose. prevent infinite loop
nodesToLook.Clear();
foreach(node nearNode in currentNote.getNearestTiles()){
if(closedNodes.Find(r => ((r.pos.x==nearNode.pos.x)&&(r.pos.y==nearNode.pos.y)))==null){
nodesToLook.Add(nearNode);
}
}
float bestValue=float.PositiveInfinity;
node bestNode=new node();
foreach(node lookingNode in nodesToLook){
//check if current node is not on the closed list
if((closedNodes.Find(r => ((r.pos.x==lookingNode.pos.x)&&(r.pos.y==lookingNode.pos.y)))==null)
&&(openedNodes.Find(r => ((r.pos.x==lookingNode.pos.x)&&(r.pos.y==lookingNode.pos.y)))==null)
&& lookingNode.type!=tilesType.BLOCK){
//calculate F=G+H
//assume path number is 0 for the question purpose
F=lookingNode.G[pathNumber]+lookingNode.H[pathNumber];
if(F<bestValue){
bestValue=F;
bestNode=lookingNode;
}else
closedNodes.Add(lookingNode);
}
}
openedNodes.Add(bestNode);
currentNote=bestNode;
i++;
}else{
Debug.Log("Error getting better path");
break;
}
}
}else Debug.Log("Current path does not have an startpos nor endpos");
return openedNodes;
}
如何实例化每个节点(我将其保存在矩阵中):
coordinate posAux=new coordinate();
this.myNodes=new node[columnNumber,lineNumber];
this.lineNumber=lineNumber;
this.columnNumber=columnNumber;
for(int y=0;y<lineNumber;y++){ // Y Desce = linhas
for(int x=0; x<columnNumber; x++){ // X vai pro lado = colunas
//create a node based on matrix position
posAux.Set(x, y);
tilesType type;
node current=new node(posAux);
//update up and left nodes
//"nodeDireita" means rightNode and "nodeEsquerda" means left node
if(x-1>=0){
current.nodeEsquerda=myNodes[x-1, y];
myNodes[x-1, y].nodeDireita=current;
}
if(y-1>=0){
current.nodeAcima=myNodes[x, y-1];
current.nodeAcima.nodeAbaixo=current;
}
//UNity stuff to set type of node visually based on what object is in it
Collider[] colliders;
if((colliders = Physics.OverlapSphere(coordinate.gridToUnity(posAux), 3f)).Length >0){
foreach(Collider collider in colliders){
objScript obj = collider.gameObject.GetComponent<objScript>();
current.type=obj.type;
if(current.type==tilesType.START){
path Path = new path (obj.pos, obj.posEnd, this);
addPath (Path);
Path.numeroPath=paths.IndexOf(Path);
}
}
}
myNodes[x,y]=current;
}
}
//adicionar vetor[] para H e G com numero de paths nos nodes
//create a vector for multiple paths in each node
int numeroPaths = paths.Count;
for (int y = 0; y < lineNumber; y++) {
for (int x = 0; x < columnNumber; x++) {
myNodes [x, y].H=new float[numeroPaths];
myNodes [x, y].G=new float[numeroPaths];
}
}
//adicionar Heuristica e G para cada node em cada path
//calculate heuristic and G for each node in each path
foreach (path Path in paths) {
coordinate start=Path.startPos, end=Path.endPos;
int numeroPath=paths.IndexOf(Path);
for (int y = 0; y < lineNumber; y++) {
for (int x = 0; x < columnNumber; x++) {
coordinate pos = myNodes [x, y].pos;
//G e H as manhattan distance
/*Mathf.Sqrt(Mathf.Pow((start.x - pos.x), 2) + Mathf.Pow((start.y - pos.y), 2)); euclidian-does not apply x.x */
myNodes [x, y].H[numeroPath]=Mathf.Abs(pos.x-end.x) + Mathf.Abs(pos.y-end.y);
myNodes [x, y].G[numeroPath]=Mathf.Abs(start.x-pos.x) + Mathf.Abs(start.y-pos.y);
}
}
}
代码引用:
--node 是一个自定义类,它包含“G”和“H”值。我使用曼哈顿公式来定义“x”,“y”,“BLOCK”或“NORMAL”(该位置的可用性)。
--openedNodes 是我将正确路径的节点放入的列表。
--closedNodes 是我检查过但具有较大“F”值的节点;
--nodesToLook 是要检查的相邻节点。
感谢任何帮助。 谢谢。
G
和H
值?我没有看到任何成本更新(这是算法的核心部分)。您对列表的处理总体上有些笨拙。例如,您实际上不需要nodesToLook
。相反,直接将节点添加到开放列表中,或者如果它们已经在该列表中,则更新其成本。 - Nico Schertler