get_route.cc 7.02 KB
Newer Older
Jean-Benoist Leger's avatar
Jean-Benoist Leger committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
#include "get_route.h"

std::list<std::list<route_point_t> > get_routes(
        route_db_t* route_db,
        parameters_t & parameters,
        std::list< std::pair<double,double> > & geos)
{
    std::list<nid_t> nids;
    route_db->lookup(geos, nids);

    std::list<std::list<route_point_t> > ret;

    for(std::list<nid_t>::iterator nids_it = nids.begin();
            nids_it != nids.end();
            nids_it++)
    {
        std::list<nid_t>::iterator nids_it_next = nids_it;
        nids_it_next++;
        if(nids_it_next!=nids.end())
        {
            ret.push_back(
                    get_route_between_nids(
                        route_db,
                        parameters,
                        *nids_it,
                        *nids_it_next));
        }
    }
    return(ret);
}


std::list<route_point_t> get_route_between_nids(
        route_db_t* route_db,
        parameters_t & parameters,
        nid_t & nid_initial,
        nid_t & nid_final)
{
    std::priority_queue<edge_in_queue_t> queue; // This is the ordoned queue used to explore
    edge_map_t edges_map;


    // first we add edge starting from the initial node in the queue
    node_info_t* initial_node = route_db->get_node(nid_initial);
    node_info_t* final_node = route_db->get_node(nid_final);

    edge_t null_edge;
    null_edge.A = 0;
    null_edge.B = 0;
    for(unsigned int i=0; i< initial_node->fixed->neighbors_number; i++)
    {
        edge_t edge;
        edge.A=nid_initial;
        edge.B=initial_node->neighbors[i].to;
        status_t & status = edges_map[edge];
        status.criterion=0;
        status.velocity=0;
        status.energy=0;
        status.time=0;
Jean-Benoist Leger's avatar
update  
Jean-Benoist Leger committed
60
        status.power=0;
Jean-Benoist Leger's avatar
Jean-Benoist Leger committed
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
        status.walk=false;
        status.from_edge=null_edge;
        status.freezed=false;
        status.initialized=true;
        edge_in_queue_t edge_in_queue;
        edge_in_queue.edge = edge;
        edge_in_queue.heuristic = rv_heuristic(parameters, initial_node->fixed, final_node->fixed, status);
        queue.push(edge_in_queue);
    }

    while(!queue.empty())
    {
        // We take the first
        edge_in_queue_t running_edge_in_queue = queue.top();
        queue.pop();

        status_t & running_status = edges_map[running_edge_in_queue.edge];

        if(running_status.freezed) // We have already foud the optimal for this edge
        {
            continue;
        }

        running_status.freezed = true;
       
        
        if(running_edge_in_queue.edge.A == nid_final) // It is finish
            break;

        node_info_t* A_node = route_db->get_node(running_edge_in_queue.edge.A);
        node_info_t* B_node = route_db->get_node(running_edge_in_queue.edge.B);


        if(running_edge_in_queue.edge.B == nid_final) // We are near the end
        {
            edge_in_queue_t following_edge_in_queue;
            following_edge_in_queue.edge.A = nid_final;
            following_edge_in_queue.edge.B = 0;
            status_t & following_status = edges_map[following_edge_in_queue.edge];
            status_t proposed_following_status;

            // We lookup the way_kind
            way_kind_t way_kind;
            for(unsigned int i=0;i<B_node->fixed->neighbors_number; i++)
            {
                if(B_node->neighbors[i].from == running_edge_in_queue.edge.A)
                {
                    way_kind = B_node->neighbors[i].way_kind;
                    break;
                }
            }

            rv_step(
                    parameters,
                    A_node->fixed,
                    B_node->fixed,
                    NULL,
                    way_kind,
                    running_status,
                    proposed_following_status);

            if(!following_status.initialized 
                    || proposed_following_status.criterion < following_status.criterion)
            {
                following_status = proposed_following_status;
                following_status.from_edge=running_edge_in_queue.edge;
                following_status.initialized=true;
                following_edge_in_queue.heuristic = rv_heuristic(
                        parameters,
                        B_node->fixed,
                        final_node->fixed,
                        following_status);
                queue.push(following_edge_in_queue);
            }
            continue;
        }

        for(unsigned int i=0; i<B_node->fixed->neighbors_number; i++)
        {
            if(B_node->neighbors[i].from == running_edge_in_queue.edge.A)
            {
                // We explore the following
                nid_t & nid_C = B_node->neighbors[i].to;
                if(!nid_C) // This is a dead end and we are not at the end
                    continue;
                way_kind_t & way_kind = B_node->neighbors[i].way_kind;

                node_info_t* C_node = route_db->get_node(nid_C);

                edge_in_queue_t following_edge_in_queue;
                following_edge_in_queue.edge.A = running_edge_in_queue.edge.B;
                following_edge_in_queue.edge.B = nid_C;
                status_t proposed_following_status;
                status_t & following_status = edges_map[following_edge_in_queue.edge];

                rv_step(
                        parameters,
                        A_node->fixed,
                        B_node->fixed,
                        C_node->fixed,
                        way_kind,
                        running_status,
                        proposed_following_status);

                if(!following_status.freezed
                        && ( !following_status.initialized 
                            || proposed_following_status.criterion < following_status.criterion))
                {
                    following_status = proposed_following_status;
                    following_status.from_edge=running_edge_in_queue.edge;
                    following_status.initialized=true;
                    following_edge_in_queue.heuristic = rv_heuristic(
                            parameters,
                            B_node->fixed,
                            final_node->fixed,
                            following_status);
                    queue.push(following_edge_in_queue);
                }
            }
        }
    }

    edge_t edge;
    edge.A = nid_final;
    edge.B =0;

    status_t status = edges_map[edge];
    if(!status.freezed) // FUCK YOU
    {
        fprintf(stderr,"Queue finished with last edge not freezed\n");
        abort();
    }

    // We only have to follow the edges in opposite order
    std::list<route_point_t> ret;
    while(true)
    {
        route_point_t routing_point;
        routing_point.nid = edge.A;
        routing_point.velocity = status.velocity;
        routing_point.distance = status.distance;
        routing_point.energy = status.energy;
        routing_point.time = status.time;
        routing_point.walk = status.walk;
Jean-Benoist Leger's avatar
update  
Jean-Benoist Leger committed
205
        routing_point.power = status.power;
Jean-Benoist Leger's avatar
Jean-Benoist Leger committed
206 207 208 209 210 211 212 213 214 215 216 217
        ret.push_front(routing_point);

        if(edge.A == nid_initial)
            break;

        edge = status.from_edge;
        status = edges_map[edge];
    }

    return(ret);
}