view release on metacpan or  search on metacpan

doc/manual/a-star.html  view on Meta::CPAN

There exist two optimal paths from A to B, one from 3,1 to 3,4 (colored <span class="port2">yellow</span>),
and the other one from 2,2 to 2,5 (colored <span class="port3">cyan</span>). However,
this holds only if there are no obstacles along these paths. With obstacles, every combination
of each starting port and each ending port would need to be examined. This are 2+1+2+1=6 x 2+2+2+2=8 == 48
possible simple paths. Clearly just trying each of them would not scale very well. Just consider
what happens if you have two nodes, each with 20 ports...
</p>

<p>
One of the strengths of the general A* algorithm is that it supports with ease
multiple start- and endpoints.
</p>

<h4>Multiple Startpoints</h4>

<p>
Multiple start points are very easy to implement, instead of adding a single start point to
the list of OPEN nodes, we add all possible starting points. We also apply a very small
tie-breaker so that the algorithm favours a certain direction in case of ties.
</p>

<p>
In the example above, the algorithm would explore both equally likely paths at the
same time, choosing the one that hits (arbitrarily) one end port first.
<br>
With the tie-breaker, it will follow only one of the paths (f.i. East, then South),
until it either hits the endpoint, or finds an obstacle.
</p>

<h4>Multiple Endpoints</h4>

<p>
Multiple endpoints are easily implemented, too. Instead of stopping the algorithm
when we hit <i>the</i> endpoint, we watch for all of them simultanously.
<br>
In addition, instead of calculating the distance from the current node to the
endpoint, we calculate the distance to each endpoint, and then use the smallest
one.
</p>

<p>
Thus the algorithm will automatically gravitate towards the nearest port, but
still work around obstacles just fine.
</p>

<h4>Crossings</h4>

doc/manual/a-star.html  view on Meta::CPAN

bad, each crossing bears a heavy penalty. The penalty is so high that if a possible
path around the edge without a crossing exists, it will be found. However, the penalty
is not so high as that the algorithm searches endless for a way around that does not
exist.
</p>

<a name="terminating"></a>
<h4>Stopping</h4>

<p>
The algorithm will stop when it reaches one of the possible endpoints. However, if
the path to the goal is blocked on all sides, it will run into trouble. The reason
is that our layout plane is essential infinitely big, and the algorithm would
spiral outwards and out of control, never finishing.
</p>

<p>
To protect against run-away situations (occuring mainly due to bugs),
the algorithm stops after a hard-coded number of steps. This is
currently set to 10,000 steps as to not interfere with normal
working conditions, and yet stop the algorithm if it runs

doc/manual/features.html  view on Meta::CPAN

  +------+
  v      |
+----------+
| Chemnitz |
+----------+
</pre>

<p class="clear">&nbsp;</p>

<a name="edges">
<h3>Edge-parts as endpoint of another edges</h3>
</a>

<p>
Sometimes you want to point an edge towards the label of another edge.
Since tradionally edges can only connect nodes with other nodes,
Graph::Easy features nodes with a shape of <code>edge</code>, these
nodes will fit seamless into an edge and thus create the illusion that
you point the edge at the label of another edge:
</p>