Second test

Second part of the tests.
Game gave order to the group of the settlement's inhabitants to move to another randomly selected settlement.
The random settlement can be anywhere on the map.
I followed them, of course.
They gathered at the some random point inside of their settlement, it could be even the far corner ^_^.
Then, game was changing next 'beacon point' every 6000 turns.
Of course, we were losing NPC during this exodus - stragglers, guys who wanted to step on the each other position and so on.
It looked less like army unit on the move and more like carnival. Because NPC were selecting different positions inside the beacon, every single move.
Also, this 'trip' showed flaw in pathfinding algoritm. It worked well in a short distance, but when we have huge catacombs, it can go looking for path to some sideways alley and clutter itself. 
Another variant, algorithm can find the right way, but it would be rather long one. 
For example 3000 tiles.
Sounds Okay? Then repeat it for all creatures of the group every turn.
I am not saving the whole path for then creatures, because don't find it reasonable.

I had other idea.  Thanks to road map we have now.
This algorithm:

1. Every time, when creature has to find its path from A to B game will make raw calculation, how far this coordinates  from each other. 
if  (abs(x1-x2) + abs(y1-y2) ) > N goto (RoadMap search)

okay, B stays in a reasonable range from A, Lets try standard  pathfinding.
This pathfinding has interation limit set to X.
If it founds the path -- hurray! Let move the creature (END)
If it couldn't find path soon enough, we don't want to bother any longer and go to (RoadMap search)

(RoadMap search)
We will make a pathfinding search on a road map.
First of all, we check the creature. Are you at road map? If no, it means that poor fellow was bugged and dug into the wall. It occurs from time to time. I am embarrassed. 
If Not at road map, then start some debug routines and END the pathfinding. There is no catch for this creature.

If it is okay, we will found nearest coordinates, that would eventually bring our creature to its destination.
Of course, they aren't 100% precise, but we don't want them to be so precise, we want creature to move in to thee direction of its goal as soon as possible.
If it wouldn't 100% precise, it would be even nicer, because creature would be more lively, that straightforward AI ruled android.
And then, we will start our short-ranged pathfinding again.It would work well, this time.

PS. Theoretically. Road map can fail, if two clusters would be considered linked , when they are not. For example, they would have long 1 tile wall between then or at one of them. I'll think about this potential issue later. 

EDIT: I found the solution. We would make precalculations. Find short path from every empty tile of one road map unit to another. If at least one misses to onother - ban this direction for global pathfindig.
EDIT2: Also, it would be great idea to move pathfinding calculations for 'out of screen' NPC to another thread and implement them in bulk, when they are done.Theoretically, few creatures may decide to move to one tile. But it wouldn't happen on the screen! Other creature got your cookie? Better luck next time.
The same thing is for groups of creatures. I think I'll do this now, because groups doesn't have any visible representation on the game map and store all data inside their own classes. They just prepare calculations, that would be used for creatures in future. No possible conflicts at all!