An simple and optimized grid pathfinding
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Assets
ProjectSettings
UnityPackageManager
.gitignore
README.md
_config.yml

README.md

Simple-optimized-A-Pathfinder

A simple pathfinder that I tried to optimize the maximum as I can, and share what I've discovered :)

The idea was pretty simple, implement a simple A* Pathfinder and use Unity Profiler to try to optimize the best as I can, trying to reduce the GC and the MS from the method itself

Final result:

alt text

Steps Descriptions

  • Step 1 - Dictionary used to for checking if a Tile is already on OpenList;
  • Step 2 - Caching index when comparing best tile from the open list, and using it to remove it from the list;
  • Step 3 - Static neighbours array;
  • Step 4 - Add FastPriorityQueue as OpenList;
  • Step 5 - Replacing Vector2Int to int for X and Y position;
  • Step 6 - Using reversed for instead of foreach on the neighbour's array;
  • Step 7 - Removing Dictionary for the open list, since FastQueue it's doing the same
  • Step 8 - Change return List to be List from Tile
  • Step 9 - Using only F cost when adding to the priority queue
  • Step 10 - Removing the reverse method from the GetPath
  • Step 11 - Removing closedList and using a Toggle inside the Tile itself
  • Step 12 - Increasing return list size to be 20% of the available tiles on the map

Performance Comparison

Keep in mind that all the results bellow are made inside Unity Deep Profiler, so the real performance its probably better than this, I'm working on the profiler for real builds

Action GC GetPath() MS GC to original GC to previous GetPath() MS to original GetPath() MS ToPrevious Commit
Original 40,6 KB 29,87 ms Original File
Step 1 50,3 KB 20,14 ms +23,89% +23,89% -32,57% -32,57% Commit
Step 2 50,3 KB 16,95 ms +23,89% 0% -43,25% -15,87% Commit
Step 3 36,2 KB 16,92 ms -10,14% -28,03% -43,35% -0,18% Commit
Step 4 32 KB 10,97 ms -21,18% -11,60% -63,27% -35,17% Commit
Step 5 32 KB 9,91 ms -21,18% 0% -66,82% -9,66% Commit
Step 6 32 KB 10,11 ms -21,18% 0% -66,15% -2,02% Commit
Step 7 22,1 KB 7,53 ms -45,57% -30,94% -74,79% -25,52% Commit
Step 8 22,1 KB 7,46 ms -45,57% 0% -75,03% -0,93% Commit
Step 9 12,6 KB 7,46 ms -68,97% -42,99% -75,03% 0% Commit
Step 10 12,6 KB 7,32 ms -68,97% 0% -75,49% -1,88% Commit
Step 11 4,2 KB 6,59 ms -89,66% -66,67% -77,94% -9,97% Commit
Step 12 0 KB 4,82 ms -100% -100% -83,86% -26,86% Commit

profiler