Dijkstra路径重建

Question

好吧,所以我在过去的几个星期里一直试图创造一个像游戏这样的流氓,我现在所困扰的是将地牢中的房间与走廊连接起来.请记住,这一切都在C中,我正在使用ncurses.所以我到目前为止所做的就是将Dijkstra的算法从A门运行到B门,记录先前的节点,然后回溯这组先前的节点以获得实际的路径.我的算法目前存在问题,我调试它的步骤是将代码转换为Java,但算法运行良好.现在,我告诉你,让我告诉你实际的问题,这里是没有任何墙壁的10×10网格的最小路径的输出.这是访问过的先前节点的列表.(yx)是起源.

(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.邻居约束

• 您忽略范围 x: < 0,70 ) y: < 0,150 ) 之外的邻居
• 这个上限不应该被你的房间/迷宫大小取代吗？
• 如果您的房间较小，那么路径可能会在您的房间周围走错路......