所以我正在使用C语言实现A*算法。以下是步骤。
我使用优先队列[使用数组]来存储所有开放的节点。由于我会有重复的距离，也就是说有多个具有相同距离/优先级的节点，因此在将节点插入PQ时，如果插入节点的父节点具有相同的优先级，则仍然交换它们两个，以便我的最新成员保持在顶部（或尽可能高），以便我继续沿着特定的方向前进。另外，在移除时，当我将最上面的元素与最后一个元素交换时，如果交换的最后一个元素与其任一子元素具有相同的元素，则再次将其交换到底部。（我不确定这是否会对任何方面产生影响）。
现在的问题是，假设我有一个100 * 100的矩阵，并且我在移动的2D数组中从（0,20）到（15,20）都有障碍物。现在对于起始位置（2,2）和结束位置（16,20），我得到了一条直线路径，即首先一直向右走，然后向下走到15，然后向右移动一格，就完成了。
但是，如果我将起点设置为（2,2），终点设置为（12,78），即点之间被障碍物分开，路径必须绕过它，则我仍然通过（16,20），并且我的路径在（16,20）之后仍然是直线，但是我的路径到（16,20）是曲折的，即我先向下走一段距离，然后向右走，然后向下走，然后向右走，以此类推，最终到达（16,20）并直接前往目的地。
为什么这条路径的前半部分会是曲折的？我该怎么做才能确保我的路径是直线的，就像当我的目的地是（16,20）而不是（12,78）时一样。
谢谢。
我使用优先队列[使用数组]来存储所有开放的节点。由于我会有重复的距离，也就是说有多个具有相同距离/优先级的节点，因此在将节点插入PQ时，如果插入节点的父节点具有相同的优先级，则仍然交换它们两个，以便我的最新成员保持在顶部（或尽可能高），以便我继续沿着特定的方向前进。另外，在移除时，当我将最上面的元素与最后一个元素交换时，如果交换的最后一个元素与其任一子元素具有相同的元素，则再次将其交换到底部。（我不确定这是否会对任何方面产生影响）。
现在的问题是，假设我有一个100 * 100的矩阵，并且我在移动的2D数组中从（0,20）到（15,20）都有障碍物。现在对于起始位置（2,2）和结束位置（16,20），我得到了一条直线路径，即首先一直向右走，然后向下走到15，然后向右移动一格，就完成了。
但是，如果我将起点设置为（2,2），终点设置为（12,78），即点之间被障碍物分开，路径必须绕过它，则我仍然通过（16,20），并且我的路径在（16,20）之后仍然是直线，但是我的路径到（16,20）是曲折的，即我先向下走一段距离，然后向右走，然后向下走，然后向右走，以此类推，最终到达（16,20）并直接前往目的地。
为什么这条路径的前半部分会是曲折的？我该怎么做才能确保我的路径是直线的，就像当我的目的地是（16,20）而不是（12,78）时一样。
谢谢。
void findPath(array[ROW][COLUMN],sourceX,sourceY,destX,destY) {
PQ pq[SIZE];
int x,y;
insert(pq,sourceX,sourceY);
while(!empty(pq)) {
remove(pq);
if(removedIsDestination)
break; //Path Found
insertAdjacent(pq,x,y,destX,destY);
}
}
void insert(PQ pq[SIZE],element){
++sizeOfPQ;
PQ[sizeOfPQ]==element
int i=sizeOfPQ;
while(i>0){
if(pq[i].priority <= pq[(i-1)/2].priority){
swapWithParent
i=(i-1)/2;
}
else
break;
}
}
___？目前我正在执行absolute(x-dx) + absolute(y-dy)。 - user1868357