Hmm, I have some tips.
Start from the source and destination, and send out 3 rays in three threads, on biased towards the left, on biased towards the middle, one biased towards the right. Have them jump randomly to a tile according the their bias at like a 65/35 ratio, starting from the source and destination. (This gives you 6 threads) And you can keep the map data in memory. Just loading in the cords of each unit you need to calculate with arguments.
When you finish, you clean up the paths, by finding where the paths run adjacent to each other. Then you calculate the total length, and pick the path that's shortest.
An additional optimization is you take the last two numbers of the ID, or convert the letters to number, and divide this into 60 frames, so you spread the load across 60 frames instead of calculating the path for every object every frame.
You can extend this to move between zones by, making each portal represent a list in locations it can access, with perhaps a score for how long it gets there, but that's complicated.
You basically just want to make a list of objects you need to pathfind, divide these objects into 60 somehow. Using the ID is a fast way to do it. For each object, calculate the shortest path using any number of algorithms or design one yourself. You have to have an interface between your pathfinding algorithm and your map data. You could generate a map of walkable tiles to make this easier as well. Another cool optimization is you can weight certain tiles by how desirable they are to walk on, so a sidewalk would have a score of 10, and grass a score of 5, and a wet area a score of 1.
This might be way too complicated. You could try to implement a simple algorithm like put your hand on the left wall and follow it and then delete loops where the paths are next to each other. This is how you get out of mazes. You could try just sending two rays directly towards each other and then moving over one if it hits a blockage. The problem with these simple algorithms is they look unnatural or may fail. You should at the minimum implement route optimization by cutting out unnecessary loops, and use multiple routes to see which one is the shortest which will make even simple algorithms appear much more natural.
Most game engines should have some kind of basic implementation. ChatGPT is really good for stuff like this. Little code bytes, helping you debug, and learning theory. Just feed it back the debugger output, and keep things simple and in small bites, so it doesn't get stuck so much or generate a lot of broken code at once that's hard to debug.