Code logic error on recursive algorithm

Question

I have a struct for an A* algorithm, which is defined by:

typedef struct matriz{
    int g,h,f;
    bool isBarrier, isStart, isEnd;
}matrix;

I have made an Matrix out of this structure, and made all the initial values 0.

matrix n[8][8];

And then I've made an algorithm to calculate the distance between the start position to the current position.

For that purpose I have used an recursive method as the steps would be the amount of steps it took to get to that position, which will increase every time it goes to calculate another position:

bool checkbounds(int x, int y){
    if(x>=0 && x<=totalsize-1){
        if(y>=0 && y<=totalsize-1) return true;
    }
    return false;
}

bool isGNull(int x, int y){
    if(n[x][y].g==0)return true;
    return false;
}

void countg(int x, int y, int steps){
    if(checkbounds(x-1,y)){
        if(isGNull(x-1,y)){
            n[x-1][y].g=steps;
            countg(x-1,y,steps+1);
        }
    }
    if(checkbounds(x,y-1)){
        if(isGNull(x,y-1)){
            n[x][y-1].g=steps;
            countg(x,y-1,steps+1);
        }
    }
    if(checkbounds(x+1,y)){
        if(isGNull(x+1,y)){
            n[x+1][y].g=steps;
            countg(x+1,y,steps+1);
        }
    }
    if(checkbounds(x,y+1)){
        if(isGNull(x,y+1)){
            n[x][y+1].g=steps;
            countg(x,y+1,steps+1);
        }
    }
}

The problem is that it was supposed to return to the initial steps value when getting back of the recursion.

The expected result was supposed to be like:

| 5  4  3  2  3  4  5  6 |
| 4  3  2  1  2  3  4  5 |
| 3  2  1  S  1  2  E  6 |
| 4  3  2  1  2  3  4  5 |
| 5  4  3  2  3  4  5  6 |
| 6  5  4  3  4  5  6  7 |
| 7  6  5  4  5  6  7  8 |
| 8  7  6  5  6  7  8  9 |

Where S is the start position and E is the end position.

but what I get is:

| 5  4  3  2 35 36 53 54 |
| 6 19 20  1 34 37 52 55 |
| 7 18 21  S 33 38  E 56 |
| 8 17 22 31 40 39 50 57 |
| 9 16 23 30 41 48 49 58 |
|10 15 24 29 42 47 60 59 |
|11 14 25 28 43 46 61 64 |
|12 13 26 27 44 45 62 63 |

Is probably some logic error, but I'm having some trouble to find it, can someone help me?

--EDIT-- The user Elazar made an certain improvement to the size of the algorithm, but still gives the same result as before.

bool checkbounds(int x, int y) {
    return 0 <= x && x < totalsize
        && 0 <= y && y < totalsize;
}

void countg(int _x, int _y, int steps) {
    static int d[] = {-1, 0, 1, 0};
    for (int i = 0; i < 4; i++) {
        int x = _x+d[i], y = _y+d[3-i];
        if (checkbounds(x,y) && n[x][y].g==0) {
            n[x][y].g=steps;
            countg(x,y,steps+1);
        }
    }
}

Thanks in advance.

Answer 1

Your recursive algorithm will wander up, then left, then down, then right, labeling the distance it's traveled so far. Look again at the numbers and you can see the route it took.

| 5 <4 <3 <2 35 36 53 54 |
  v        ^
| 6 19>20  1 34 37 52 55 |
  v  ^  v  ^
| 7 18 21  S 33 38  E 56 |
  v  ^  v
| 8 17 22 31 40 39 50 57 |
  v  ^  v
| 9 16 23 30 41 48 49 58 |
  v  ^  v
|10 15 24 29 42 47 60 59 |
  v  ^  v
|11 14 25 28 43 46 61 64 |
  v  ^  v
|12>13 26>27 44 45 62 63 |

Then, when it finally reaches the bottom right, it unwinds the stack and doesn't keep going because everything has a number. This is called a depth first search.

The easiest change would be to alter your algorithm to actually work would be to check if the current steps is shorter than the previous steps, instead of if the previous steps was "null". But in the words of patashu, "it would be horrendously inefficient".

This algorithm isn't even remotely close to an A*, and it's hard to see how it could be turned into one. A* is a breadth first search, and requires you to perform several paths in an interleaved manner. I very much recommend starting over from scratch.

Answer 2

Not an answer, but it stings my eyes:

bool checkbounds(int x, int y) {
    return 0 <= x && x < totalsize
        && 0 <= y && y < totalsize;
}

void countg(int _x, int _y, int steps) {
    static int d[] = {-1, 0, 1, 0};
    for (int i = 0; i < 4; i++) {
        int x = _x+d[i], y = _y+d[3-i];
        if (checkbounds(x,y) && n[x][y].g==0) {
            n[x][y].g=steps;
            countg(x,y,steps+1);
        }
    }
}

Answer 3

You're doing a depth first instead of breadth first search (notice that it takes one looong path from 1 to 64, then never tries anything else) recursive search. Meaning that you're travelling all the way down the first path, trying every single cell, then after that's done you try the next direction from the cell one up, then the cell one up, the cell one up... the starting cell, and each time you find no other place to go.

This is not well suited for being coded recursively, IMO. Instead, you should keep a data structure of all cells that you have not checked the neighbours of yet (call it the open set, in A* terminology) and continually

1) check to see if anything is in the open set (else you're done)

2) else pick the best candidate for the best path (lowest cost so far + lowest admissive heuristic if using one) and check all of its neighbours - every path you make from it or improve, add to the open set