C++ A* algorithm – row and col getting stack error

  a-star, algorithm, c++

I’m using the a* algorithm to create a rotation, but when I increase the row and col above 180, I get a stack overflow error.

Anyone have any ideas?

my codes, if you run this now, it will not give an error, but if you set the ROW and COL values to 180e or higher, it will give an error.

like the

#define ROW 250
#define COL 250

enter image description here

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <Windows.h>
#include <bits/stdc++.h>
using namespace std;

#define ROW 100
#define COL 100

using namespace std;

typedef pair<int, int> Pair;


typedef pair<double, pair<int, int> > pPair;

struct cell {

    int parent_i, parent_j;
    double f, g, h;
};

namespace Algorithm
{
    bool isValid(int row, int col)
    {
        return (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL);
    }

    bool isUnBlocked(BYTE grid[][COL], int row, int col)
    {
        if (grid[row][col] == 1)
            return (true);
        else
            return (false);
    }

    bool isDestination(int row, int col, Pair dest)
    {
        if (row == dest.first && col == dest.second)
            return (true);
        else
            return (false);
    }

    double calculateHValue(int row, int col, Pair dest)
    {
        return ((double)sqrt(float(
            (row - dest.first) * (row - dest.first)
            + (col - dest.second) * (col - dest.second))));
    }

    void tracePath(cell cellDetails[][COL], Pair dest)
    {
        cout << "The Path is" << endl;
        int row = dest.first;
        int col = dest.second;

        stack<Pair> Path;

        while (!(cellDetails[row][col].parent_i == row
            && cellDetails[row][col].parent_j == col)) {
            Path.push(make_pair(row, col));
            int temp_row = cellDetails[row][col].parent_i;
            int temp_col = cellDetails[row][col].parent_j;
            row = temp_row;
            col = temp_col;
        }

        Path.push(make_pair(row, col));
        while (!Path.empty()) {
            pair<int, int> p = Path.top();
            Path.pop();
            char message[255];
            sprintf(message, "-> (%d,%d) ", p.first, p.second);
            cout << message << endl;
        }

        return;
    }

    void aStarSearch(BYTE grid[][COL], Pair src, Pair dest)
    {
        if (isValid(src.first, src.second) == false) {
            printf("Source is invalidn");
            return;
        }

        if (isValid(dest.first, dest.second) == false) {
            printf("Destination is invalidn");
            return;
        }

        if (isUnBlocked(grid, src.first, src.second) == false
            || isUnBlocked(grid, dest.first, dest.second)
            == false) {
            printf("Source or the destination is blockedn");
            return;
        }


        if (isDestination(src.first, src.second, dest)
            == true) {
            printf("We are already at the destinationn");
            return;
        }

        bool closedList[ROW][COL];
        memset(closedList, false, sizeof(closedList));

        cell cellDetails[ROW][COL];

        int i, j;

        for (i = 0; i < ROW; i++) {
            for (j = 0; j < COL; j++) {
                cellDetails[i][j].f = FLT_MAX;
                cellDetails[i][j].g = FLT_MAX;
                cellDetails[i][j].h = FLT_MAX;
                cellDetails[i][j].parent_i = -1;
                cellDetails[i][j].parent_j = -1;
            }
        }

        i = src.first, j = src.second;
        cellDetails[i][j].f = 0.0;
        cellDetails[i][j].g = 0.0;
        cellDetails[i][j].h = 0.0;
        cellDetails[i][j].parent_i = i;
        cellDetails[i][j].parent_j = j;

        set<pPair> openList;

        openList.insert(make_pair(0.0, make_pair(i, j)));

        bool foundDest = false;

        while (!openList.empty()) {
            pPair p = *openList.begin();

            openList.erase(openList.begin());

            i = p.second.first;
            j = p.second.second;
            closedList[i][j] = true;

            double gNew, hNew, fNew;

            if (isValid(i - 1, j) == true) {

                if (isDestination(i - 1, j, dest) == true) {

                    cellDetails[i - 1][j].parent_i = i;
                    cellDetails[i - 1][j].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i - 1][j] == false
                    && isUnBlocked(grid, i - 1, j)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.0;
                    hNew = calculateHValue(i - 1, j, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i - 1][j].f == FLT_MAX
                        || cellDetails[i - 1][j].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i - 1, j)));


