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

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++