I didn't get much of a reception for this pathfinding algorithm at cprogramming.com (the site is a bit of a farce now anyway). The algorithm uses precompiled connectivity matrices so that you don't need to calculate the entire path before knowing which next move to take. I don't particularly want to re-write everything so I'm just going to post a link to the thread on cprog (contains screenshots, link to the demo and link to the paper detailing it, you need not register to view these things), I hope this is okay. cprog Note this is most similar to 'Floy'd all pair's algorithm' except it's faster, uses less memory, and I didn't know floy'd all pair's algorithm existed when I wrote it.

Don't expect much of a reception here either. Your code is very difficult to follow, the paper providing an explanation of your method is lacking in many important places (you claim to have a matrix multiplication function that doesn't do any math?), and your method seems to rely on using sparse matrices to reduce the memory required but this only helps if the connectivity graph has lots of islands since the full connectivity matrix will have an entry for every pair of nodes that a path exists between. The screenshots of your demo show that your test world has many islands.

>>you claim to have a matrix multiplication function that doesn't do any math?

In the source, VectorCollapsedMatrixMultiply, I should have put that in the paper

>>and your method seems to rely on using sparse matrices to reduce the memory required but this only helps if the connectivity graph has lots of islands since the full connectivity matrix will have an entry for every pair of nodes that a path exists between

Duly noted, the demo randomly generates a maze, the islands appeared accidentally, using a sparse matrix speeds up the computation time (in the function that doesn't do any math to build higher order matrices).


So, your suggestions are to make my code clearer, and a better mechanism for making mazes?

Ultimately I did this on a whim, it's not an overly important project for me to be honest, but I thought I should at least just post the demo (most people just stick with A* or the like without trying a much different approach).