1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2004-2009 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
26 #include <algorithm>
27 #include <vector>
28 #include <climits>
29 #define _USE_MATH_DEFINES
30 #include <cmath>
32 #include "libavoid/vertices.h"
33 #include "libavoid/makepath.h"
34 #include "libavoid/geometry.h"
35 #include "libavoid/connector.h"
36 #include "libavoid/graph.h"
37 #include "libavoid/router.h"
38 #include "libavoid/debug.h"
39 #include "libavoid/assertions.h"
40 #ifdef ASTAR_DEBUG
41 #include <SDL_gfxPrimitives.h>
42 #endif
44 namespace Avoid {
46 class ANode
47 {
48 public:
49 VertInf* inf;
50 double g; // Gone
51 double h; // Heuristic
52 double f; // Formula f = g + h
54 int prevIndex; // Index into DONE for the previous ANode.
55 int timeStamp; // Timestamp used to determine explaration order of
56 // seemingly equal paths during orthogonal routing.
58 ANode(VertInf *vinf, int time)
59 : inf(vinf),
60 g(0),
61 h(0),
62 f(0),
63 prevIndex(-1),
64 timeStamp(time)
65 {
66 }
67 ANode()
68 : inf(NULL),
69 g(0),
70 h(0),
71 f(0),
72 prevIndex(-1),
73 timeStamp(-1)
74 {
75 }
76 };
79 // This returns the opposite result (>) so that when used with stl::make_heap,
80 // the head node of the heap will be the smallest value, rather than the
81 // largest. This saves us from having to sort the heap (and then reorder
82 // it back into a heap) when getting the next node to examine. This way we
83 // get better complexity -- logarithmic pushs and pops to the heap.
84 //
85 bool operator<(const ANode &a, const ANode &b)
86 {
87 if (a.f != b.f)
88 {
89 return a.f > b.f;
90 }
91 if (a.timeStamp != b.timeStamp)
92 {
93 // Tiebreaker, if two paths have equal cost, then choose the one with
94 // the highest timeStamp. This corresponds to the furthest point
95 // explored along the straight-line path. When exploring we give the
96 // directions the following timeStamps; left:1, right:2 and forward:3,
97 // then we always try to explore forward first.
98 return a.timeStamp < b.timeStamp;
99 }
100 COLA_ASSERT(a.prevIndex != b.prevIndex);
101 return a.prevIndex > b.prevIndex;
102 }
105 static double Dot(const Point& l, const Point& r)
106 {
107 return (l.x * r.x) + (l.y * r.y);
108 }
110 static double CrossLength(const Point& l, const Point& r)
111 {
112 return (l.x * r.y) - (l.y * r.x);
113 }
116 // Return the angle between the two line segments made by the
117 // points p1--p2 and p2--p3. Return value is in radians.
118 //
119 static double angleBetween(const Point& p1, const Point& p2, const Point& p3)
120 {
121 if ((p1.x == p2.x && p1.y == p2.y) || (p2.x == p3.x && p2.y == p3.y))
122 {
123 // If two of the points are the same, then we can't say anything
124 // about the angle between. Treat them as being collinear.
125 return M_PI;
126 }
128 Point v1(p1.x - p2.x, p1.y - p2.y);
129 Point v2(p3.x - p2.x, p3.y - p2.y);
131 return fabs(atan2(CrossLength(v1, v2), Dot(v1, v2)));
132 }
135 // Construct a temporary Polygon path given several VertInf's for a connector.
136 //
137 static void constructPolygonPath(Polygon& connRoute, VertInf *inf2,
138 VertInf *inf3, std::vector<ANode>& done, int inf1Index)
139 {
140 int routeSize = 2;
141 for (int curr = inf1Index; curr >= 0; curr = done[curr].prevIndex)
142 {
143 routeSize += 1;
144 }
145 connRoute.ps.resize(routeSize);
146 connRoute.ps[routeSize - 1] = inf3->point;
147 connRoute.ps[routeSize - 2] = inf2->point;
148 routeSize -= 3;
149 for (int curr = inf1Index; curr >= 0; curr = done[curr].prevIndex)
150 {
151 connRoute.ps[routeSize] = done[curr].inf->point;
152 routeSize -= 1;
153 }
154 }
157 // Given the two points for a new segment of a path (inf2 & inf3)
158 // as well as the distance between these points (dist), as well as
159 // possibly the previous point (inf1) [from inf1--inf2], return a
160 // cost associated with this route.
161 //
162 static double cost(ConnRef *lineRef, const double dist, VertInf *inf2,
163 VertInf *inf3, std::vector<ANode>& done, int inf1Index)
164 {
165 VertInf *inf1 = (inf1Index >= 0) ? done[inf1Index].inf : NULL;
166 double result = dist;
167 Polygon connRoute;
169 Router *router = inf2->_router;
170 if (inf1 != NULL)
171 {
172 const double angle_penalty = router->routingPenalty(anglePenalty);
173 const double segmt_penalty = router->routingPenalty(segmentPenalty);
175 // This is not the first segment, so there is a bend
176 // between it and the last one in the existing path.
177 if ((angle_penalty > 0) || (segmt_penalty > 0))
178 {
179 Point p1 = inf1->point;
180 Point p2 = inf2->point;
181 Point p3 = inf3->point;
183 double rad = M_PI - angleBetween(p1, p2, p3);
185 if (rad > 0)
186 {
187 // Make `xval' between 0--10 then take its log so small
188 // angles are not penalised as much as large ones.
189 //
190 double xval = rad * 10 / M_PI;
191 double yval = xval * log10(xval + 1) / 10.5;
192 result += (angle_penalty * yval);
193 //db_printf("deg from straight: %g\tpenalty: %g\n",
194 // rad * 180 / M_PI, (angle_penalty * yval));
195 }
197 if (rad == M_PI)
198 {
199 // Needs to double back
200 result += (2 * segmt_penalty);
201 }
202 else if (rad > 0)
203 {
204 // Only penalise as an extra segment if the two
205 // segments are not collinear.
206 result += segmt_penalty;
207 }
208 }
209 }
211 if (!router->_inCrossingPenaltyReroutingStage)
212 {
213 // Return here if we ar not in the postprocessing stage
214 return result;
215 }
217 const double cluster_crossing_penalty =
218 router->routingPenalty(clusterCrossingPenalty);
219 // XXX: Clustered routing doesn't yet work with orthogonal connectors.
220 if (router->ClusteredRouting && !router->clusterRefs.empty() &&
221 (cluster_crossing_penalty > 0) &&
222 (lineRef->routingType() != ConnType_Orthogonal))
223 {
224 if (connRoute.empty())
225 {
226 constructPolygonPath(connRoute, inf2, inf3, done, inf1Index);
227 }
228 // There are clusters so do cluster routing.
229 for (ClusterRefList::const_iterator cl = router->clusterRefs.begin();
230 cl != router->clusterRefs.end(); ++cl)
231 {
232 ReferencingPolygon& cBoundary = (*cl)->polygon();
233 COLA_ASSERT(cBoundary.ps[0] != cBoundary.ps[cBoundary.size() - 1]);
234 for (size_t j = 0; j < cBoundary.size(); ++j)
235 {
236 // Cluster boundary points should correspond to shape
237 // vertices and hence already be in the list of vertices.
238 COLA_ASSERT(router->vertices.getVertexByPos(cBoundary.at(j))!=NULL);
239 }
241 bool isConn = false;
242 Polygon dynamic_c_boundary(cBoundary);
243 Polygon dynamic_conn_route(connRoute);
244 const bool finalSegment = (inf3 == lineRef->dst());
245 CrossingsInfoPair crossings = countRealCrossings(
246 dynamic_c_boundary, isConn, dynamic_conn_route,
247 connRoute.size() - 1, true, finalSegment);
248 result += (crossings.first * cluster_crossing_penalty);
249 }
250 }
252 const double shared_path_penalty =
253 router->routingPenalty(fixedSharedPathPenalty);
254 if (shared_path_penalty > 0)
255 {
256 // Penalises shared paths, except if the connectors shared an endpoint.
257 if (connRoute.empty())
258 {
259 constructPolygonPath(connRoute, inf2, inf3, done, inf1Index);
260 }
261 ConnRefList::const_iterator curr, finish = router->connRefs.end();
262 for (curr = router->connRefs.begin(); curr != finish; ++curr)
263 {
264 ConnRef *connRef = *curr;
266 if (connRef->id() == lineRef->id())
267 {
268 continue;
269 }
270 const Avoid::PolyLine& route2 = connRef->route();
272 bool isConn = true;
273 Polygon dynamic_route2(route2);
274 Polygon dynamic_conn_route(connRoute);
275 CrossingsInfoPair crossings = countRealCrossings(
276 dynamic_route2, isConn, dynamic_conn_route,
277 connRoute.size() - 1, false, false, NULL, NULL,
278 connRef, lineRef);
280 if ((crossings.second & CROSSING_SHARES_PATH) &&
281 (crossings.second & CROSSING_SHARES_FIXED_SEGMENT) &&
282 !(crossings.second & CROSSING_SHARES_PATH_AT_END))
283 {
284 // Penalise unecessary shared paths in the middle of
285 // connectors.
286 result += shared_path_penalty;
287 }
288 }
289 }
291 const double crossing_penalty = router->routingPenalty(crossingPenalty);
292 if (lineRef->doesHateCrossings() && (crossing_penalty > 0))
293 {
294 if (connRoute.empty())
295 {
296 constructPolygonPath(connRoute, inf2, inf3, done, inf1Index);
297 }
298 ConnRefList::const_iterator curr, finish = router->connRefs.end();
299 for (curr = router->connRefs.begin(); curr != finish; ++curr)
300 {
301 ConnRef *connRef = *curr;
303 if (connRef->id() == lineRef->id())
304 {
305 continue;
306 }
307 const Avoid::PolyLine& route2 = connRef->route();
309 bool isConn = true;
310 Polygon dynamic_route2(route2);
311 Polygon dynamic_conn_route(connRoute);
312 CrossingsInfoPair crossings = countRealCrossings(
313 dynamic_route2, isConn, dynamic_conn_route,
314 connRoute.size() - 1, true);
315 result += (crossings.first * crossing_penalty);
316 }
317 }
319 return result;
320 }
323 static double estimatedCost(ConnRef *lineRef, const Point *last,
324 const Point& a, const Point& b)
325 {
326 if (lineRef->routingType() == ConnType_PolyLine)
327 {
328 return euclideanDist(a, b);
329 }
330 else // Orthogonal
331 {
332 // XXX: This currently just takes into account the compulsory
333 // bend but will have to be updated when port direction
334 // information is available.
335 int num_penalties = 0;
336 double xmove = b.x - a.x;
337 double ymove = b.y - a.y;
338 if (!last)
339 {
340 // Just two points.
341 if ((xmove != 0) && (ymove != 0))
342 {
343 num_penalties += 1;
344 }
345 }
346 else
347 {
348 // We have three points, so we know the direction of the
349 // previous segment.
350 double rad = M_PI - angleBetween(*last, a, b);
351 if (rad > (M_PI / 2))
352 {
353 // Target point is back in the direction of the first point,
354 // so at least two bends are required.
355 num_penalties += 2;
356 }
357 else if (rad > 0)
358 {
359 // To the side, so at least one bend.
360 num_penalties += 1;
361 }
362 }
363 double penalty = num_penalties *
364 lineRef->router()->routingPenalty(segmentPenalty);
366 return manhattanDist(a, b) + penalty;
367 }
368 }
371 class CmpVisEdgeRotation
372 {
373 public:
374 CmpVisEdgeRotation(const VertInf* lastPt)
375 : _lastPt(lastPt)
376 {
377 }
378 bool operator() (const EdgeInf* u, const EdgeInf* v) const
379 {
380 return u->rotationLessThan(_lastPt, v);
381 }
382 private:
383 const VertInf *_lastPt;
384 };
387 // Returns the best path from src to tar using the cost function.
388 //
389 // The path is worked out using the aStar algorithm, and is encoded via
390 // prevIndex values for each ANode which point back to the previous ANode's
391 // position in the DONE vector. At completion, this order is written into
392 // the pathNext links in each of the VerInfs along the path.
393 //
394 // The aStar STL code is based on public domain code available on the
395 // internet.
396 //
397 static void aStarPath(ConnRef *lineRef, VertInf *src, VertInf *tar,
398 VertInf *start)
399 {
400 bool isOrthogonal = (lineRef->routingType() == ConnType_Orthogonal);
402 double (*dist)(const Point& a, const Point& b) =
403 (isOrthogonal) ? manhattanDist : euclideanDist;
405 std::vector<ANode> PENDING; // STL Vectors chosen because of rapid
406 std::vector<ANode> DONE; // insertions/deletions at back,
407 ANode Node, BestNode; // Temporary Node and BestNode
408 bool bNodeFound = false; // Flag if node is found in container
409 int timestamp = 1;
411 if (start == NULL)
412 {
413 start = src;
414 }
416 Router *router = lineRef->router();
417 if (router->RubberBandRouting && (start != src))
418 {
419 COLA_ASSERT(router->IgnoreRegions == true);
421 const PolyLine& currRoute = lineRef->route();
422 VertInf *last = NULL;
423 int rIndx = 0;
424 while (last != start)
425 {
426 const Point& pnt = currRoute.at(rIndx);
427 bool isShape = (rIndx > 0);
428 VertID vID(pnt.id, isShape, pnt.vn);
430 #ifdef PATHDEBUG
431 db_printf("/// %d %d %d\n", pnt.id, (int) isShape, pnt.vn);
432 #endif
433 VertInf *curr = router->vertices.getVertexByID(vID);
434 COLA_ASSERT(curr != NULL);
436 Node = ANode(curr, timestamp++);
437 if (!last)
438 {
439 Node.g = 0;
440 Node.h = estimatedCost(lineRef, NULL, Node.inf->point,
441 tar->point);
442 Node.f = Node.g + Node.h;
443 }
444 else
445 {
446 double edgeDist = dist(BestNode.inf->point, curr->point);
448 Node.g = BestNode.g + cost(lineRef, edgeDist, BestNode.inf,
449 Node.inf, DONE, BestNode.prevIndex);
451 // Calculate the Heuristic.
452 Node.h = estimatedCost(lineRef, &(BestNode.inf->point),
453 Node.inf->point, tar->point);
455 // The A* formula
456 Node.f = Node.g + Node.h;
458 // Point parent to last BestNode (pushed onto DONE)
459 Node.prevIndex = DONE.size() - 1;
460 }
462 if (curr != start)
463 {
464 BestNode = Node;
466 DONE.push_back(BestNode);
467 }
468 else
469 {
470 PENDING.push_back(Node);
471 }
473 rIndx++;
474 last = curr;
475 }
476 }
477 else
478 {
479 // Create the start node
480 Node = ANode(src, timestamp++);
481 Node.g = 0;
482 Node.h = estimatedCost(lineRef, NULL, Node.inf->point, tar->point);
483 Node.f = Node.g + Node.h;
484 // Set a null parent, so cost function knows this is the first segment.
486 // Populate the PENDING container with the first location
487 PENDING.push_back(Node);
488 }
490 tar->pathNext = NULL;
492 // Create a heap from PENDING for sorting
493 using std::make_heap; using std::push_heap; using std::pop_heap;
494 make_heap( PENDING.begin(), PENDING.end() );
496 while (!PENDING.empty())
497 {
498 // Set the Node with lowest f value to BESTNODE.
499 // Since the ANode operator< is reversed, the head of the
500 // heap is the node with the lowest f value.
501 BestNode = PENDING.front();
503 // Pop off the heap. Actually this moves the
504 // far left value to the far right. The node
505 // is not actually removed since the pop is to
506 // the heap and not the container.
507 pop_heap(PENDING.begin(), PENDING.end());
508 // Remove node from right (the value we pop_heap'd)
509 PENDING.pop_back();
511 // Push the BestNode onto DONE
512 DONE.push_back(BestNode);
514 VertInf *prevInf = (BestNode.prevIndex >= 0) ?
515 DONE[BestNode.prevIndex].inf : NULL;
516 #if 0
517 db_printf("Considering... ");
518 db_printf(" %g %g ", BestNode.inf->point.x, BestNode.inf->point.y);
519 BestNode.inf->id.db_print();
520 db_printf(" - g: %3.1f h: %3.1f back: ", BestNode.g, BestNode.h);
521 if (prevInf)
522 {
523 db_printf(" %g %g", prevInf->point.x, prevInf->point.y);
524 //prevInf->id.db_print();
525 }
526 db_printf("\n");
527 #endif
529 #if defined(ASTAR_DEBUG)
530 if (router->avoid_screen)
531 {
532 int canx = 151;
533 int cany = 55;
534 int radius = 5;
535 ANode curr;
536 for (curr = BestNode; curr.prevIndex >= 0;
537 curr = DONE[curr.prevIndex])
538 {
539 filledCircleRGBA(router->avoid_screen,
540 (int) curr.inf->point.x + canx,
541 (int) curr.inf->point.y + cany,
542 radius, 0, 0, 255, 128);
543 }
544 filledCircleRGBA(router->avoid_screen,
545 (int) BestNode.inf->point.x + canx,
546 (int) BestNode.inf->point.y + cany,
547 radius, 255, 0, 0, 255);
549 SDL_Flip(router->avoid_screen);
550 //SDL_Delay(500);
552 filledCircleRGBA(router->avoid_screen,
553 (int) BestNode.inf->point.x + canx,
554 (int) BestNode.inf->point.y + cany,
555 radius, 255, 255, 255, 255);
556 filledCircleRGBA(router->avoid_screen,
557 (int) BestNode.inf->point.x + canx,
558 (int) BestNode.inf->point.y + cany,
559 radius, 0, 255, 0, 128);
560 for (curr = BestNode; curr.prevIndex >= 0;
561 curr = DONE[curr.prevIndex])
562 {
563 filledCircleRGBA(router->avoid_screen,
564 (int) curr.inf->point.x + canx,
565 (int) curr.inf->point.y + cany,
566 radius, 255, 255, 255, 255);
567 filledCircleRGBA(router->avoid_screen,
568 (int) curr.inf->point.x + canx,
569 (int) curr.inf->point.y + cany,
570 radius, 0, 255, 0, 128);
571 }
572 }
573 #endif
575 // If at destination, break and create path below
576 if (BestNode.inf == tar)
577 {
578 #ifdef PATHDEBUG
579 db_printf("Cost: %g\n", BestNode.f);
580 #endif
581 //bPathFound = true; // arrived at destination...
583 // Correct all the pathNext pointers.
584 ANode curr;
585 int currIndex = DONE.size() - 1;
586 for (curr = BestNode; curr.prevIndex > 0;
587 curr = DONE[curr.prevIndex])
588 {
589 COLA_ASSERT(curr.prevIndex < currIndex);
590 curr.inf->pathNext = DONE[curr.prevIndex].inf;
591 currIndex = curr.prevIndex;
592 }
593 // Check that we've gone through the complete path.
594 COLA_ASSERT(curr.prevIndex == 0);
595 // Fill in the final pathNext pointer.
596 curr.inf->pathNext = DONE[curr.prevIndex].inf;
598 break;
599 }
601 // Check adjacent points in graph
602 EdgeInfList& visList = (!isOrthogonal) ?
603 BestNode.inf->visList : BestNode.inf->orthogVisList;
604 if (isOrthogonal)
605 {
606 // We would like to explore in a structured way,
607 // so sort the points in the visList...
608 CmpVisEdgeRotation compare(prevInf);
609 visList.sort(compare);
610 }
611 EdgeInfList::const_iterator finish = visList.end();
612 for (EdgeInfList::const_iterator edge = visList.begin();
613 edge != finish; ++edge)
614 {
615 Node = ANode((*edge)->otherVert(BestNode.inf), timestamp++);
617 // Set the index to the previous ANode that we reached
618 // this ANode through (the last BestNode pushed onto DONE).
619 Node.prevIndex = DONE.size() - 1;
621 // Only check shape verticies, or the tar endpoint.
622 if (!(Node.inf->id.isShape) && (Node.inf != tar))
623 {
624 continue;
625 }
627 VertInf *prevInf = (BestNode.prevIndex >= 0) ?
628 DONE[BestNode.prevIndex].inf : NULL;
630 // Don't bother looking at the segment we just arrived along.
631 if (prevInf && (prevInf == Node.inf))
632 {
633 continue;
634 }
636 double edgeDist = (*edge)->getDist();
638 if (edgeDist == 0)
639 {
640 continue;
641 }
643 if (!router->_orthogonalRouting &&
644 (!router->RubberBandRouting || (start == src)) &&
645 (validateBendPoint(prevInf, BestNode.inf, Node.inf) == false))
646 {
647 // The bendpoint is not valid, i.e., is a zigzag corner, so...
648 continue;
649 // For RubberBand routing we want to allow these routes and
650 // unwind them later, otherwise instead or unwinding, paths
651 // can go the *really* long way round.
652 }
654 Node.g = BestNode.g + cost(lineRef, edgeDist, BestNode.inf,
655 Node.inf, DONE, BestNode.prevIndex);
657 // Calculate the Heuristic.
658 Node.h = estimatedCost(lineRef, &(BestNode.inf->point),
659 Node.inf->point, tar->point);
661 // The A* formula
662 Node.f = Node.g + Node.h;
664 #if 0
665 db_printf("-- Adding: %g %g ", Node.inf->point.x,
666 Node.inf->point.y);
667 Node.inf->id.db_print();
668 db_printf(" - g: %3.1f h: %3.1f \n", Node.g, Node.h);
669 #endif
671 bNodeFound = false;
673 // Check to see if already on PENDING
674 for (unsigned int i = 0; i < PENDING.size(); i++)
675 {
676 ANode& ati = PENDING.at(i);
677 if ((Node.inf == ati.inf) &&
678 (DONE[Node.prevIndex].inf == DONE[ati.prevIndex].inf))
679 {
680 // If already on PENDING
681 if (Node.g < ati.g)
682 {
683 PENDING[i] = Node;
685 make_heap( PENDING.begin(), PENDING.end() );
686 }
687 bNodeFound = true;
688 break;
689 }
690 }
691 if (!bNodeFound ) // If Node NOT found on PENDING
692 {
693 // Check to see if already on DONE
694 for (unsigned int i = 0; i < DONE.size(); i++)
695 {
696 ANode& ati = DONE.at(i);
697 if ((Node.inf == ati.inf) &&
698 (DONE[Node.prevIndex].inf == DONE[ati.prevIndex].inf))
699 {
700 // If on DONE, Which has lower gone?
701 if (Node.g < ati.g)
702 {
703 DONE[i] = Node;
704 }
705 bNodeFound = true;
706 break;
707 }
708 }
709 }
711 if (!bNodeFound ) // If Node NOT found on PENDING or DONE
712 {
713 // Push NewNode onto PENDING
714 PENDING.push_back(Node);
715 // Push NewNode onto heap
716 push_heap( PENDING.begin(), PENDING.end() );
718 #if 0
719 using std::cout; using std::endl;
720 // Display PENDING and DONE containers (For Debugging)
721 cout << "PENDING: ";
722 for (unsigned int i = 0; i < PENDING.size(); i++)
723 {
724 cout << PENDING.at(i).g << "," << PENDING.at(i).h << ",";
725 cout << PENDING.at(i).inf << "," << PENDING.at(i).pp << " ";
726 }
727 cout << endl;
728 cout << "DONE: ";
729 for (unsigned int i = 0; i < DONE.size(); i++)
730 {
731 cout << DONE.at(i).g << "," << DONE.at(i).h << ",";
732 cout << DONE.at(i).inf << "," << DONE.at(i).pp << " ";
733 }
734 cout << endl << endl;
735 #endif
736 }
737 }
738 }
739 }
742 // Returns the best path for the connector referred to by lineRef.
743 //
744 // The path encoded in the pathNext links in each of the VertInfs
745 // backwards along the path, from the tar back to the source.
746 //
747 void makePath(ConnRef *lineRef, bool *flag)
748 {
749 bool isOrthogonal = (lineRef->routingType() == ConnType_Orthogonal);
750 Router *router = lineRef->router();
751 VertInf *src = lineRef->src();
752 VertInf *tar = lineRef->dst();
753 VertInf *start = lineRef->start();
755 // TODO: Could be more efficient here.
756 if (isOrthogonal)
757 {
758 aStarPath(lineRef, src, tar, start);
759 }
760 else // if (!isOrthogonal)
761 {
762 EdgeInf *directEdge = EdgeInf::existingEdge(src, tar);
763 // If the connector hates crossings or there are clusters present,
764 // then we want to examine direct paths:
765 bool examineDirectPath = lineRef->doesHateCrossings() ||
766 !(router->clusterRefs.empty());
768 if ((start == src) && directEdge && (directEdge->getDist() > 0) &&
769 !examineDirectPath)
770 {
771 tar->pathNext = src;
772 directEdge->addConn(flag);
773 }
774 else
775 {
776 aStarPath(lineRef, src, tar, start);
777 }
778 }
780 #if 0
781 for (VertInf *t = vertices.connsBegin(); t != vertices.end();
782 t = t->lstNext)
783 {
784 t->id.db_print();
785 db_printf(" -> ");
786 t->pathNext->id.db_print();
787 db_printf("\n");
788 }
789 #endif
790 }
793 }