Simple-optimized-A-Pathfinder
August 27, 2020 ยท View on GitHub
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:
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 |
