Skip to main content
Code Review

Return to Answer

added 163 characters in body
Source Link
user555045
user555045
  • 10.7k
  • 1
  • 16
  • 32
  • All nodes could be owned by one big vector which is destroyed all in one go when the function returns (the destructor of Node can be trivial as long as T has a trivial destructor, then all the nodes in the vector just poof out of existence without ceremony). References to nodes can be replaced with indexes into that vector, or if you really want, you could still dynamically allocate the individual nodes and refer to them by non-owning pointer (except in the vector, which would own them with a unique pointer), but that negates some of the benefit of doing this.
  • The parent relationships could be recorded outside the nodes, in a map from T to T. This way the nodes are only needed as part of the Open set (the only thing needed from a closed node is its parent, but that isn't in the node anymore in this scheme), which could own them by value. This may be bad if T is a large type, because it creates a lot more Ts.
    By the way, you are already using a similar approach for the closed set, which in some implementations is implemented as a bool isClosed in the Node class.
  • If the search space is a grid, temporary grids can be used to store the nodes (or its separate constituents). Nodes could be referred to by their position in the grid, parents specifically can also be recorded by their direction.
  • All nodes could be owned by one big vector which is destroyed all in one go when the function returns (the destructor of Node can be trivial as long as T has a trivial destructor, then all the nodes in the vector just poof out of existence without ceremony). References to nodes can be replaced with indexes into that vector, or if you really want, you could still dynamically allocate the individual nodes and refer to them by non-owning pointer (except in the vector, which would own them with a unique pointer), but that negates some of the benefit of doing this.
  • The parent relationships could be recorded outside the nodes, in a map from T to T. This way the nodes are only needed as part of the Open set (the only thing needed from a closed node is its parent, but that isn't in the node anymore in this scheme), which could own them by value. This may be bad if T is a large type, because it creates a lot more Ts.
  • If the search space is a grid, temporary grids can be used to store the nodes (or its separate constituents). Nodes could be referred to by their position in the grid, parents specifically can also be recorded by their direction.
  • All nodes could be owned by one big vector which is destroyed all in one go when the function returns (the destructor of Node can be trivial as long as T has a trivial destructor, then all the nodes in the vector just poof out of existence without ceremony). References to nodes can be replaced with indexes into that vector, or if you really want, you could still dynamically allocate the individual nodes and refer to them by non-owning pointer (except in the vector, which would own them with a unique pointer), but that negates some of the benefit of doing this.
  • The parent relationships could be recorded outside the nodes, in a map from T to T. This way the nodes are only needed as part of the Open set (the only thing needed from a closed node is its parent, but that isn't in the node anymore in this scheme), which could own them by value. This may be bad if T is a large type, because it creates a lot more Ts.
    By the way, you are already using a similar approach for the closed set, which in some implementations is implemented as a bool isClosed in the Node class.
  • If the search space is a grid, temporary grids can be used to store the nodes (or its separate constituents). Nodes could be referred to by their position in the grid, parents specifically can also be recorded by their direction.
Source Link
user555045
user555045
  • 10.7k
  • 1
  • 16
  • 32

Linear search through the whole heap

// find the node with the same data as child
auto it = std::find_if(opened.begin(), opened.end(), [&child](auto&& node) {
    return node->data == child;
});

This is a clear issue. It may seem like there is no way to avoid it, but there actually is. Unfortunately, it will mean having to re-implement the heap functions. The trick is this:

  • Maintain an unordered_map (or as secondary choice, map) from T to the index in the heap at which the node with a given data is located.
  • All heap-related functions must update the indices in that map when they move nodes. This is why they need to be re-implemented. It won't change their time complexity though.
  • "find node with the same data as child" can implemented as a lookup in the map.

"Re-parenting" a node changes its f score

*it = node; is not sufficient to update a node when a shortcut has been found to it. Its f score changed, that's why this is being done in the first place. Leaving it in same position may mean that it violates the heap property, which will have to be restored, otherwise future heap operations become unreliable.

Reachable unreachable code

The return in the end, return {}; // impossible to reach can be reached, namely when the goal is unreachable from the start and the amount of search space which is reachable from the start is finite.

Shared pointers

Nodes do not really need shared pointers to their parents, conceptually they do not own their parent after all, the parent pointers are just to say "go there to follow the path". What is really needed is these two things:

  • There must be some way to go from a node to its parent.
  • .. and that must be possible when the path finding is done, so the lifetime of this data must be until after the path has been traced.

That can be accomplished with shared pointers, but that has some disadvantages:

  • Creating nodes is non-trivial, requiring individual dynamic allocation.
  • Nodes have some additional, hidden, memory overhead (from being shared, and also from being individually allocated).
  • Getting rid of the nodes that still exist when the function returns is non-trivial.

There are various alternatives. For example (these can be combined/mixed to some extent):

  • All nodes could be owned by one big vector which is destroyed all in one go when the function returns (the destructor of Node can be trivial as long as T has a trivial destructor, then all the nodes in the vector just poof out of existence without ceremony). References to nodes can be replaced with indexes into that vector, or if you really want, you could still dynamically allocate the individual nodes and refer to them by non-owning pointer (except in the vector, which would own them with a unique pointer), but that negates some of the benefit of doing this.
  • The parent relationships could be recorded outside the nodes, in a map from T to T. This way the nodes are only needed as part of the Open set (the only thing needed from a closed node is its parent, but that isn't in the node anymore in this scheme), which could own them by value. This may be bad if T is a large type, because it creates a lot more Ts.
  • If the search space is a grid, temporary grids can be used to store the nodes (or its separate constituents). Nodes could be referred to by their position in the grid, parents specifically can also be recorded by their direction.