Thanks for the comments guys. I appreciate your input.
If your algorithm works OK with "X" towns, why not limit the number of towns you consider, using some 'intelligent' criteria to weed out uninteresting places, such as: "Already have a high degree of service (me or other)", "Too small population", "Too far away from everything" etc. until you're down at X towns to optimize. Of course, this will not give you a global optimum, but it might be good enough.
Hmm yes, that's a good idea.
I was thinking of having a domain restriction based on the distance from the home town (which is semi-randomly selected), however it would be nice to have different strategies for selecting a domain, especially "too small population". I usually find than small towns of less than 200~300 people are a huge drain on profits.
Or consider tha large map as a number of smaller maps, and develop one part at a time.
Oooh, regional services... I REALLY like this idea!
How would you split the map into "parts"? Ooooh, here's an idea... find the a list of the largest cities (top 10-percentile by population perhaps) and then use those to split the map into "counties" or "provinces" (I don't know the term used in Sweden) using a Voronoi diagram
. I already have an algorithm to compute the dual-graph of this, so it should be pretty straight-forward.
Some of the upcoming changes I am thinking about will require having multiple plan graphs anyway, one per cargo "scheme", e.g. one for pax/mail, one for coal, one for the farm vector, etc... Perhaps the pax scheme could be split into pax-regional (one graph per region) and pax-express/-intercity.
Its all a bit meaningless with stock TTDLX buses, but with NewGRFs (Zephyris' generic road vehicles set has some cool coaches that I'd like to take advantage of), or better yet once rail gets implemented in NoAI, this could really take off! I love stuff like this! This is the fun bit for me.
AndersI suggestion will also help take into account water-heavy maps. There are sometimes areas that, while technically feasible to connect via. road, are economically completely rubbish decisions to make!
You're absolutely right, and this really is something I need to fix. On maps with a high sea level it builds ridiculously long bridges all over the place.
I was thinking of applying a pruning stage after the triangulation graph is computed, to discount any links that cross the sea or that are otherwise impractical. Any ideas on how I could determine whether a link worthwhile or not?
Usually buses don't go to far, so linking up towns more then 100-200 (or more?) tiles apart, due to the nature of breakdowns, is rather counter productive in most cases (and with rail, if we get to it, is easier done on a station-to-station, or branch-station-onto-mainline-route mentality).
So you could always use the algorithm, but on very specific groups of towns. After all, the AI still needs to make use of the roads - building them is fair enough, as a task it is something necessary, but it doesn't make any sense to do it for unused roads does it? (or is the exercise ignoring that?)
Roads are only actually BUILT when needed to implement a bus route, and those routes are selected based on which is most profitable. However I don't currently consider breakdowns... maybe I should factor that in. Thanks for the tip!
Once we have rail then I think it would be best to split up services as you suggest, however for now since we only have buses to play with and I still want to work with long range services, I'll stick with the current system! To be honest, right now I have more interest in designing a realistic and aesthetically pleasing road network than in making profit! I'll worry about winning the tournament later on!
Thanks again guys