PathZilla (v6) - A networking AI

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Post Reply
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

PathZilla (v6) - A networking AI

Post by Zutty »

Image

Here is my AI - PathZilla. The focus of this AI is on high level planning and neat, realistic construction.

To get the best results from PathZilla you are strongly advised to activate the advanced setting "Stations" > "Allow drive-through road stops on town owned roads". PathZilla will still function correctly without this but will need to perform more demolition in towns, which can complicate things.

The AI has a number of settings which the user should change to their personal preference. If desired, the player will find a less challenging opponent if setting planning speed to very slow, turning aggression off, and setting traffic to low. Regardless of these settings though, the AI will always attempt to build a complete network and turn a profit.
pathzilla.tar
PathZilla v6 - for 0.7.0 and up
(276 KiB) Downloaded 4332 times
NOTE: The preferred method to install PathZilla is via the in-game content downloading service.

Features
  • High-level network planning using graph theory
  • Uses two tiers of pathfinding to improve line re-use
  • Aesthetic pathfinding builds tram lines alongside roads and honours town grid layouts where applicable
  • Full support for articulated vehicles and trams, where available
  • Builds "green belt" around towns to improve local authority rating
  • Supports NewGRF vehicles (tested with Zephyris' eGRVTS, George's Long Vehicles v4, and PikkaBird?'s HOVS)
  • Supports NewGRF house and industry sets (tested with TTRS, George's ECS Vectors and PikkaBird's PBI)
  • Builds multiple road stations per town and maintains fleet sizes
  • Supports save/load and difficulty settings
  • Supports all primary industries
Separation of road and tram tracks to reduce congestion...
Image

Snap-to-grid for 2x2 and 3x3 town layouts...
Image

"Green belt" construction to improve local authority rating...
Image

Changelog
v6 - 08/07/2009
  • Added support for primary industries and NewGRF house sets
  • Improved 2x2/3x3 town grid handling
  • Construction of windy "country lanes" at early dates and in small towns
  • Added configuration option for amount of traffic to generate
  • Allow AI to sell vehicles from unprofitable services
  • Better handling of construction in traffic
  • Reduce initial processing steps to allow AI to start faster
v5 - 24/01/2009
  • Changed to library pathfinder (with modifications)
  • Split different road types and honour 2x2/3x3 town grid layouts where possible
  • Re-wrote station placement to be more flexible
  • Maintain fleet sizes based on waiting cargo
  • Enable bribing of town authority & build trees around a town to improve local authority rating
  • Re-attempt pathfinding if construction fails
  • Fixed various bugs
v4 - 01/10/2008
  • Improved DTRS support and enabled ARVs where possible
  • Added support for trams
  • Added generic cargo support for towns only (i.e. mail)
  • Improved vehicle selection criteria. Gives more variety with large sets like eGRVTS
  • Changed fleet size and property management to improve profitability at early dates (pre-1950)
v3 - 16/08/2008
  • Added save/load support
  • Introduced size limit for service planning data sets, to reduce memory usage and save file size
  • Added support for AI difficulty settings, which scale work intervals and aggression
  • Added a 'aggressive' setting. When PathZilla is not aggressive it will try to avoid building stations near to competitors
  • Fixed bugs
v2 - 11/08/2008
  • Vastly improved performance by optimising graph algorithms
  • Introduced limit on number of targets (towns) that will be included in the master graph, to make very large maps(2048x2048) playable
  • Changed service selection routine to process one town at a time, furtherimproving performance
  • Fixed various bugs, including one that caused the AI to go crazy when the local authority rating got too low
v1.1 - 29/07/2008
  • Changed require() statements to use cross-platform slashes
  • Reduced work intervals to make AI more aggressive
See the readme.txt file for the full changelog.

I have attached a screenshot showing performance after 10 years on a demo run. Its not going to win any tournaments, but I'm quite happy with the performance.

I have also attached a short animation (apologies for size - will remove if anyone wants) which shows how the network planning works. It starts with a delaunay triangulation of the set of all towns in the map. Based on the triangulation it then computes a shortest path tree from a large "home town" (chosen from the top 10% percentile by population) and the minimum spanning tree, and adds them together to form a "plan" graph. The AI also stores an "actual" graph, which represents what has actaully been built. Whenever new routes are built they are selected from the "plan" graph (i.e. the plan governs what CAN be built) and added to the "actual" graph.

I have commited the source to SVN at Google Code, so you can view it online if you like. The URL is...

http://code.google.com/p/ottd-noai-pathzilla/

I like the idea of browsing the code without having to download the whole thing and load it into an IDE, etc... so I think this is rather neat. The code is GPL too so feel free to use any of it.

Hope you like it :) Any comments or questions?

