Fix for https://stackoverflow.com/q/76697140/16582

gistfile1.txt

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <queue>
#include <map>
#include <cfloat>
#include <set>

#include <string>
using namespace std;

struct Obstacle {
    double x;
    double y;
    double diameter;
};

struct Waypoint {
    double x;
    double y;
    double cumulativeDistanceEuclidean;
    double cumulativeDistanceManhattan;
    int parentIndex;
};

double calculateEuclideanDistance(const Waypoint& waypoint1, const Waypoint& waypoint2) {
    return std::sqrt(std::pow(waypoint1.x - waypoint2.x, 2) + std::pow(waypoint1.y - waypoint2.y, 2));
}

double calculateManhattanDistance(const Waypoint& waypoint1, const Waypoint& waypoint2) {
    return std::abs(waypoint1.x - waypoint2.x) + std::abs(waypoint1.y - waypoint2.y);
}

bool isWaypointValid(
    const Waypoint& waypoint,
    const std::vector<Obstacle>& obstacles,
    int maxDistFromOriginSquared ) {
    if ( waypoint.x * waypoint.x + waypoint.y * waypoint.y >
        maxDistFromOriginSquared )
        return false;
    for (const Obstacle& obstacle : obstacles) {
        double distance = std::sqrt(std::pow(obstacle.x - waypoint.x, 2) + std::pow(obstacle.y - waypoint.y, 2));
        if (distance <= obstacle.diameter / 2.0) {
            // Waypoint lies inside an obstacle
            return false;
        }
    }
    return true;
}
// this part is generating the waypoints 
std::vector<Waypoint> generateNeighboringWaypoints(
      const Waypoint& currentWaypoint,
      const std::vector<Obstacle>& obstacles,
      int parentIndex,
      int maxDistFromOriginSquared ) {
    std::vector<Waypoint> neighboringWaypoints;

    for (double dx : {-1.0, 0.0, 1.0}) {
        for (double dy : {-1.0, 0.0, 1.0}) {
            if (dx == 0.0 && dy == 0.0) {
                continue;
            }

            Waypoint newWaypoint;
            newWaypoint.x = currentWaypoint.x + dx;
            newWaypoint.y = currentWaypoint.y + dy;
            newWaypoint.cumulativeDistanceEuclidean = currentWaypoint.cumulativeDistanceEuclidean + calculateEuclideanDistance(currentWaypoint, newWaypoint);
            newWaypoint.cumulativeDistanceManhattan = currentWaypoint.cumulativeDistanceManhattan + calculateManhattanDistance(currentWaypoint, newWaypoint);
            newWaypoint.parentIndex = parentIndex;

            if (isWaypointValid(
                 newWaypoint,
                 obstacles,
                 maxDistFromOriginSquared)) {
                neighboringWaypoints.push_back(newWaypoint);
            }
        }
    }

    return neighboringWaypoints;
}

std::vector<Waypoint> exploreWorkspace(
    const std::vector<Obstacle>& obstacles,
    int maxDistFromOriginSquared ) {
    std::vector<Waypoint> waypoints;
    std::queue<int> queue;
    std::set<std::pair<double, double>> visited;

    Waypoint startWaypoint = {-1.0, -1.0, 0.0, 0.0, -1};
    waypoints.push_back(startWaypoint);
    queue.push(0);
    visited.insert({startWaypoint.x, startWaypoint.y});

    while (!queue.empty()) {
        int currentIndex = queue.front();
        queue.pop();
        Waypoint currentWaypoint = waypoints[currentIndex];

        std::vector<Waypoint> neighboringWaypoints = generateNeighboringWaypoints(
            currentWaypoint,
            obstacles,
            currentIndex,
            maxDistFromOriginSquared );

        for (const Waypoint& newWaypoint : neighboringWaypoints) {
            if (!visited.count({newWaypoint.x, newWaypoint.y})) {
                waypoints.push_back(newWaypoint);
                queue.push(waypoints.size() - 1);
                visited.insert({newWaypoint.x, newWaypoint.y});
            }
        }
    }

    return waypoints;
}





    


