Computation is done on worker so main thread should be safe all the time.
I plan to add textual information on each step, to show how algorithm is "thinking".
Also, heuristics is fixed for now, I plan to add heuristics choice. So,
Roadmap: - different heuristics - 8 way support - Detailed explanation of each step
Let me know what you think!
Yep after playing around with it for a bit it didn't give a minimum path. I believe something is wrong with the heuristic you are using.
Edit: You can prove A* will give a min path as long as: heuristic(x to y) <= min_cost(x to y). Problem seems to be here https://github.com/ssaric/algoviz/blob/master/src/util/GridN... I think it should be a matter of removing "times 100"
I got my knowledge about heuristics from here:
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics...
But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example:
xxx
xEx
x x
x x
x x
x x
Sxxxxxxxxxxxxxx x
x
xxxxxxxxxxxxxxxxI don’t think the algorithm is correct though. The heuristic seems to use Euclidean distance instead of “how the crow flies” and thus this implementation goes along the axis instead of directly towards the goal. This causes the algorithm to find the optimal route only occasionally and probably has little to no effect on average execution time.
You have Manhattan distance and you want Euclidean distance to make sure the path is always optimal. Execution speed should be the same or better in the average case with Euclidean distance.
> I plan to add textual information on each step, to show how algorithm is "thinking"