Graph::Easy - Manual

Layouter - A* (A-star)

If you haven't done so, please read the Overview first.

For a general overview of the A* algorithm please read Amit J. Patel's great page and then come back here.

The Good and The Bad Paths

The pathfinding algorithm has the goal to find a path between two nodes. It considers each starting port and each ending port and needs to return the best possible path. Here is a list of things that are considered good:

shorter paths are better than longer ones
the less bends a path has, the better
crossings are doubleplusungood

The best possible path goes straight and occupies only one cell.

Multi-celled Nodes

Consider the following two placed nodes with their appropriate ports:

...........................................
:     :     :     :     :     :     :     :
: 0,0 :North:North: 3,0 : 4,0 : 5,0 : 6,0 :
:     :     :     :     :     :     :     :
...........................................
:     :+---------+:     :     :     :     :
:West :|    A    |: East: 4,1 : 5,1 : 6,1 :
:     :+---------+:     :     :     :     :
...........................................
:     :     :     :     :     :     :     :
: 0,2 :South:South: 3,2 : 4,2 : 5,2 : 6,2 :
:     :     :     :     :     :     :     :
...........................................
:     :     :     :     :     :     :     :
: 0,3 : 1,3 : 2,3 : 3,3 : 4,3 : 5,3 : 6,3 :
:     :     :     :     :     :     :     :
...........................................
:     :     :     :     :     :     :     :
: 0,4 : 1,4 : 2,4 :North:North: 3,4 : 4,4 :
:     :     :     :     :     :     :     :
...........................................
:     :     :     :+---------+:     :     :
: 0,5 : 1,5 :West :|         |: East: 4,5 :
:     :     :     :|         |:     :     :
...................|    B    |.............
:     :     :     :|         |:     :     :
: 0,6 : 1,6 :West :|         |: East: 4,6 :
:     :     :     :+---------+:     :     :
...........................................
:     :     :     :     :     :     :     :
: 0,7 : 1,7 : 2,7 :South:South: 6,7 : 7,7 :
:     :     :     :     :     :     :     :
...........................................

There exist two optimal paths from A to B, one from 3,1 to 3,4 (colored yellow), and the other one from 2,2 to 2,5 (colored cyan). 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...

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

Multiple Startpoints

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.

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.
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.

Multiple Endpoints

Multiple endpoints are easily implemented, too. Instead of stopping the algorithm when we hit the endpoint, we watch for all of them simultanously.
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.

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

Crossings

The pathfinding will also find crossings. However, since edge crossings are considered 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.

Stopping

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.

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 into a cycle (which should not happen, but experience has shown that some bugs always creep in :)

To prevent the algorithm from spiraling out of control, we define a working space:

.............................
:                           :
:   +-------+               :
:   | Start | ------+       :
:   +-------+       |       :
:                   |       : 
:                   |       :
:                   v       :
:                 +------+  :
:                 | Dest |  :             
:                 +------+  :
:                           : 
.............................

The working space is the rectangle that encompasses all used cells at the start of the algorithm, plus one cell in each direction.
Since it is possible to reach any cell in the outer stripe from any other cell in the same region, the algorithm never needs to leave that working space to find a path. By confining the algorithm into this region (simple dropping all OPEN cells outside this area), we make sure that there is a finite number of cells to check and visit.
When A* runs out of cells to check (OPEN is empty), we know we have reached every possible location reachable from our start position(s), and if no stop position was among them, the target is not reachable at all. The pathfinding thus stops without a result, but after a small finite amount of steps.

A* Map

Below is a diagnostic output of the A* algorithm finding a path from a one-cell node to a 2x2 celled node, which has a few ports blocked. Empty cells are lightgrey, blocked darkgrey, and nodes are white. The lime to orange cells were still in the to-be-done phase when the algorithm finished, the purple-blue-teal fields were already considered while finding the path. The found path (clearly not optimal, since it has too many bends) is outlined in white.

Nodes examined: 168
Nodes still to do (open): 50
Nodes in path: 21

1+22

2+21

4+20

8+16

9+15

10+14

12+11

13+10

1+22

0+18

1+20

3+19

4+18

5+17

6+16

7+15

8+14

9+13

10+12

11+10

12+9

1+22

0+18

0+16

1+18

2+17

3+16

4+15

5+14

6+13

7+12

8+11

9+9

10+8

11+10

12+11

2+21

1+20

0+16

1+18

3+17

4+16

5+15

6+14

7+13

8+12

9+11

10+10

11+8

12+7

14+9

4+20

3+19

1+18

3+17

7+16

8+15

6+14

8+13

11+12

9+11

10+10

14+9

12+7

13+6

15+8

5+19

4+18

2+17

4+16

5+15

9+14

7+13

9+12

12+11

10+10

11+9

15+8

13+6

14+5

16+7

6+18

5+17

3+16

5+15

9+14

10+13

11+12

12+11

13+10

11+9

12+8

16+7

14+5

15+4

17+6

7+17

6+16

4+15

6+14

7+13

8+12

9+11

10+10

14+9

12+8

13+7

17+6

15+4

16+3

18+5

8+16

7+15

5+14

7+13

9+12

10+11

11+10

12+9

15+8

13+7

14+6

17+2

19+4

9+15

8+14

6+13

8+12

12+11

13+10

14+9

15+8

16+7

17+6

21+3

10+13

9+12

7+11

9+10

10+9

11+8

12+7

13+6

14+5

15+4

24+0

22+1

11+12

10+11

8+10

10+9

11+8

12+7

13+6

14+5

15+4

16+3

17+2

9+12

12+11

13+10

14+9

15+8

16+7

17+6

18+5

19+4

10+13