my, now this has become a thread.
Well, as an update, I have used several Array arrays in my new pathfinding algorithm, the finalized (for now) pathfinding class can now pathfind over complex/convoluted mazed-terrain on a 256x256 map at a rate of 0-1ms/calc for short, and 8-10ms/calc for long distances. (Average long distances check around 35,000 tiles before finalizing the path, pathing over a complicated maze from around 0,0 on the map to 256,256).
My pathfinding is my own take on A*, that removes almost all of the terrain/heuristic data and actually seeks the path backwards from destination to start. It also finds shortest path A* would have found every time.
I currently have over 5,000 entities picking random spots all over a 256x256 map and pathfinding to them, and keeping a solid 60FPS.
I'll share the code later, when I'm done cleaning it up and announce the second project that this is a part of.