Slic3r::astar Namespace Reference

Classes
struct	QNode
struct	TracerTraits_

Typedefs
template<class T >
using	remove_cvref_t = std::remove_cv_t< std::remove_reference_t< T > >
template<class T >
using	TracerNodeT = typename TracerTraits_< remove_cvref_t< T > >::Node

Functions
template<class Tracer , class It , class NodeMap = std::unordered_map<size_t, QNode<Tracer>>>
bool	search_route (const Tracer &tracer, const TracerNodeT< Tracer > &source, It out, NodeMap &&cached_nodes={})

Variables
constexpr auto	Unassigned = std::numeric_limits<size_t>::max()

Typedef Documentation

remove_cvref_t

template<class T >

using Slic3r::astar::remove_cvref_t = typedef std::remove_cv_t<std::remove_reference_t<T> >

TracerNodeT

template<class T >

using Slic3r::astar::TracerNodeT = typedef typename TracerTraits_<remove_cvref_t<T> >::Node

Function Documentation

search_route()

template<class Tracer , class It , class NodeMap = std::unordered_map<size_t, QNode<Tracer>>>

bool Slic3r::astar::search_route	(	const Tracer &	tracer,
		const TracerNodeT< Tracer > &	source,
		It	out,
		NodeMap &&	cached_nodes = {}
	)

                                                            {})
{
    using Node         = TracerNodeT<Tracer>;
    using QNode        = QNode<Tracer>;
    using TracerTraits = TracerTraits_<remove_cvref_t<Tracer>>;
 
    struct LessPred { // Comparison functor needed by the priority queue
        NodeMap &m;
        bool operator ()(size_t node_a, size_t node_b) {
            return m[node_a].f() < m[node_b].f();
        }
    };
 
    auto qopen = make_mutable_priority_queue<size_t, true>(
        [&cached_nodes](size_t el, size_t qidx) {
            cached_nodes[el].queue_id = qidx;
        },
        LessPred{cached_nodes});
 
    QNode initial{source, /*parent = */ Unassigned, /*g = */0.f};
    size_t source_id = TracerTraits::unique_id(tracer, source);
    cached_nodes[source_id] = initial;
    qopen.push(source_id);
 
    size_t goal_id = TracerTraits::goal_heuristic(tracer, source) < 0.f ?
                         source_id :
                         Unassigned;
 
    while (goal_id == Unassigned && !qopen.empty()) {
        size_t q_id = qopen.top();
        qopen.pop();
        QNode &q = cached_nodes[q_id];
 
        // This should absolutely be initialized in the cache already
        assert(!std::isinf(q.g));
 
        TracerTraits::foreach_reachable(tracer, q.node, [&](const Node &succ_nd) {
            if (goal_id != Unassigned)
                return true;
 
            float  h       = TracerTraits::goal_heuristic(tracer, succ_nd);
            float  dst     = TracerTraits::distance(tracer, q.node, succ_nd);
            size_t succ_id = TracerTraits::unique_id(tracer, succ_nd);
            QNode  qsucc_nd{succ_nd, q_id, q.g + dst, h};
 
            if (h < 0.f) {
                goal_id = succ_id;
                cached_nodes[succ_id] = qsucc_nd;
            } else {
                // If succ_id is not in cache, it gets created with g = infinity
                QNode &prev_nd = cached_nodes[succ_id];
 
                if (qsucc_nd.g < prev_nd.g) {
                    // new route is better, apply it:
 
                    // Save the old queue id, it would be lost after the next line
                    size_t queue_id = prev_nd.queue_id;
 
                    // The cache needs to be updated either way
                    prev_nd = qsucc_nd;
 
                    if (queue_id == InvalidQueueID)
                        // was in closed or unqueued, rescheduling
                        qopen.push(succ_id);
                    else // was in open, updating
                        qopen.update(queue_id);
                }
            }
 
            return goal_id != Unassigned;
        });
    }
 
    // Write the output, do not reverse. Clients can do so if they need to.
    if (goal_id != Unassigned) {
        const QNode *q = &cached_nodes[goal_id];
        while (q->parent != Unassigned) {
            assert(!std::isinf(q->g)); // Uninitialized nodes are NOT allowed
 
            *out = q->node;
            ++out;
            q = &cached_nodes[q->parent];
        }
    }
 
    return goal_id != Unassigned;
}

Variable Documentation

Unassigned

constexpr auto Slic3r::astar::Unassigned = std::numeric_limits<size_t>::max()

constexpr