I think I got it fixed. I removed the assertion anyway just to be safe. Even if this still fails in rare occastion (I spent hours generating 4k maps with 900 roads without triggering it, so it has to be very rare) the game will try later to connect a city again. So it's very unlikely anything stays unconnected even if it fails once.
Should be fine now. To make sure rare strange maps don't cause too much of a slowdown (happens maybe 1:100 times, but can take a few minutes for a single town then), I added a max limit for the A* search of a million nodes. That's still more than good enough for 4k by 4k maps and still fast enough in the worst case that the game won't seem frozen.
If anybody adds this to a patch that supports maps larger than 4k x 4k you probably don't want to increase this either. Most of the time less than 30k nodes are explored to find a path. So unless you create a 16k x 16k town with two unconnected continents and like 4 cities on each, this shouldn't be a problem. If it is, just get rid of the limit, but then it can take quite a while sometimes, if the map is weirdly set up.
1024x1024 maps usually get their roads set up in seconds, even with towns set to "many". In fact, many is probably faster, since the cities are closer together. But even custom low numbers work. I've tries 4k x 4k with a 100 town limit, and it was still fast enough. Should be fine now
If anything else fails, which I don't think it will, report a bug on my GitHub pls. I don't check here too often.
@JGR and others who might look at this: If you find any improvements, any fixes or ways to improve performance even more, let me know and maybe do a pull request. I'll put the branch online as well. Thanks.
Newest patch file and screenshots in the first post.