There are several things you will notice about this picture:
First, it has ugly lines all over it. I was using those so I knew where tiles began and ended, for some debugging stuff I still haven't quite fixed.
Second, that map took 14.2 seconds to generate. It is 70x70, and contains 20 rooms, all connected, and then an extra 20 unnecessary links. In short, the map generator is pretty slow. I'm working on ways to speed it up. At the moment, the bottleneck is ensuring connectivity between regions on the graph. The way it's currently done is to select two regions, select a starting point, and then do Dijkstra's algorithm until you hit a turf that's in the border of the second region, and that's your path. It would seem clever to select an endpoint from the borders of the second region and do A*, but that tends to drastically increase the number of rejected paths when there are few regions left, because the points selected tend to be on opposite sides of the map, so that's not an option.
Most of that time is going into paths that are being rejected because they get too long before hitting a border turf in the second region. So some way to identify likely-to-fail pathfinds would probably go a long way to solving the issue. Any suggestions? Additionally, some sort of sorted array would speed up my implementation of Dijkstra's algorithm significantly, but I'm pretty sure the speed issues are all the failed pathfinds.
Thirdly, some of those paths can be crossed into rooms from a diagonal - this is both undesirable and undesired. I have attempted to remedy it by adding turfs to the list of borders if they have two adjacent turfs that are in the borders (where adjacency does not include diagonals). This did not work. Instead, it caused too many turfs to be marked as borders, and prevented a lot of the interlinking occuring, so I got rid of it. I'm still considering other fixes. I think I have a way to solve the issues with the original implementation.
Fourthly, all the rooms are rectangular. This is not a limitation of the algorithm, which can make arbitrary rooms, as specified by the user. It's just the way I've whipped up the demo for now. The program theoretically supports arbitrary rooms right now. Yes, that means arbitrary rooms are currently untested, but I intend to fix that once I've got the basic algorithm functioning nicely.
Fifthly, some of the extra paths tacked onto the ends of others are somewhat useless. The one in the bottom-left corner is a prime example. I'm not sure if this is a problem or not, but I suspect it's caused by the large numbers of 'extra' paths I'm adding in this example (one for every room). This is not yet tested, because I've got other issues to work out.
Finally, if you want to have a look at the code yourself, the source as of this post is here. It is not yet ready for use in projects, I just thought people might want to have a look at it and fiddle.
I'd suggest not, though, because it's completely uncommented and pretty ugly at the moment. :P
