C- Dijkstra路径重建

Question

好吧，所以过去几周我一直在尝试创建像游戏这样的流氓，我现在陷入困境的是将房间与走廊的地牢连接在一起。请记住，这全是在C中，我正在使用ncurses。因此，到目前为止，我一直在尝试做的是，将Dijkstra的算法从门A到门B录制以前的节点，然后回溯到以前的节点以获取实际路径。目前，我的算法存在问题，我要调试的步骤是将代码转换为Java，但是该算法运作良好。现在，我告诉您，让我给您实际的问题，这是10乘10个网格的最小路径的输出，而没有任何墙壁。这是访问过的先前节点的列表。（y x）是原点。

(y x)  (1 1)  (0 1)  (1 3)  (0 3)  (1 5)  (0 5)  (1 7)  (0 7)  (1 9)
(0 0)  (2 1)  (0 2)  (2 3)  (0 4)  (2 5)  (0 6)  (2 7)  (0 8)  (2 9)
(1 0)  (3 1)  (1 2)  (3 3)  (1 4)  (3 5)  (1 6)  (3 7)  (1 8)  (3 9)
(2 0)  (4 1)  (2 2)  (4 3)  (2 4)  (4 5)  (2 6)  (4 7)  (2 8)  (4 9)
(3 0)  (5 1)  (3 2)  (5 3)  (3 4)  (5 5)  (3 6)  (5 7)  (3 8)  (5 9)
(4 0)  (6 1)  (4 2)  (6 3)  (4 4)  (6 5)  (4 6)  (6 7)  (4 8)  (6 9)
(5 0)  (7 1)  (5 2)  (7 3)  (5 4)  (7 5)  (5 6)  (7 7)  (5 8)  (7 9)
(6 0)  (8 1)  (6 2)  (8 3)  (6 4)  (8 5)  (6 6)  (8 7)  (6 8)  (8 9)
(7 0)  (9 1)  (7 2)  (9 3)  (7 4)  (9 5)  (7 6)  (9 7)  (7 8)  (9 9)
(8 0)  (10 1) (8 2)  (10 3) (8 4)  (10 5) (8 6)  (10 7) (8 8)  (10 9)

您可以看到，在第0行1上，上一个节点应为（0 0），而不是（1 1）。编辑（我添加新的BFS而不是Dijkstra）

eq(q,startU);
/*while there are elements in the q*/
while(dq(q,&u))
{
    uX = u[1];
    uY = u[0];

    /*break if at the end*/
    if(uX == xEnd && uY == yEnd)
    {
        break;
    }
    seen[uY][uX]=1;
    /*Neighbours around the current cell*/
    for(i=0;i<4;++i)
    {
        vX = uX + neighbours[i][1];
        vY = uY + neighbours[i][0];
        if(!bounds(vX,vY)||seen[vY][vX])
        {
            continue;
        }
        c=(char)mvinch(vY,vX);
        if(c == '+'||c=='|'||c=='-'||c=='.')
        {
            continue;
        }
        p->prev[vY][vX][1]=uX;
        p->prev[vY][vX][0]=uY;
        u[0]=vY;
        u[1]=vX;
        /*enqueue*/
        eq(q,u);

    }
}

Answer 1

1.输入数组看起来像

• 如何启动
• 什么值是空间
• 什么值是墙
• 什么值是门或墙壁开口（您的路径的起始点点）

2.条件（如果）

• 一些编译器不正确地对布尔运营商进行计算优先级

• 尝试添加（）应该在哪里...

  //if(uX == xEnd && uY == yEnd)
  if((uX==xEnd)&&(uY==yEnd))
  

3.Neighbour约束

• 您忽略了范围x的邻居：＆lt;0,70）y：＆lt;0,150）
• 不应该被您的房间/迷宫尺寸代替的上限吗？
• 如果您的房间较小，则该路径可能会在您的房间周围走错路...

Answer 2

我不知道您的其余代码，所以这是我的诊断。查看输出中的模式：

X
|   (y x)  (1 1)  (0 1)  (1 3)  (0 3)  (1 5)  (0 5)  (1 7)  (0 7)  (1 9)
|   (0 0)  (2 1)  (0 2)  (2 3)  (0 4)  (2 5)  (0 6)  (2 7)  (0 8)  (2 9)
V   (1 0)  (3 1)  (1 2)  (3 3)  (1 4)  (3 5)  (1 6)  (3 7)  (1 8)  (3 9)
    (2 0)  (4 1)  (2 2)  (4 3)  (2 4)  (4 5)  (2 6)  (4 7)  (2 8)  (4 9)
    (3 0)  (5 1)  (3 2)  (5 3)  (3 4)  (5 5)  (3 6)  (5 7)  (3 8)  (5 9)
    (4 0)  (6 1)  (4 2)  (6 3)  (4 4)  (6 5)  (4 6)  (6 7)  (4 8)  (6 9)
    (5 0)  (7 1)  (5 2)  (7 3)  (5 4)  (7 5)  (5 6)  (7 7)  (5 8)  (7 9)
    (6 0)  (8 1)  (6 2)  (8 3)  (6 4)  (8 5)  (6 6)  (8 7)  (6 8)  (8 9)
    (7 0)  (9 1)  (7 2)  (9 3)  (7 4)  (9 5)  (7 6)  (9 7)  (7 8)  (9 9)
    (8 0)  (10 1) (8 2)  (10 3) (8 4)  (10 5) (8 6)  (10 7) (8 8)  (10 9)

从给定的列中从上到下遍历y，y首先增加，x仅在下一列开始后增加。

也位于代码的顶行

eq(q,startU);
/*while there are elements in the q*/

因此，基于输出和代码，似乎您似乎在做图形taversal。您正在做的是处理队列中的点，而外圈的内环和x的增加。您正在使用队列遍历处理数据，而不是使用图形遍历。