void printWaypoints(const std::vector<Waypoint>& waypoints) {
    if (waypoints.empty()) {
        std::cout << "No waypoints found." << std::endl;
        return;
    }

    std::cout << "Waypoints: " << std::endl;
    int i = 0;
    for (const Waypoint& waypoint : waypoints) {
        std::cout << "Waypoint " << i << ": (" << waypoint.x << ", " << waypoint.y << ")";
        std::cout << ", Euclidean Distance: " << waypoint.cumulativeDistanceEuclidean;
        std::cout << ", Manhattan Distance: " << waypoint.cumulativeDistanceManhattan;
        std::cout << ", Parent Index: " << waypoint.parentIndex << std::endl;
        i++;
    }
}

int main() {
    // Define the obstacles
    std::vector<Obstacle> obstacles = {
        {0.0, 0.0, 0.5},    // Example obstacle 1 (center x, center y, diameter)
        {0.5, 0.5, 0.3},    // Example obstacle 2
        {-0.5, 0.0, 0.4},   // Example obstacle 3
        {0.3, -0.2, 0.2}    // Example obstacle 4
    };
    int maxDistFromOriginSquared = 20;

    std::vector<Waypoint> waypoints = exploreWorkspace(
        obstacles,
        maxDistFromOriginSquared);

    // Print obstacles
    std::cout << "Obstacles: " << std::endl;
    int obstacleIndex = 1;
    for (const Obstacle& obstacle : obstacles) {
        std::cout << "Obstacle " << obstacleIndex << ": (" << obstacle.x << ", " << obstacle.y << "), Diameter: " << obstacle.diameter << std::endl;
        obstacleIndex++;
    }
    std::cout << std::endl;

    // Print waypoints
    printWaypoints(waypoints);

    return 0;
}

Hey, thankyou soo much for your reply. But the code still fails and gives a seg fault. Can we try to further resolve it. I added some more checks but the issue persists.

When I download the code in this gist, build and run it, then it runs perfectly.

Build log

g++  -std=c++17 -g  \
-c -o .vscode/obj/main.o ./src/main.cpp
g++ -g \
-o bin/starter.exe .vscode/obj/main.o  \

Output

Obstacles: 
Obstacle 1: (0, 0), Diameter: 0.5
Obstacle 2: (0.5, 0.5), Diameter: 0.3
Obstacle 3: (-0.5, 0), Diameter: 0.4
Obstacle 4: (0.3, -0.2), Diameter: 0.2

