I have recently implemented the A* pathfinding algorithm in C# based on some pseudo code that I found.
I need the algorithm to run as fast as possible and at present my code isn't quite cutting it. I understand that the heuristics used can have a big impact on the performance of the algorithm, however, I have gotten to the point where I feel that the only way that I can make further gains is to optimise the algorithm itself.
The reason why I need the algorithm to be so fast is so that I can 'instantly' determine a decent estimate for the time it would take to travel between two points.
So far I have tried using a hierarchical graph structure to allow at least a partial path to be returned immediately -- The problem with this approach is that I don't actually need path data immediately, I simply need the path to be computed in order to get the time estimate.
I have also considered making the pathfind function unsafe in order to improve performance but I'm not really sure how this would work -- I can't create node pointers because they are "non-unmanaged" types.
This is essentially the first time where I've had to write performance critical code in C# (usually I'm working in C++) so I'm not sure what I could do to really squeeze those gains. If anyone has any ideas then I would greatly appreciate it.