Abstract

This paper discusses an approach to automatically generate edges that represent transitions between fixed, user-created states in a hierarchical state diagram with emphasis on aesthetics and clarity. For this purpose, we applied the graph search algorithm A* to a generated grid that uses distance fields as well as different weights and prioritizations for crossing edges and states to calculate different path costs. The results are very promising, and there is a need for further research into post-processing and the avoidance of unwanted edge bending.

Aesthetic Criteria

For our approach, we prioritized the following criteria:

1. Edges should not come too close to state nodes to which they do not belong.
2. The number of crossings and overlaps should be as small as possible.
3. Edges should not use unnecessary paths (e.g. into and out of dead ends) and should not move too far from the direct path.
4. Edge lengths should not become unnecessary long.

Results/Implementation

Because of our distance field, edges do not come too close to state nodes to which they do not belong. This can be altered by changing the distance field’s size or by modifying the additional distance field cost. 

The number of crossing and overlaps is kept as small as possible, as this involves high costs. Of course, this cannot be completely prevented, as this would require dislocation of nodes, but the cost can be adjusted as desired to prevent all unnecessary intersections, whether it is states or edges.

By using the A* algorithm, we can guarantee that it will find a shortest path if the heuristic function outputs equal or lower numbers than the actual cost of moving from one grid point to another. Hence, edges do not use unnecessary paths (e.g. into and out of dead ends) and do not move too far from the direct path. 

Furthermore, by using the A* algorithm, edge lengths should not become unnecessary long.

Conclusion

The approach presented in this paper delivers useful results. It respects all the rules and aesthetic criteria we have established and quickly computes the edges during runtime. Further research needs to be done to avoid unwanted bends. Various post-processing methods could be explored to obtain even better edges. Even curved edges using Bezier would be possible.

In terms of performance our approach delivers good results. Nevertheless, further optimizations should be done for bigger grids or other grid representations should be used.

Paper

Final presentation