Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Performance considerations with Tile-Based Path Finding - any Ideas/Tipps?

Discussion in 'Scripting' started by HenryChinaski, Feb 2, 2019.

  1. HenryChinaski

    HenryChinaski

    Joined:
    Jul 9, 2013
    Posts:
    108
    Hey guys,

    I am programming a Pathfinding System for a simple Tile-Based game. I am facing heavy performance problems with my code to find a path from the start to the target tile, so I am asking myself if this is caused by the way I am handling it or actually by missing computation power (my CPU is pretty good).

    I will keep it simple and short:
    The tiles are set up like this but eventually will become more complex:


    My idea was to just check all the neighbouring tiles of the start tile and then all their neighbouring tiles, and so on, until I find the target tile. Each branch gets the distance assigned it took to reach the target and finally the fastest one of them is chosen. Branches, where the target was found, are skipped further on. In code something like:

    Code (CSharp):
    1. foreach (Neighbour1 in StartTile)
    2. {
    3. if  (Neighbour1 == target) AddPath to list, continue with next neighbour
    4. else
    5. {
    6. foreach (Neighbour2 in Neighbour1)
    7. {
    8. if (Neighbour2 == target) Add Path to list, continue with next neighbour
    9. else
    10. {
    11. ......And so on.......
    12. }
    13. }
    14. }
    15. }
    This construction of code leads to a 1-second delay whenever it is executed. I know that there are complex algorithms and much more sophisticated ways of doing this. My question is simply: is the problem just my code specifically or my general approach itself?

    Hope someone has a tip and everything is understandable.
     
  2. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    You're effectively searching ALL possible paths and then picking the shortest. This is like the most ineffective pathfinding algorithm.

    A* is the usual go to node based pathing algorithm (your tile map is a node based, where each tile is a node).

    There's tons of implementations of A* out there, packages you can get for Unity, or even examples of how to roll your own in Unity.

    Here is my personal self-rolled version:
    https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs
    (note - you can ignore the code in the region called ISteppingResolver Interface... it's just an alternate version used for spreading a calculation over multiple frames if threading isn't a possibility).
     
  3. HenryChinaski

    HenryChinaski

    Joined:
    Jul 9, 2013
    Posts:
    108
    It's something!

    But seriously, I actually own A* Pathfinding Pro. I just thought that I would prefer to not use too many third-party assets. I knew that my solution is extremely inefficient. I assume I just underestimated the exponential effects and thought it would be fine for such a small grid.

    Thanks for the tip, anyway!
     
  4. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    You can roll your own A*, it's an algorithm that existed for a long time predating most video games (1968).
    https://en.wikipedia.org/wiki/A*_search_algorithm

    So you don't have to use 3rd party to get A*. You just have to use A*.

    There's even an earlier (1956) version that is less efficient (though more than yours), and that's Dijkstra's algorithm:
    https://en.wikipedia.org/wiki/Dijkstra's_algorithm

    It's useful because A* basically builds on Dijkstra. So if you start with one you can use it to help understand the second.

    I also implemented Dijkstra here:
    https://github.com/lordofduct/space.../SPPathfinding/Graphs/DijkstraPathResolver.cs