0

（对于某些人来说，我的代码中的坐标约定可能非常混乱——这真的很奇怪。除非有人指出这可能是问题所在，否则我不会解释它。我认为问题在于我使用了“漫游”指针[参见下面的回溯]。）

所以我有这个结构：

typedef struct node astarnode;
struct node{
    int xpos;
    int ypos;
    astarnode* father;
};

我在其上运行 A* 搜索地图上的路径：

void astar(int m,int n,int sx,int sy,int gx,int gy,char *map[]){
    //Yep. A priority queue. Will post code if this happens to be the problem.
PQueue* nodequeue = (PQueue *) malloc(sizeof(PQueue));
initPQueue(nodequeue);
//Just some global variables
rowlimit = m;
collimit = n;
startx = sx;
starty = sy;
goalx = gx;
goaly = gy;
environment = map;

int row = sx;
int col = sy;
astarnode* thisnode = (astarnode *) malloc(sizeof(astarnode));
thisnode->xpos = col;
thisnode->ypos = row;
//The root of the tree is the node with itself as father.
thisnode->father = thisnode;

while(row != gy || col != gx){
    printf("currently in (%d, %d)\n", row, col);
    printAStarNode(thisnode);
    printf("\n");
    //Tedious move functions---see template below
    //putToQueue won't enqueue astarnodes whose fathers are null---see move functions
    astarnode* upleft = moveUpLeft(col, row, thisnode);
    putToQueue(nodequeue, upleft);
    astarnode* up = moveUp(col, row, thisnode);
    putToQueue(nodequeue, up);
    astarnode* upright = moveUpRight(col, row, thisnode);
    putToQueue(nodequeue, upright);
    astarnode* left = moveLeft(col, row, thisnode);
    putToQueue(nodequeue, left);
    astarnode* right = moveRight(col, row, thisnode);
    putToQueue(nodequeue, right);
    astarnode* downleft = moveDownLeft(col, row, thisnode);
    putToQueue(nodequeue, downleft);
    astarnode* down = moveDown(col, row, thisnode);
    putToQueue(nodequeue, down);
    astarnode* downright = moveDownRight(col, row, thisnode);
    putToQueue(nodequeue, downright);
    //And enqueue
    free(thisnode);
    thisnode = (astarnode *) malloc(sizeof(astarnode));
    thisnode = dequeue(nodequeue, thisnode);
    row = thisnode->ypos;
    col = thisnode->xpos;
}
traceback(thisnode);
}

我的回溯功能是

void traceback(astarnode* asn){
astarnode* rover = asn;

while(rover->xpos != startx || rover->ypos != starty){
    printAStarNode(rover);
    printf("\n");
    rover = rover->father;
}
}

我将 astarnode 打印为：

void printAStarNode(astarnode *asn){
int address = (int) asn->father;
int myaddress = (int) asn;
printf("%d : (%d, %d, %d)", myaddress, asn->ypos, asn->xpos, address);
}

我的移动功能模板：

astarnode* moveDown(int x, int y, astarnode* pred){
astarnode* downnode = (astarnode *) malloc(sizeof(astarnode));
//Do necessary translations and then reflect to struct
y += 1;
downnode->xpos = x;
downnode->ypos = y;

if(y > rowlimit){ //This move is infeasible.
    downnode->father = NULL;
} else{
    downnode->father = pred;
}

return downnode;
}

为此，我得到以下跟踪：

currently in (0, 0)
149012584 : (0, 0, 149012584)
currently in (1, 1)
149012712 : (1, 1, 149012584)
currently in (2, 2)
149012888 : (2, 2, 149012712)
currently in (3, 3)
149013080 : (3, 3, 149012888)
currently in (3, 4)
149013240 : (3, 4, 149013080)
currently in (4, 5)
149013512 : (4, 5, 149013240)
currently in (5, 6)
149013720 : (5, 6, 149013512)
currently in (6, 6)
149013880 : (6, 6, 149013720)
currently in (6, 7)
149013912 : (6, 7, 149013720)
currently in (7, 8)
149014392 : (7, 8, 149013912)
currently in (8, 8)
149014616 : (8, 8, 149014392)
<Traceback actually starts here>
149014872 : (9, 9, 149014616)
149014616 : (8, 0, 149014392)
149014392 : (7, 0, 149013912)
149013912 : (6, 0, 149013720)
149013720 : (5, 0, 149013512)
149013512 : (4, 0, 149013240)
149013240 : (3, 0, 149013080)
149013080 : (3, 0, 149012888)
149012888 : (2, 0, 149012712)
149012712 : (1, 0, 149012584)

地址似乎是正确的，但为什么 xpos' 都变成了 0？我错过了什么？

4

1 回答 1

0

我怀疑您的回溯例程会打印出您已经释放的节点。（在关于入队的评论之后的 free() 。）

于 2011-07-13T08:51:44.567 回答