#include "map.h"
#include "graph.h"
-static uint bidir;
+static uint bidir; // 0=unidir, 1=bidir balanced by #opened, 2=bidir balanced by distance
static uint astar;
static struct cf_section graph_cf = {
v_dest->state[1] = 1;
v_dest->dist[1] = 0;
- uint open[2] = { 1, 1 };
+ uint opened[2] = { 1, 1 }, closed[2] = { 0, 0 };
+ double last_dist[2] = { 0, 0 };
struct graph_vertex *w;
for (;;)
{
double best_d = 0;
- uint dir = (open[0] <= open[1]) ? 0 : 1;
+ uint dir;
+ if (bidir == 2)
+ dir = (last_dist[0] <= last_dist[1]) ? 0 : 1;
+ else
+ dir = (opened[0] <= opened[1]) ? 0 : 1;
w = NULL;
- msg(L_DEBUG, "Dijkstra: dir=%d", dir);
+ // msg(L_DEBUG, "Dijkstra: dir=%d", dir);
CLIST_FOR_EACH(struct graph_vertex *, v, graph_vertices)
{
if (!w)
die("Path not found");
- msg(L_DEBUG, "Dijkstra: closing vertex #%jd (d=%f, dir %d)", w->node->o.id, best_d, dir);
+ // msg(L_DEBUG, "Dijkstra: closing vertex #%jd (d=%f, dir %d)", w->node->o.id, best_d, dir);
+ closed[dir]++;
+ last_dist[dir] = best_d;
w->state[dir] = 2;
if (w->state[!dir] == 2)
{
struct graph_vertex *x = e->dest;
double d = w->dist[dir] + e->length;
- msg(L_DEBUG, "Neighbor: #%jd, state=%d, dist=%f vs. %f", x->node->o.id, x->state[dir], x->dist[dir], d);
+ // msg(L_DEBUG, "Neighbor: #%jd, state=%d, dist=%f vs. %f", x->node->o.id, x->state[dir], x->dist[dir], d);
if (x->state[dir] == 0 || x->dist[dir] > d)
{
if (x->state[dir] == 2)
x->state[dir] = 1;
x->dist[dir] = d;
x->via_edge[dir] = e;
- open[dir]++;
+ opened[dir]++;
}
}
}
w = ev;
}
+ msg(L_DEBUG, "Dijkstra: Stats: %u/%u opened, %u/%u closed", opened[0], opened[1], closed[0], closed[1]);
visualize_states(v_src, v_dest);
visualize_path(w, 0);
visualize_path(w, 1);
v_src->state[0] = 1;
v_src->dist[0] = 0;
+ uint opened = 1, closed = 0;
+ struct graph_vertex *w;
+
for (;;)
{
- struct graph_vertex *w = NULL;
double best_d = 0;
+ w = NULL;
CLIST_FOR_EACH(struct graph_vertex *, v, graph_vertices)
if (v->state[0] == 1)
die("Path not found");
// msg(L_DEBUG, "Dijkstra: closing vertex #%jd", w->node->o.id);
+ closed++;
if (w == v_dest)
- {
- msg(L_INFO, "Found path: dist=%f", w->dist[0]);
- visualize_states(v_src, v_dest);
- visualize_path(v_dest, 0);
- return;
- }
+ break;
w->state[0] = 2;
CLIST_FOR_EACH(struct graph_edge *, e, w->edges)
x->state[0] = 1;
x->dist[0] = d;
x->via_edge[0] = e;
+ opened++;
}
}
}
+
+ msg(L_INFO, "Dijkstra: Found path: dist=%f", w->dist[0]);
+ msg(L_INFO, "Dijkstra: Stats: %u opened, %u closed", opened, closed);
+ visualize_states(v_src, v_dest);
+ visualize_path(v_dest, 0);
}
void graph_build(void)
struct graph_vertex *v1 = graph_vertex_by_node_id(96745573); // Beroun, Lidická x Pražská
// struct graph_vertex *v2 = graph_vertex_by_node_id(21289321); // Brno, Heršpická x Opuštěná
// struct graph_vertex *v2 = graph_vertex_by_node_id(271385400); // Znojmo, Vídeňská třída x Brněnská
- // struct graph_vertex *v2 = graph_vertex_by_node_id(26753344); // Šumperk, Jesenická x Lidická
- struct graph_vertex *v2 = graph_vertex_by_node_id(714908910); // Ostrava, Mariánskohorská x Plzeňská x 28. října
+ struct graph_vertex *v2 = graph_vertex_by_node_id(26753344); // Šumperk, Jesenická x Lidická
+ // struct graph_vertex *v2 = graph_vertex_by_node_id(714908910); // Ostrava, Mariánskohorská x Plzeňská x 28. října
ASSERT(graph_degree(v1) && graph_degree(v2));
if (bidir)