Dijkstra path reconstruction

Question

Ok so I have been trying for the past few weeks to create a rogue like game, what I am stuck on right now, is connecting rooms in a dungeon with hallways. Keep in mind this is all in C, and I am using ncurses. So what I have been trying to do so far, is to run Dijkstra's algorithm from Door A to Door B recording previous nodes and then backtracking this set of previous nodes to get the actual path. There is a problem with my algorithm at the moment, the steps I took to debug it was to translate the code to Java, but the algorithm worked perfectly . Now that I told you that let me give you the actual problem, here is the output of the min path of a 10 by 10 grid without any walls. This is a list of previous nodes visited. (y x) is the origin.

(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)

As you can see, on row 0, column 1, the previous node should be (0 0), and not (1 1). EDIT(I am adding my new bfs instead of the 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.what is the input array looks like

• how it is initiated
• what value is space
• what value is wall
• what value is door or opening in wall (start-end points for your path)

2.conditions (if)

• some compilers do not doing computation priorities for boolean operators correctly

• try to add () where they should be ...

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

3.neighbour constrains

• you are ignoring neighbours outside range x: < 0,70 ) y: < 0,150 )
• should not be that upper limit replaced by your room/maze size?
• if your room is smaller then the path can go the wrong way around your room ...

Answer 2

I don't know the rest of your code so here is my diagnosis. See the pattern in your output:

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)

Traversing top to bottom from in a given column, y increases first and x increases only after the beginning of next column.

Also at the top line of your code

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

So based on the output and your code it does not seem like you are doing graph taversal. What you are doing is processing the points in a queue with increasing y in inner loop and x in outer loop. You are processing the data with queue traversal, not with graph traversal.