BTW I didn't draw the dinosaur! Its from a free icon set! :D

Edit (08/07/2009): Added version 6 with a new 10 year performance shot. Used more aggressive settings to give most "tournament"-like performance.
Attachments
Network planning breakdown
Network planning breakdown
networking.gif (630.54 KiB) Viewed 63776 times
perfshot6.png
Performance after 10 years (with eGRVTS & HEQS)
(460.74 KiB) Downloaded 62 times
Last edited by Zutty on 08 Jul 2009 23:27, edited 16 times in total.
PathZilla - A networking AI - Now with tram support.
Misha
Engineer
Engineer
Posts: 18
Joined: 21 Jul 2008 17:39

Re: PathZilla (v1) - A road networking AI

Post by Misha »

It looks very cool, so I tried to run it. But every time I got this error when it tries to build a station:

BuildStation() pathzilla\roadManager.nut.line(222)
script error: wrong number of parameters

How is that possible? I guess you didn't face it.

The line numbers in the tar-file are different, but I think it's this line that triggers it:

Code: Select all

local success = AIRoad.BuildRoadStation(stationTile, roadTile, truckStation, useDtrs, true);
But I don't see how that could be wrong.
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1) - A road networking AI

Post by Zutty »

Thanks for trying it Misha. :) What version of NoAI are you using? PathZilla v1 requires NoAI r13837. It looks like your using a version prior to r13751.

Sorry I should have mentioned this in the firt post!
PathZilla - A networking AI - Now with tram support.
wilco_moerman
Engineer
Engineer
Posts: 70
Joined: 05 Jun 2008 15:51

Re: PathZilla (v1) - A road networking AI

Post by wilco_moerman »

your method sounds interesting, but is it fast enough on large worlds? I have tried a clustering algorithm, but on a 512x512 world it takes many months to run.
Nunc dimittis servum tuum Domine secundum verbum tuum in pace
Yexo
Tycoon
Tycoon
Posts: 3663
Joined: 20 Dec 2007 12:49

Re: PathZilla (v1) - A road networking AI

Post by Yexo »

Impressive AI you made :D I really like the way you are generating your routes. Keep up the good work.

I did some testing with it (either alone and against admiralai (with only busses) and convoy). It loses from those two, but only because you sleep a lot. For example, in your main loop you only build a new route every 10000 ticks, this is not enough in the beginning of the game (it is against a human, but not in a tournament AI vs AI).

And a small bug report: If it tries to build a road depot, it doesn't test whether or not building the road to connect the depot with the tile in front of it succeeds, so on a busy road it sometimes fails to connect the depot. It sitll builds vehicles there, but they can't go anywhere.
TrueBrain
OpenTTD Developer
OpenTTD Developer
Posts: 1370
Joined: 31 May 2004 09:21

Re: PathZilla (v1) - A road networking AI

Post by TrueBrain »

The tournament failed on your AI.

This is because you use \\ in 'require'. Please don't. On all OSes you should use '/', and this will work. With \\, it only works on Windows ... which I don't own ;)
The only thing necessary for the triumph of evil is for good men to do nothing.
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1) - A road networking AI

Post by Zutty »

