It took a while for the A* pathfinding algorithm to find a way around that big lake - but it did.

To make the performance faster I will need some clever optimization. But many of the widely used optimizations for A* are designed for maps with rooms and corridors etc - a big, irregular shape like that lake area is still bit of a problem. I guess I need to add some pre-calculating to random world generator, so that it would analyze the map and save some data which would help to speed up the pathfinding.