1: Google for heuristics, which is an algorithm to help the pathfinder to guess the next move.

2: Either put pathfinding in it's own thread or do time/frame based divisions (i.e only let pathfinding take 100 ms each frame - if not complete, wait till next frame and continue then)

3: Multiple grids, or use node-based pathfinding instead of grid-based. You could easily link the grids together so that B contains four tiles from A for instance.

Cheers!

Pathfinding rocks! It's like magic to watch the little critters find their way around the maps! :)

/Robert

Just thought of a crazy idea:

You could add a deviation-cost into the calculations...?
Imagine a line drawn directly between start and finish, and the further away from the line, the higher the cost (in addition the already calculated cost to the finish node). This SHOULD lead to units always trying to find a direct line towards their target.

It could create problems thou, since the agents may take longer paths than required to get to the target - especially if the obstacles are long thin walls for instance.

/Robert

Why is path 1 incorrect? It's just the same as path 2 (distance-traveled and efficiency wise). Anyway, maybe try using Euclidean distance (just test it with Euclidean distance; I wouldn't recommend using Euclidean distance in the end seeing as it requires a sqrt).

I'm going to guess you want your path's to have some kind of constant slope when possible so that the unit can move in a straight path from A to B without being forced to use some path that makes its movement unnatural (meaning it is obvious it is on a grid). This is a bit of a problem though. If you're doing 8-directional A* pathfinding, you have to realize that movement is constricted to 8 directions. That means that if your unit is going from A to B, it will travel there using those 8 directions and only those 8 directions. If you want to be able to move in any direction, well, that's another problem which I unfortunately can't help much with.