Thanks for the replies guys :)
wilco_moerman wrote:your method sounds interesting, but is it fast enough on large worlds? I have tried a clustering algorithm, but on a 512x512 world it takes many months to run.
Hmm, good question. It takes a couple of months on a 256x256 TBH, but I've never found that to be an issue for profitability. There are some improvements that I can make though. I'll try it tonight on a bigger map (2048x2048!!).
Yexo wrote:Impressive AI you made :D I really like the way you are generating your routes. Keep up the good work.
Thanks very much :)
I did some testing with it (either alone and against admiralai (with only busses) and convoy). It loses from those two, but only because you sleep a lot. For example, in your main loop you only build a new route every 10000 ticks, this is not enough in the beginning of the game (it is against a human, but not in a tournament AI vs AI).
Hmmmm... damn! I pitted it against Convoy 1.7 and it steam-rolled it (might have been a bug in Convoy though!!), but that might be because my environment is different to yours. I play with maximum AI construction speed in settings, with fast-forward on and full animation off, all on a 3.2GHz quad-core CPU. Is it possible that I have set my delays too long because they seemed short in my setup?

I must admit that I did initially set them that long to try to compensate for a lack of optimisation in some of my nastier code!
And a small bug report: If it tries to build a road depot, it doesn't test whether or not building the road to connect the depot with the tile in front of it succeeds, so on a busy road it sometimes fails to connect the depot. It sitll builds vehicles there, but they can't go anywhere.
Doh. I built a routine to handle this but couldn't remember where to put it!! Cheers.

TrueLight wrote:The tournament failed on your AI.

This is because you use \\ in 'require'. Please don't. On all OSes you should use '/', and this will work. With \\, it only works on Windows ... which I don't own ;)
Damn! I tried it with /es at first but it didn't work in Windoze. Maybe I'm doing something wrong.

I'll update it ASAP as I don't want to miss out on the tournament. (I don't want to force you to wait for me though!) I'll recude the delays too so that I have a chance against Yexo!! :P

Thanks again.
PathZilla - A networking AI - Now with tram support.
Misha
Engineer
Engineer
Posts: 18
Joined: 21 Jul 2008 17:39

Re: PathZilla (v1) - A road networking AI

Post by Misha »

I downloaded noai-r13857 and now it works. :) I saw that Pathzilla is maximizing road re-use by using Convoys roads.

I have now 3 versions of openttd on my computer, is that bad? And if such newbie questions are asked often, where can I find the answers?;)
Yexo
Tycoon
Tycoon
Posts: 3663
Joined: 20 Dec 2007 12:49

Re: PathZilla (v1) - A road networking AI

Post by Yexo »

Misha wrote:I downloaded noai-r13857 and now it works. :) I saw that Pathzilla is maximizing road re-use by using Convoys roads.

I have now 3 versions of openttd on my computer, is that bad? And if such newbie questions are asked often, where can I find the answers?;)
Multiple versions of openttd is no problem at all. Personally I have like 10 copies or so. Answers to some questions can be found in the wiki (wiki.openttd.org) and otherwise by searching the forums. If you can't find it, just ask and you'll get an answer :)
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1) - A road networking AI

Post by Zutty »

wilco_moerman wrote:....is it fast enough on large worlds?
Ahem..... no. You were right. On a 1024x1024 map with "high" town, just to compute the triangulation took... well, I gave up waiting after 10 YEARS!

I'll need to do some optimisation!
PathZilla - A networking AI - Now with tram support.
wilco_moerman
Engineer
Engineer
Posts: 70
Joined: 05 Jun 2008 15:51

Re: PathZilla (v1) - A road networking AI

Post by wilco_moerman »

Zutty wrote:
wilco_moerman wrote:....is it fast enough on large worlds?
Ahem..... no. You were right. On a 1024x1024 map with "high" town, just to compute the triangulation took... well, I gave up waiting after 10 YEARS!

I'll need to do some optimisation!
I was afraid of that ... same thing with my clustering algorithm. Works fine for 256x256, but is way too slow for 512x512. Problem is that the map size grows quadratically (for square maps) and that your algorithm (just as mine) probably has some quadratic (or higher) dependancy between running time and the amount of tiles in a world.

