Tilemap Path Finding ( a* ) (beta)

Arcade
33

Hi Joey!
I am so happy that you are satisfied with these changes! Thanks!
And I am very glad to explain the reason about costs, or even any more details if you are interested.

about costs changes:

  • cost of Heuristic (I guess you mean this):
    according to a* algorithm, it should be the short distance from current spot to target. In real map, we estimate the distance with the length of a streight line from current spot to target, there are no other choice(say no pre-data of routes). In our tilemap, particularly, walking direction are limited(8), so the length of possible shortest path connecting these 2 spot would like:
    image

So we got:

   costHeuristic = shortest path length
   = LengthOfLongerSide - LengthOfShortSide + LengthOfShortSide * 1.414
   = LengthOfLongerSide + LengthOfShortSide * 0.414

Then, to avoid float multi calculation, scale all costs up by 1000:
=LengthOfLongerSide * 1000 + LengthOfShortSide * 414

  • BTW, for cost calculation of each step:
        const neighborCost = currLocation.cost + 1000;
        const cornerCost = currLocation.cost + 1414
  • total cost = cost/factorOfWeight + costHeuristic
    the factorOfWeight make cost more important than the costHeuristic. It’s a experimental number relative to the number and shape of paths on the map, 10 or more can all make it faster about 50%.
  • the comparator of the Heap , I changed to: (a.cost + a.extraCost) - (b.cost + b.extraCost) ,
    from (a.cost ** 2 + a.extraCost) - (b.cost ** 2 + b.extraCost) , cause I thought this is just a typo when the commit “avoid sqrt …”, correct me please if not.

Waiting for your review for above, and then I will create a PR, if all of these are OK for you.
Feel free to ask me please, if there is anything I didn’t explain clearly(sorry for my poor english) or any thing you are interesting.

2 Likes