void icon indicating copy to clipboard operation
void copied to clipboard

Overhaul arrow pathfinding

Open alch-emi opened this issue 3 years ago • 0 comments

Currently, arrow pathfinding works using the following algorithm:

  • for each possible starting point (typically = 2)
    • for each possible ending point (1 for a point, 2 for a node)
      • run a greedy search from the start to the end
  • pick the fastest path

This algorithm often creates arrows that are way squigglier and hard to follow than they really need to be. Additionally, it often does four times more work than it needs to, because it runs once for every combination of start and end points.

This PR replaces the greedy search algorithm with a slightly more expensive A* algorithm, while also using an algorithm that allows automatically picking the best path from one of a number of start points to one of a number of end points, eliminating the need to run the algorithm more than once.

By using an A* algorithm, we also gain more control over the pathfinding, by the use of weights. This PR takes advantage of this fact to improve arrow generation in the following ways:

  • Making more turns than necessary is discouraged, decreasing line squigle factor (cost +1 / turn)
  • Pointing in the direction of the end arrow is encouraged (cost +5 if ending in the wrong direction, see 69241df)

This also opens the door for future work in order to discourage arrows from overlapping for long distances, but that's left to another PR.

Before

image

After

image

alch-emi avatar Jun 30 '22 16:06 alch-emi