                        cellDetails[i - 1][j].f = fNew;
                        cellDetails[i - 1][j].g = gNew;
                        cellDetails[i - 1][j].h = hNew;
                        cellDetails[i - 1][j].parent_i = i;
                        cellDetails[i - 1][j].parent_j = j;
                    }
                }
            }

            if (isValid(i + 1, j) == true) {

                if (isDestination(i + 1, j, dest) == true) {

                    cellDetails[i + 1][j].parent_i = i;
                    cellDetails[i + 1][j].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i + 1][j] == false
                    && isUnBlocked(grid, i + 1, j)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.0;
                    hNew = calculateHValue(i + 1, j, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i + 1][j].f == FLT_MAX
                        || cellDetails[i + 1][j].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i + 1, j)));

                        cellDetails[i + 1][j].f = fNew;
                        cellDetails[i + 1][j].g = gNew;
                        cellDetails[i + 1][j].h = hNew;
                        cellDetails[i + 1][j].parent_i = i;
                        cellDetails[i + 1][j].parent_j = j;
                    }
                }
            }

            if (isValid(i, j + 1) == true) {

                if (isDestination(i, j + 1, dest) == true) {

                    cellDetails[i][j + 1].parent_i = i;
                    cellDetails[i][j + 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i][j + 1] == false
                    && isUnBlocked(grid, i, j + 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.0;
                    hNew = calculateHValue(i, j + 1, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i][j + 1].f == FLT_MAX
                        || cellDetails[i][j + 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i, j + 1)));

                        cellDetails[i][j + 1].f = fNew;
                        cellDetails[i][j + 1].g = gNew;
                        cellDetails[i][j + 1].h = hNew;
                        cellDetails[i][j + 1].parent_i = i;
                        cellDetails[i][j + 1].parent_j = j;
                    }
                }
            }

            if (isValid(i, j - 1) == true) {

                if (isDestination(i, j - 1, dest) == true) {

                    cellDetails[i][j - 1].parent_i = i;
                    cellDetails[i][j - 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i][j - 1] == false
                    && isUnBlocked(grid, i, j - 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.0;
                    hNew = calculateHValue(i, j - 1, dest);
                    fNew = gNew + hNew;


                    if (cellDetails[i][j - 1].f == FLT_MAX
                        || cellDetails[i][j - 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i, j - 1)));

                        cellDetails[i][j - 1].f = fNew;
                        cellDetails[i][j - 1].g = gNew;
                        cellDetails[i][j - 1].h = hNew;
                        cellDetails[i][j - 1].parent_i = i;
                        cellDetails[i][j - 1].parent_j = j;
                    }
                }
            }

            if (isValid(i - 1, j + 1) == true) {

                if (isDestination(i - 1, j + 1, dest) == true) {

                    cellDetails[i - 1][j + 1].parent_i = i;
                    cellDetails[i - 1][j + 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i - 1][j + 1] == false
                    && isUnBlocked(grid, i - 1, j + 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.414;
                    hNew = calculateHValue(i - 1, j + 1, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i - 1][j + 1].f == FLT_MAX
                        || cellDetails[i - 1][j + 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i - 1, j + 1)));

                        cellDetails[i - 1][j + 1].f = fNew;
                        cellDetails[i - 1][j + 1].g = gNew;
                        cellDetails[i - 1][j + 1].h = hNew;
                        cellDetails[i - 1][j + 1].parent_i = i;
                        cellDetails[i - 1][j + 1].parent_j = j;
                    }
                }
            }


            if (isValid(i - 1, j - 1) == true) {

                if (isDestination(i - 1, j - 1, dest) == true) {
                    cellDetails[i - 1][j - 1].parent_i = i;
                    cellDetails[i - 1][j - 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i - 1][j - 1] == false
                    && isUnBlocked(grid, i - 1, j - 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.414;
                    hNew = calculateHValue(i - 1, j - 1, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i - 1][j - 1].f == FLT_MAX
                        || cellDetails[i - 1][j - 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i - 1, j - 1)));

                        cellDetails[i - 1][j - 1].f = fNew;
                        cellDetails[i - 1][j - 1].g = gNew;
                        cellDetails[i - 1][j - 1].h = hNew;
                        cellDetails[i - 1][j - 1].parent_i = i;
                        cellDetails[i - 1][j - 1].parent_j = j;
                    }
                }
            }


            if (isValid(i + 1, j + 1) == true) {

                if (isDestination(i + 1, j + 1, dest) == true) {

                    cellDetails[i + 1][j + 1].parent_i = i;
                    cellDetails[i + 1][j + 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i + 1][j + 1] == false
                    && isUnBlocked(grid, i + 1, j + 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.414;
                    hNew = calculateHValue(i + 1, j + 1, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i + 1][j + 1].f == FLT_MAX
                        || cellDetails[i + 1][j + 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i + 1, j + 1)));

                        cellDetails[i + 1][j + 1].f = fNew;
                        cellDetails[i + 1][j + 1].g = gNew;
                        cellDetails[i + 1][j + 1].h = hNew;
                        cellDetails[i + 1][j + 1].parent_i = i;
                        cellDetails[i + 1][j + 1].parent_j = j;
                    }
                }
            }

            if (isValid(i + 1, j - 1) == true) {

                if (isDestination(i + 1, j - 1, dest) == true) {

                    cellDetails[i + 1][j - 1].parent_i = i;
                    cellDetails[i + 1][j - 1].parent_j = j;
                    printf("The destination cell is foundn");
                    tracePath(cellDetails, dest);
                    foundDest = true;
                    return;
                }

                else if (closedList[i + 1][j - 1] == false
                    && isUnBlocked(grid, i + 1, j - 1)
                    == true) {
                    gNew = cellDetails[i][j].g + 1.414;
                    hNew = calculateHValue(i + 1, j - 1, dest);
                    fNew = gNew + hNew;

                    if (cellDetails[i + 1][j - 1].f == FLT_MAX
                        || cellDetails[i + 1][j - 1].f > fNew) {
                        openList.insert(make_pair(
                            fNew, make_pair(i + 1, j - 1)));

                        cellDetails[i + 1][j - 1].f = fNew;
                        cellDetails[i + 1][j - 1].g = gNew;
                        cellDetails[i + 1][j - 1].h = hNew;
                        cellDetails[i + 1][j - 1].parent_i = i;
                        cellDetails[i + 1][j - 1].parent_j = j;
                    }
                }
            }
        }

        if (foundDest == false)
            printf("Failed to find the Destination Celln");

        return;
    }
}

int main()
{
    auto grid = new BYTE[ROW][COL];

    for (int x = 0; x != ROW; x++)
    {
        for (int y = 0; y != COL; y++)
        {
            float cord_x = (x * 10) * 100;
            float cord_y = (y * 10) * 100;

            grid[x][y] = 1;
        }
    }

    Pair src = make_pair(8, 0);

    Pair dest = make_pair(174, 96);

    Algorithm::aStarSearch(grid, src, dest);

    cin.get();
    return (0);
}

Source: Windows Questions C++

LEAVE A COMMENT