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

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