Beta Particle Beta Particle - 6 days ago 4
C++ Question

Error C2678 C++ A* Pathfinding

I'm currently working on implementing the A* pathfinding algorithm in C++. I tried to run my code to see if the display grid function was working but got the C2678 error: binary '<': no operator found which takes a left-hand operand of type 'const Coord' (or there is no acceptable conversion).

I know that my program is messy and probably not efficient at all however i was trying to get a basic version working before optimising. Is the error because I'm trying to output a boolean value of a Coord structure?

Code:

#include <iostream>
#include <fstream>
#include <chrono>
#include <thread>
#include <vector>
#include <set>

using std::chrono::milliseconds;
using std::chrono::duration_cast;
using std::this_thread::sleep_for;

typedef std::chrono::steady_clock the_clock;

struct Location {
int g = 0; // Distance covered so far
int h = 0; // Estimate of distance to goal
float f = 0; // Estimated cost of the complete path
bool walkable = 0; // 0 = Walkable, 1 = Wall
};

// Structure
struct Coord {
int x;
int y;
Location location;
};

// Declare size of grid
#define WIDTH 10
#define HEIGHT 10

typedef Location Array[HEIGHT][WIDTH];
Location grid[HEIGHT][WIDTH]; // Create an array of locations

void displayGrid() {
/* Displays the Grid to the console! */
system("CLS");
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
std::cout << grid[y][x].walkable;
}
std::cout << "\n";
}
sleep_for(milliseconds(100)); // Visual delay
}

void initialiseGrid() {
/* Fills the Grid array with values */
srand((unsigned)time(0));

for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
grid[y][x].walkable = 0;
}
}

/* Test grid */
grid[4][2].walkable = 1;
grid[5][2].walkable = 1;
grid[4][3].walkable = 1;
grid[5][3].walkable = 1;
grid[4][5].walkable = 1;
grid[5][5].walkable = 1;
grid[4][6].walkable = 1;
grid[5][6].walkable = 1;
}

void Astar(Coord startPoint, Coord endPoint) {
/**/
std::set<Coord> closedSet = {}; // Nodes that do not have to be considered again
std::set<Coord> openSet = {}; // Nodes still to be considered to find the shortest path

Coord currentNode; // Current node
currentNode.x = startPoint.x;
currentNode.y = startPoint.y;
currentNode.location.g = 0; // 0 Distance from starting point

openSet.insert(currentNode); // Insert starting node

while (openSet.empty() == false) { // Loop while open list is not empty

for (std::set<Coord>::iterator it = openSet.begin(); it != openSet.end(); it++) { // Iterate through each element in the open set to find the lowest F value
if ((*it).location.f < currentNode.location.f) { // Check if iterator f value is smaller than the current value
currentNode = *it; // Update the current node
}
}

openSet.erase(currentNode); // Drop from the open set since been checked
closedSet.insert(currentNode); // Add to the closed set
}
}


int main(int argc, char *argv[]) {
// Set start and end points
Coord start;
start.x = 3;
start.y = 3;
Coord end;
end.x = 5;
end.y = 6;

initialiseGrid(); // Put -1 (empty) in

// Start timing
the_clock::time_point startTime = the_clock::now();

// Stop timing
the_clock::time_point endTime = the_clock::now();

// Compute the difference between the two times in milliseconds
auto time_taken = duration_cast<milliseconds>(endTime - startTime).count();

displayGrid();

std::cout << "That took: " << time_taken << " ms" << std::endl;

return 0;
}

Answer

The easiest way to solve the issue with std::set requiring a strict-weak-ordering and your Coord class is to provide an operator < comparing the x and y values in Coord, and returning whether one Coord is less than another Coord using these values.

You can do this with std::tie

#include <tuple>
//...
struct Coord {
    int x;
    int y;
    Location location;
    bool operator <(const Coord& c) const 

    // returns true if this->x and this->y < c.x and c.y, false otherwise
    { return std::tie(x,y) < std::tie(c.x,c.y); }  
};

The std::tie compares the x components, then if equal, compares the y components. The result of the comparison is returned (either true if the first set of x,y components is less than the second set of x,y components, or false otherwise).

Live Example here