It is in fact the general problem for all artificial intelligence: many idea's that are perfrect on small toy problems are hopelessly complex and intractable for problems with a more serious size.
Nunc dimittis servum tuum Domine secundum verbum tuum in pace
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1) - A road networking AI

Post by Zutty »

After some more investigation, there seems to be some kind of violently geometric progression going on. On a 256x256 it takes less than a month. On a 512x512 (4 times as big) it takes 5 months. On a 1024x1024 (16 times as big) map it takes over 10 years. Hmmm... I'll try it on a 512x1024 to see if I get a sane value, but this doesn't seem to add up to me. Maybe theres another issue at work here (or maybe I was watching Mock the Week while the debug window was churning out "Save function not implemented" 10,000 times, and so I missed an error message!!!)

I'm already working on improvements to the algorithm itself, but I also thought that I would put in some kind of domain limitation too, just to keep things sane. For now it would be a hard limit, but I might be able to allow the AI to expand its domain incrementally.

Its a shame really... the AI doesn't care if it takes 30 years to figure out the graph. The game runs forever, for crying out loud! DAMN those puny human players, with their primitive notions of time and their "user interface" hogging up all the CPU!
PathZilla - A networking AI - Now with tram support.
wilco_moerman
Engineer
Engineer
Posts: 70
Joined: 05 Jun 2008 15:51

Re: PathZilla (v1) - A road networking AI

Post by wilco_moerman »

Zutty wrote:(..)Maybe theres another issue at work here (or maybe I was watching Mock the Week while the debug window was churning out "Save function not implemented" 10,000 times, and so I missed an error message!!!)
I just implemented a dummy save() that does nothing and specifically does not print any annoying things :)
Nunc dimittis servum tuum Domine secundum verbum tuum in pace
Yexo
Tycoon
Tycoon
Posts: 3663
Joined: 20 Dec 2007 12:49

Re: PathZilla (v1) - A road networking AI

Post by Yexo »

wilco_moerman wrote:
Zutty wrote:(..)Maybe theres another issue at work here (or maybe I was watching Mock the Week while the debug window was churning out "Save function not implemented" 10,000 times, and so I missed an error message!!!)
I just implemented a dummy save() that does nothing and specifically does not print any annoying things :)
Or you could just disable autosave as long as you haven't implemented save / load functions.
Jtm
Engineer
Engineer
Posts: 2
Joined: 29 Jul 2008 19:39

Re: PathZilla (v1.1) - A road networking AI

Post by Jtm »

Zutty,
Have you tried genetic algoritms to approximate the shortest route between the cities, in other words to find a solution for the traveling salesman problem? It is very fast even with hundreds of cities (solution found within seconds).

An example of Genetic Algorithm solution:
http://obitko.com/tutorials/genetic-alg ... xample.php

Similarly fast but also much more easily programmable solution is simulated annealing method:
http://en.wikipedia.org/wiki/Simulated_annealing

An example of Simulated Annealing solution:
http://www.svengato.com/salesman.html

Traveling Salesman Problem:
The amount of all possible routes between desired amount of cities is ½(n-1)!, where n is the number of cities.
For more information:
http://en.wikipedia.org/wiki/Traveling_salesman_problem
Finaldeath
Engineer
Engineer
Posts: 72
Joined: 09 Apr 2006 23:49
Location: UK
Contact:

Re: PathZilla (v1.1) - A road networking AI

Post by Finaldeath »

Yeah, the travelling salesperson is a really tough nut to crack, and really, players don't do it in their heads to be honest. Usually they link up towns (if they do need road at all!) by larger networks, or do it on-demand where in fact, spending some cash on extra roads for a more efficient route is deemed more effective.

Still an interesting way of doing it, I'm not personally convinced it'll scale enough. :)
Finaldeath
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1.1) - A road networking AI

Post by Zutty »

Hi all,

I have good news and bad news.

Good News: I have managed to make some significant optimisations. The triangulation for a 1024x1024 map with ~750 towns ("high" setting) now takes about 3~4 months to compute on "medium" AI construction speed, which I consider just about playable. On "very fast" construction speed it takes less than a month.

