Index: plugins/rt_topo/crbs_route.c =================================================================== --- plugins/rt_topo/crbs_route.c (revision 1447) +++ plugins/rt_topo/crbs_route.c (revision 1448) @@ -176,13 +176,28 @@ } */ +/* toa must be an arc */ +static int crbs_is_spiral(usrch_a_star_t *ctx, grbs_detached_addr_t *froma, grbs_addr_t *toa) +{ + usrch_a_star_node_t *it; + grbs_detached_addr_t *da; + +#warning TODO: we should probably allow real spirals and deny only on the same orbit (some maze setup may have legit spiral) + + for(da = usrch_a_star_path_first_from(ctx, froma, &it); da != NULL; da = usrch_a_star_path_next(ctx, &it)) { + if (da->pt == toa->obj.arc->parent_pt) + return 1; + } +} + static int hop_cnt = 0; /* Attempt to create a grbs path segment from curr to pt:adir. If fails, return NULL. If succeeds, remove the path segment from the grbs context, add a detached address of it to the hash and return it. */ -static grbs_detached_addr_t *crbs_next_hop(crbs_t *crbs, grbs_detached_addr_t *curr, crbs_point_t *pt, grbs_arc_dir_t adir) +static grbs_detached_addr_t *crbs_next_hop(usrch_a_star_t *ctx, grbs_detached_addr_t *curr, crbs_point_t *pt, grbs_arc_dir_t adir) { + crbs_t *crbs = ctx->user_data; grbs_addr_t *froma, *toa; grbs_2net_t *gtn = crbs->routing_tn; grbs_detached_addr_t *res = NULL, dtmp[3]; @@ -241,6 +256,16 @@ } } + if ((adir == GRBS_ADIR_CONVEX_CCW) || (adir == GRBS_ADIR_CONVEX_CW)) { + if (crbs_is_spiral(ctx, curr, toa)) { + printf(" INVALID spiral: P%ld\n", froma->obj.arc->parent_pt == NULL ? -1 : froma->obj.arc->parent_pt->uid); + grbs_path_cleanup_addr(&crbs->grbs, toa); + grbs_path_cleanup_addr(&crbs->grbs, froma); + return NULL; + } + } + + grbs_detach_addr(&crbs->grbs, dtmp, toa); key = grbs_det_addr_to_key(dtmp); e = htad_getentry(&crbs->addrs, key); @@ -306,7 +331,7 @@ if (pt == crbs->target->pt->user_data) { /* quick lane for reaching the target */ if (crbs_trace_ast) printf(" try from %s P%ld to TARGET P%ld", from_type, curr->pt->uid, pt->gpt->uid); - next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_INC); + next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_INC); if (next != NULL) { a->pt_idx = a->pts.used; /* don't consider detours from the current node if target node can be reached directly */ if (crbs_trace_ast) printf(" -> ok\n"); @@ -339,11 +364,11 @@ /* prefer concave over convex; order matters when reaching target: first valid solution will stop the search */ switch(a->grbs_idx) { - case 0: if (crbs_trace_ast) printf(" concave ccw"); next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_CONCAVE_CCW); break; - case 1: if (crbs_trace_ast) printf(" concave cw"); next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_CONCAVE_CW); break; - case 2: if (crbs_trace_ast) printf(" vconcave"); next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_VCONCAVE); break; - case 3: if (crbs_trace_ast) printf(" convex ccw"); next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_CONVEX_CCW); break; - case 4: if (crbs_trace_ast) printf(" convex cw"); next = crbs_next_hop(crbs, curr, pt, GRBS_ADIR_CONVEX_CW); break; + case 0: if (crbs_trace_ast) printf(" concave ccw"); next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_CONCAVE_CCW); break; + case 1: if (crbs_trace_ast) printf(" concave cw"); next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_CONCAVE_CW); break; + case 2: if (crbs_trace_ast) printf(" vconcave"); next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_VCONCAVE); break; + case 3: if (crbs_trace_ast) printf(" convex ccw"); next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_CONVEX_CCW); break; + case 4: if (crbs_trace_ast) printf(" convex cw"); next = crbs_next_hop(ctx, curr, pt, GRBS_ADIR_CONVEX_CW); break; } a->grbs_idx++;