Much depends on what is dynamic (which effects continuing validity of a path that is found) .

If nothing impacts a path once it is built then the calculated paths dont need to be redone over and over

If the things that impact the path validity move less than once a second (or alot less), then re-calculating the paths much faster than that is a waste.
(You may even be able to detect IF something on the map changed each 'turn' and if it hasnt, then the previously calculated paths can be reused0

When the target is far away. you mau be able to continue to reuse the old calculated path (or only recaclulate it infrequently) until you get close enuf or get stuck on something dynamic. (You may have to find any factors/cases where it DOES matter to recalculate faster).


Usually when you are very close (terminal guidance) to the target is when you need to recalculate very frequently (which usually has to be handled specially anyway)

If you have alot of dynamic elements (things that block paths change alot) then there also can be processing variations that can reuse/patch a saved path data (so as to not require full recalculation).

----

Multi-threading can be useful when you have cores to spare- (and see Processor affinity to help that along) especially when you have many objects that need pathfinding done for them (but with the usual issues of handling any map dynamic changes ).

For huge maps (and long paths) - hierarchical pathfinding can be very important

Yeah, your datastructure is definitely a problem.

A common, and very fast way, let the nodes be cells in an array, like pixels in a bitmap, and just mark cells as "unpassable" for walls and such.
Then finding neighbours is as easy as adding or substracting to the index of the current node.

Edit: didn't see the last post Glad to see you've improved it.

yeah the flagged 'grid' border eliminates the costly edge coordinate tests


I helped someone long ago with every optimzation possible and even went so far as ditching the 2D array, using a single dimensional array/memory block and pointer math +/- 1 for the X axiz and +/- a precaclulated map width for the Y (I forget if we did byte addressing directly to get rid of the pointer multiply altogether- though I do recall an 8 grid direction array with all the single value offsets precalculated) .

The pointers also helped with the open/closed list (one offset value to point to the map data) . Along with other things like using a HeapQ and smallest datas possible to minimize cache misses (which was far more significant than word alignment issues).

It was amazing how much faster we got it to run (and we were using large maps 1K x 1K where you needed the performance)