0

I am trying to implement A* algorithm (with visualization in Qt). I've got this method:

result_path astar_algorithm::calculate(mapview* m_view)
{
    map_view = m_view;
    auto closed_set = std::vector<std::shared_ptr<node>>();
    auto start_node = std::make_shared<node>(_start);
    auto open_set = std::vector<std::shared_ptr<node>>{start_node};
    std::map<node, node> came_from;

    std::shared_ptr<node> current;
    while (!open_set.empty())
    {
        current = *std::min_element(open_set.begin(), open_set.end());
        if (*current == _end)
        {
            // TODO: Reconstruct a result path!!!
            break;
        }
        open_set.erase(std::find(open_set.begin(), open_set.end(), current));
        closed_set.push_back(current);
        auto neighbors = get_neighbors(*current);
        for (auto& neighbor : neighbors)
        {
            if (std::find_if(closed_set.begin(), closed_set.end(),
                             [&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
                closed_set.end())
                continue;

            auto tentative_g_score = current->G + 1;

            if (std::find_if(open_set.begin(), open_set.end(), [&](std::shared_ptr<node> const& p) {
                    return *p == neighbor;
                }) == open_set.end())
            {
                neighbor.G = tentative_g_score;
                neighbor.H = heuristic_cost_estimate(neighbor.pos, _end);
                neighbor.parent = current;
                open_set.push_back(std::make_shared<node>(neighbor));
            }
            else if (tentative_g_score < neighbor.G)
            {
                neighbor.parent = current;
                neighbor.G = tentative_g_score;
            }
        }
    }
    auto result = result_path();
    while (*current != *start_node)
    {
        result.path.push_back(current->pos);
        current = current->parent;
    }
    result.path.push_back(start_node.pos);
    std::reverse(result.path.begin(), result.path.end());
    return result;
}

It works, but I have a few problems:

if (std::find_if(closed_set.begin(), closed_set.end(),
                             [&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
                closed_set.end())
                continue;

This line checks if a node is present in an std::vector and if so, it continues the loop (then there is a second line similar to this, it just checks if node is not actually present in the vector). I guess the better way would be to store those nodes in a vector and then searching and further adding would be easier (cuz I just have to check if the insert succeeded).

The problem is, afaik, to make this work I have to implement < operator. And so I did. I also made == and !=:

class node
{
public:
    node() {}
    node(const QPoint& p) : pos(p) {}
    bool operator == (const node& o ) const { return pos == o.pos; }
    bool operator == (const QPoint& o ) const { return pos == o; }
    bool operator != (const node& o) const {return pos != o.pos; }
    bool operator <(const node& o ) const { return G + H < o.G + o.H; }
    QPoint pos;
    std::shared_ptr<node> parent;
    int G = 0;
    int H = 0;
};

It works perfectly for the earlier search for std::min_element (it searches for a node with the lowest F value (F=G+H)), it uses < operator. But then I tried to use a set, so those two vectors at the beginning of the method were set and when I wanted to just insert or even check if a node is already in a set and then insert I had a problem. Many of those nodes will have the same G+H value, as the maze which I used was kind of simple (i.e. a maze completely without terrains). I checked it under the debugger and the nodes with unique .pos values (QPoint) were not added to the set just like they weren't unique (but if the node had a different G+H value than any node in the set, it would be added). For the vector the same nodes of course work, cuz there are no checks made, I checked everything carefully under the debugger.

I don't know if I am getting this wrong, but I thought it would use a == or != operators but as seen in this answer: link, it actually uses < operator, which in my case would not distinguish between two nodes (cuz the unique part of each node is its position in the grid (node represents a box in a grid, which can represent a maze or smth similar))

So, is there something I am doing wrong or am I actually getting this right, and the inserting (which checks if the element is unique) or checking if the element exists in a set uses < operator and I cannot do anything about it? (cuz I would like to have my < operator with comparing G+H and then I would like the searching/inserting to use the == operator to compare)

This is the example that I wrote (I forgot I have Microsoft C++ Compiler from the command line - cl.exe)

#include <algorithm>
#include <iostream>
#include <memory>
#include <set>

class Point
{
public:
    int _x, _y;
    Point() : _x(0), _y(0) {}
    Point(int x, int y) : _x(x), _y(y) {}
    bool operator==(const Point& p) const { return _x == p._x && _y == p._y; }
    bool operator!=(const Point& p) const { return _x != p._x && _y != p._y; }
};

class node
{
public:
    node() {}
    node(const Point& p) : pos(p) {}
    bool operator==(const node& o) const { return pos == o.pos; }
    bool operator==(const Point& o) const { return pos == o; }
    bool operator!=(const node& o) const { return pos != o.pos; }
    bool operator<(const node& o) const { return G + H < o.G + o.H; }
    Point pos;
    std::shared_ptr<node> parent;
    int G = 0;
    int H = 0;
};

int main()
{
    node n1(Point(0, 0));
    n1.G = 1;
    n1.H = 1;
    node n2(Point(1, 1));
    n2.G = 2;
    n2.H = 2;
    node n3(Point(2, 2));
    n3.G = 1;
    n3.H = 1;
    std::set<node> nodes;
    nodes.insert(n1);
    nodes.insert(n2);
    nodes.insert(n3);
    auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;
    std::cout << min._x << " " << min._y << '\n';
    std::cout << nodes.size() << '\n';
}

>main.exe
0 0
2

std::min_element works, but those are 3 unique nodes for me (differet .pos values) so there should be 3 nodes in the set. And that's what I want to achieve

dabljues
  • 1,663
  • 3
  • 14
  • 30
  • *which in my case would not distinguish between two nodes* -- Then `operator <` does not follow a strict-weak-ordering, something most (if not all) uses of `operator <` in the standard library requires. For example, `std::sort` would have also failed to work, or would have bizarre behavior if you attempted to sort those entries. – PaulMcKenzie Feb 06 '19 at 15:06
  • Okay, you see the cases I need to cover. G+H for std::min_element and comparing by `. pos` for inserting to a set. Can I somehow make those both work? – dabljues Feb 06 '19 at 15:10
  • And by the way, I thought that `operator<` should not distinguish two different objects, just say which one is less, by property – dabljues Feb 06 '19 at 15:13
  • It basically boils down to [this answer](https://stackoverflow.com/questions/21842749/stdsort-comparing-elements-to-null/21843204#21843204). Whatever the case, you can't have `a < b` and at the same time `b < a` for the same values of `a` and `b`. If we had your entire code, don't be surprised if run under Visual Studio debug runtime, your code asserts with a failure when inserting into the set. – PaulMcKenzie Feb 06 '19 at 15:13
  • Right, but comparing by operator< I made follows strict-weak-ordering. When inserting to a set I don't want to compare which is less, I want to compare equality, by different property (.pos). So there's no way to do that? And I have to write either min element or checking the existence by hand? And then if I would write a function to search for the minimum element, how would I write operator< for comparing by `.pos`? I know I can `<` two `QPoints` but that seems kinda stupid for the uniqueness check... – dabljues Feb 06 '19 at 15:23
  • I don't see where you are using `std::set`. Second, I think you could have whittled this entire code down to a [mcve], showing `std::set`, your class, your lambda or functor you're using to determine `<`. – PaulMcKenzie Feb 06 '19 at 15:29
  • I tried before, the objects were not added to the set, so I switched to a vector. I'm on a train without a compiler, but I will try to provide an example with a set – dabljues Feb 06 '19 at 15:29
  • Then we are shooting in the dark. We have no idea what you really tried since we don't have the code.. – PaulMcKenzie Feb 06 '19 at 15:31
  • I don't want to store duplicates @rustyx. I want the objects which are not duplicates (have a different property value - .pos property) to be added to the set, and not treated as duplicates. PaulMcKenzie I am just writing a quick example outside this project to show what I am trying to achieve – dabljues Feb 06 '19 at 15:47
  • 1
    @dabljues -- `std::set` has a [second template argument](https://en.cppreference.com/w/cpp/container/set). This is where you specify a custom comparitor (but still must follow a strict-weak-order). Your code does not utilize this template parameter. – PaulMcKenzie Feb 06 '19 at 15:56
  • @dabljues: With your `operator<` and `a = {1, 2}; b = {2, 1}`, both `a < b` and `b < a` are false. Therefore, `std::set` considers them identical. – You Feb 06 '19 at 15:58
  • ^You're right. But how can I fix it in my situation? – dabljues Feb 06 '19 at 16:34

1 Answers1

2

I thought it would use a == or != operators

No, std::set does not use operators == and !=, std::set uses just one function, the comparison function (the second template argument, which defaults to std::less<T>).

Uniqueness is based on the equivalence relation which is derived from applying the same comparison function twice: !a<b && !b<a.

It seems you don't really need uniqueness, in which case you can use std::multiset instead. It will maintain the order, but will not enforce uniqueness.

std::set<node> nodes;
. . .
auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;

std::min_element is always O(N). Using it on a set defeats the purpose of having a set. Just get the first element, which will be the smallest (according to the comparison function).

auto min = begin(nodes)->pos;
rustyx
  • 80,671
  • 25
  • 200
  • 267
  • I don't think we understand each other. G and H may be mixed up. It doesn't matter. But if G+H on two nodes is equal, then they are considered equal and therefore the second one is not added to the set. But I want to distinguish them by `.pos` (coordinates). And doing that I still want to preserve the functionality of `std::min_element` which finds this lowest element by comparing G + H on both nodes – dabljues Feb 06 '19 at 17:11
  • 1
    @dabljues -- Then you need to write your `<` so that it is unique, bottom line, whatever it takes (think outside the box). Maybe multiply one of the values, maybe store the items in a pair (pairs have an available <), whatever. This is more of a logical issue than a C++ one. – PaulMcKenzie Feb 06 '19 at 17:15
  • Okay, I get it. By the way, is there a reason why sets use `<` instead of `==` for checking uniqueness? – dabljues Feb 06 '19 at 17:30
  • It's how a set (binary tree) works. Also see my updated answer, hope it helps. – rustyx Feb 06 '19 at 20:10