Bad News: A 2048 x 2048 map with ~3000 towns is still unplayable, taking longer than 10 years. Plus the service selection routine is still grossly underperformant (is that a word? - IT IS NOW!). Given n towns it takes O(n2) to choose its services, which for a map with 750 towns takes a ridiculously long time to compute! Even discounting the A* pathfinder which runs for every combination of towns, the pausing alone kills it! If Sleep(1) takes a millisecond, theres ~10 real life minutes of just of waiting!! Clearly, a re-think is needed here.

This is where Jtm comes in, I hope... :D
Jtm wrote:Zutty,
Have you tried genetic algoritms to approximate the shortest route between the cities, in other words to find a solution for the traveling salesman problem? It is very fast even with hundreds of cities (solution found within seconds).

An example of Genetic Algorithm solution:
http://obitko.com/tutorials/genetic-alg ... xample.php

Similarly fast but also much more easily programmable solution is simulated annealing method:
http://en.wikipedia.org/wiki/Simulated_annealing

An example of Simulated Annealing solution:
http://www.svengato.com/salesman.html

Traveling Salesman Problem:
The amount of all possible routes between desired amount of cities is ½(n-1)!, where n is the number of cities.
For more information:
http://en.wikipedia.org/wiki/Traveling_salesman_problem
Hi Jtm, thanks for posting.

I am familiar with the traveling salesman problem, but I don't want to use it to plan roads. I like the sort-of realistic look that I get from the methods I use now, though its still early days. Having sadi that though it might come in useful for creating the services that run on those roads. It would be interesting to see if a circular bus route with many stops would be more profitable than a series of point to point services.

I AM very interested in genetic algorithms, and stochastic optimisations in general. I must admit that I don't know much about this kind of thing yet, but I am keen to learn.

As you may be able to tell, I am in need of suggestions for solutions to the service problem.

Once the road network is planned out, PathZilla attempts to choose the most profitable service to run on the network. It does this by building up a matrix of all towns in the map and finding paths through the netowrk between them. it ten checks the distance accross the network against the distance as the crow flies to estimate how much profit can be made from the route. When all these routes are calculated it puts them in a big list and implements them one by one from the top down.

This works well on small maps but is wasteful on a larger one, as the AI can spend years waiting before it builds ANYTHING! If I could use something like a genetic algorithm or simulated annealing to choose the best service in a faster way, this would be a great boost for the AI.

Any ideas? I will do some reading on this topic but if you could give me a head start that would be great!

Cheers :D
PathZilla - A networking AI - Now with tram support.
User avatar
AndersI
Tycoon
Tycoon
Posts: 1732
Joined: 19 Apr 2004 20:09
Location: Sweden
Contact:

Re: PathZilla (v1.1) - A road networking AI

Post by AndersI »

Zutty wrote:Once the road network is planned out, PathZilla attempts to choose the most profitable service to run on the network. It does this by building up a matrix of all towns in the map and finding paths through the netowrk between them. it ten checks the distance accross the network against the distance as the crow flies to estimate how much profit can be made from the route. When all these routes are calculated it puts them in a big list and implements them one by one from the top down.

This works well on small maps but is wasteful on a larger one, as the AI can spend years waiting before it builds ANYTHING! If I could use something like a genetic algorithm or simulated annealing to choose the best service in a faster way, this would be a great boost for the AI.
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.

Or consider tha large map as a number of smaller maps, and develop one part at a time.
Finaldeath
Engineer
Engineer
Posts: 72
Joined: 09 Apr 2006 23:49
Location: UK
Contact:

Re: PathZilla (v1.1) - A road networking AI

Post by Finaldeath »

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! :)

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?)
Finaldeath
User avatar
Zutty
Director
Director
Posts: 565
Joined: 22 Jan 2008 16:33

Re: PathZilla (v1.1) - A road networking AI

Post by Zutty »

Thanks for the comments guys. I appreciate your input. :)
AndersI wrote: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.
AndersI wrote: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. :D

Finaldeath wrote: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?
Finaldeath wrote: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 :)
PathZilla - A networking AI - Now with tram support.
Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 9 guests