Patfinding, when everything else is equal

Algo Creation
1

image

image
image760×753 22.8 KB

In the above scenario, there are 3 paths with

  • [1] equal lenghts,
  • [2] all follow the change direction rule
  • [4] all take oposite from the target direction
    the only difference is, how early will you take the uncomfortable back turn.

terminal implementation takes the first option, (green)
my current logic takes the latest (further along the path) option.

I thing there is a missing rule, what to do if you only have uncomfortable turns

  1. Choose the tile which is the shortest number of steps…
  2. If multiple tiles are equally close to the units destination, move in the opposite direction…
  3. In the case where a Unit has just been deployed …
  4. If there are two tiles with equal distances and are equally prefered based on direction, the unit will choose one that is in the direction of it’s target edge. For example, if a unit wants to reach the top-right edge, and must choose between moving left and right, if both tiles have the same minimum number of steps it will move right.
2

At location (21, 9) you can go either up or left and it will be same distance to destination and because previous move was horizontal (from (22, 9) to (21, 9)) now you should prioritize up direction.

2 Likes
3

A* pathfinding is going to choose the first detour as its building the shortest routes close to the straight line starting from the beginning I think?

4

Everything is working as intended, as noted by paprikadobi:

This is correct, couldn’t have said it better myself

The logic of terminals pathfinding should be ‘rules based’ and not implementation dependent. See the rules & docs for more info.