Waypoints:
Waypoint 0: (-1, -1), Euclidean Distance: 0, Manhattan Distance: 0, Parent Index: -1
Waypoint 1: (-2, -2), Euclidean Distance: 1.41421, Manhattan Distance: 2, Parent Index: 0
Waypoint 2: (-2, -1), Euclidean Distance: 1, Manhattan Distance: 1, Parent Index: 0
Waypoint 3: (-2, 0), Euclidean Distance: 1.41421, Manhattan Distance: 2, Parent Index: 0
Waypoint 4: (-1, -2), Euclidean Distance: 1, Manhattan Distance: 1, Parent Index: 0
Waypoint 5: (-1, 0), Euclidean Distance: 1, Manhattan Distance: 1, Parent Index: 0
Waypoint 6: (0, -2), Euclidean Distance: 1.41421, Manhattan Distance: 2, Parent Index: 0
Waypoint 7: (0, -1), Euclidean Distance: 1, Manhattan Distance: 1, Parent Index: 0
Waypoint 8: (-3, -3), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 1
Waypoint 9: (-3, -2), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 1
Waypoint 10: (-3, -1), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 1
Waypoint 11: (-2, -3), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 1
Waypoint 12: (-1, -3), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 1
Waypoint 13: (-3, 0), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 2
Waypoint 14: (-3, 1), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 3
Waypoint 15: (-2, 1), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 3
Waypoint 16: (-1, 1), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 3
Waypoint 17: (0, -3), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 4
Waypoint 18: (0, 1), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 5
Waypoint 19: (1, -3), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 6
Waypoint 20: (1, -2), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 6
Waypoint 21: (1, -1), Euclidean Distance: 2.82843, Manhattan Distance: 4, Parent Index: 6
Waypoint 22: (1, 0), Euclidean Distance: 2.41421, Manhattan Distance: 3, Parent Index: 7
Waypoint 23: (-4, -2), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 8
Waypoint 24: (-2, -4), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 8
Waypoint 25: (-4, -1), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 9
Waypoint 26: (-4, 0), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 10
Waypoint 27: (-1, -4), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 11
Waypoint 28: (0, -4), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 12
Waypoint 29: (-4, 1), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 13
Waypoint 30: (-4, 2), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 14
Waypoint 31: (-3, 2), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 14
Waypoint 32: (-2, 2), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 14
Waypoint 33: (-1, 2), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 15
Waypoint 34: (0, 2), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 16
Waypoint 35: (1, -4), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 17
Waypoint 36: (1, 1), Euclidean Distance: 3.41421, Manhattan Distance: 4, Parent Index: 18
Waypoint 37: (1, 2), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 18
Waypoint 38: (2, -4), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 19
Waypoint 39: (2, -3), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 19
Waypoint 40: (2, -2), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 19
Waypoint 41: (2, -1), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 20
Waypoint 42: (2, 0), Euclidean Distance: 4.24264, Manhattan Distance: 6, Parent Index: 21
Waypoint 43: (2, 1), Euclidean Distance: 3.82843, Manhattan Distance: 5, Parent Index: 22
Waypoint 44: (-3, 3), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 30
Waypoint 45: (-2, 3), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 31
Waypoint 46: (-1, 3), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 32
Waypoint 47: (0, 3), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 33
Waypoint 48: (1, 3), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 34
Waypoint 49: (2, 2), Euclidean Distance: 4.82843, Manhattan Distance: 6, Parent Index: 36
Waypoint 50: (2, 3), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 37
Waypoint 51: (3, -3), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 38
Waypoint 52: (3, -2), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 39
Waypoint 53: (3, -1), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 40
Waypoint 54: (3, 0), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 41
Waypoint 55: (3, 1), Euclidean Distance: 5.65685, Manhattan Distance: 8, Parent Index: 42
Waypoint 56: (3, 2), Euclidean Distance: 5.24264, Manhattan Distance: 7, Parent Index: 43
Waypoint 57: (-2, 4), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 44
Waypoint 58: (-1, 4), Euclidean Distance: 6.65685, Manhattan Distance: 9, Parent Index: 45
Waypoint 59: (0, 4), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 46
Waypoint 60: (1, 4), Euclidean Distance: 6.65685, Manhattan Distance: 9, Parent Index: 47
Waypoint 61: (2, 4), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 48
Waypoint 62: (3, 3), Euclidean Distance: 6.24264, Manhattan Distance: 8, Parent Index: 49
Waypoint 63: (4, -2), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 51
Waypoint 64: (4, -1), Euclidean Distance: 6.65685, Manhattan Distance: 9, Parent Index: 52
Waypoint 65: (4, 0), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 53
Waypoint 66: (4, 1), Euclidean Distance: 6.65685, Manhattan Distance: 9, Parent Index: 54
Waypoint 67: (4, 2), Euclidean Distance: 7.07107, Manhattan Distance: 10, Parent Index: 55

Please post your build log and output when you try to run my, unaltered, code.

@Tejal-19 hello?

ohh I'm trying to run it using vscode and it prints nothing. Is it something vscode ?

can you please explain your file structure

Did you look at the build log I posted yesterday? All the code is in one file. Please post your build log ( 2nd time I have asked )

Hey, thankyou soo much for your help. The issue was with VS code. Resolved it. Thankyou