thatdan123/simple-optimized-a-pathfinder

An simple and optimized grid pathfinding

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