Hello,

I would like to give some ideas that I learned while working on the path-finding for my game. I'm going to try to keep it short :)

First, if you have islands that are not connected, then you should definitely use the above suggestions; i.e. check all blocks against one and pre-calculate the islands. If this value doesn't match starting block it is unreachable. You should also close any blocks that are completely unreachable. For instance, if an area is enclosed by a ring of mountains.

Second, I would break your path down into 2-3 components. In my game, I call the first path calculation the "far-path", which only cares about closed blocks (it ignores all units that can not be seen unless in range). I compress it by saving every X blocks, where X is the max number of blocks (radius) each player unit can see (10 in my game).

When determining each next move, I calculate the "near-path." This process cares about all entities, but only within a range (max G-Value). Any blocks that are greater than this max G-value are ignored as bad choices. I use a range that is equal to max visible blocks * 3, where the destination is taken from the far path. The destination block is always 2 in advance, so you are guaranteed to be checking just out of visible range, which keeps the path smooth.

Finally, there are times when your units get blocked by other units, such as the peninsula case. I handle this case with a 3rd path, which I just call the "middle-path." When my near-path fails, I re-calculate it, but caring only about closed blocks (like I did with the far-path). I save each block that is occupied, which will be player units (dont save the destination since you just checked it).

I work from destination back to the location of the unit requesting next move until a successful path is found. This keeps your units moving and bunches them up at the peninsula. I have some other tweaks like if the unit is within 6 blocks of final destination and cant move, I just clear the path and assume it is bunched up with other units at a mass-destination. This keeps them from trying constantly, which wastes CPU time.

Anyway, this sounds complex but it is really pretty simple. It reduces the constant path-finding calculations of the full path to just an area around the unit. It compresses the path so you dont have to use much memory. It handles dynamic paths around units. It also handles being blocked. There's more to it, but this is already long enough :)

If you are interested in this solution and have any specific questions, please ask.

-Mike