User Provided Node

[heavenfall]

Current search_node for holds the fields as follows:

pad_id id_;
pad_id parent_id_;
cost_t g_;
cost_t f_;
cost_t ub_;
uint8_t status_;    // open or closed
uint32_t priority_; // expansion priority
uint32_t search_number_;
static uint32_t refcount_;

It uses getters/setters to refer to these data types and is the class in use for basic search and memory pool like node_pool.

I propose allowing the user to propose the use of their own nodes.
This proposal aligns with #22 and #6 issues, in that we will need a flexible memory allocator, and allowing custom nodes will help with the graph section of warthog.

The allocators (or factory) have great progress over in inxlib.

The following posts will be some proposals.

[heavenfall]

Issues to consider:

• Classes receiving node will expect certain variables or methods to retrieve value of the node.
• Similar classes or even multiple of the same class may share a node (i.e. two searches). They might share some values (like h-value) but need their own (like g-value).
• Nodes may need certain initialisation. A rolling init may be shared among classes, but call the same reset function.

Updating the node could follow several patterns:

• Direct access to variables (or member variable pointer)
• Getter/Setter functions
• lvalue references
• Utility functions
• A mixture of many

[heavenfall]

Proposal 1:

Using argument-dependent lookup, function getters/setters/methods can be used for easy default methods, with easy overridable to user node/algorithm. Example setup below:

namespace node {
struct node_base {}; // for ADL
auto wn_get_id(auto& alg[[maybe_unused]], const auto& n)
{ return n.id; }
void wn_set_id(auto& alg[[maybe_unused]], auto& n, auto value)
{ n.id = value; }
}
struct search_node : node::node_base
{
    pad_id id;
}

namespace derived {
struct derived_node : node::node_base
{
    point id;
};
void wn_set_id(auto& alg[[maybe_unused]], derived_node& n, point value)
{ n.id = point(value.x+1, value.y+1); }
void wn_set_id(auto& alg, derived_node& n, pad_id value)
{
    uint32_t width = alg.get_map()->get_width();
    n.id = point(value.id % width, value.id / width); }
}

In this method, the user can provide their own functions to change behaviour of some of the getters. It is easy to do but knowledge on C++ ADL and template overload resolution will help.

The algorithm is provided as both a way to get access to a global state for nodes (such as a rolling reset), or a way for a user to differentiate between which value to return, such as separate f-values for two different searches. The latter could be done using a tagging system too.

Proposal 2:

Similar to 1, but can use class template specialisation, or an option to look into a traits class.