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

User avatar
planetmaker
OpenTTD Developer
OpenTTD Developer
Posts: 9414
Joined: 07 Nov 2007 22:44
Location: Sol d

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

Post by planetmaker »

Hi,
Zutty wrote: 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
unfortunately I haven't found time to test this AI so far, but some thoughts:

may I propose to maybe not look for the globally best solution but possibly for a local maximum. You might define yourself a maximum map size you want to play - and for larger maps you just build a graph for a smaller part of it and only start to incorporate the other parts later into your plan. You cannot go and fill an entire huge map in the beginning anyway.

Another approach would be to make a histogramme of town sizes (if you're dealing with pax only) and only take into account the biggest most xy towns - with the possibility to extend your graph locally with smaller towns in order to improve the efficiency of your network. The latter approach might be similar to an adaptive grid used variously in numerical simulations.

I know both of these two proposals might not be too easy to implement, though. But they're save to work once they're done :) or the algorithms are extended to other cargos and such.

Regards,
planetmaker

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 »

From your question; the best way to sort if you want to connect towns which are either expensive to connect (bridges! massively expensive per tile) or are too far apart - well, the latter is easy, the former, I'd suggest either a cost calculation (so it can take into account mountains getting in the way and tunnel usage too) or simply limiting the size of bridges to be something like 10-20 tiles max - and not in the pathfinder - let the pathfinder "find" the optimal but if it returns a bridge in it's list of items, don't use it if the bridge is too long.

Would need some tweaking however, but the premise is sound - high water maps really suffer for roads anyway. Of course if you have the cash and it is a reasonable distance, why not build a 100 tile bridge for a profitable route? :)

(and to be honest, long bridges are aesthetically unpleasing anyway :) ).
Finaldeath

dbkblk
Traffic Manager
Traffic Manager
Posts: 154
Joined: 29 Mar 2008 18:38

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

Post by dbkblk »

I've played a game with 3 pathzilla and they made stranges roads sometimes ! They also spam towns ^^ (i think some stops are nice but not too much...)

Moreover i can't play with eGRVTS because it always build articulated vehicules but never drive-trough stops ... so this never gonna work !
Attachments
Baker & Co., 23 Aut 1959.png
#Strange roads 1
(348.46 KiB) Downloaded 273 times
Baker & Co., 26 Aut 1959.png
#Strange roads 2
(301.23 KiB) Downloaded 233 times

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

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

Post by Zutty »

dbkblk wrote:I've played a game with 3 pathzilla and they made stranges roads sometimes ! They also spam towns ^^ (i think some stops are nice but not too much...)
Thanks for the play-testing dbkblk. :) This is all very useful information for me.

If the AI can a poor local authority rating then it goes crazy and builds roads all around a town. This is a known bug, and I will try to fix this ASAP.

If you think it is building too many bus stops in a town, I might put in a setting that allows the player to control how many stops it attempts to build. It might also be a good idea to have an "aggression" setting similar to Geektoo's Convoy, to allow or prevent it from building stations near to a competitor's stations.

I must also admit that I haven't tried playing a game with several instances of PathZilla running at once. Can you show me some examples of the strange roads that it builds?
dbkblk wrote:Moreover i can't play with eGRVTS because it always build articulated vehicules but never drive-trough stops ... so this never gonna work !
Can't articulated vehciles stop at a non-drive through station? I didn't know that :oops: I write AI more than I actually play the game, clearly!

I think this can also be fixed.

Thanks again dbkblk :)
PathZilla - A networking AI - Now with tram support.

dbkblk
Traffic Manager
Traffic Manager
Posts: 154
Joined: 29 Mar 2008 18:38

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

Post by dbkblk »

Zutty wrote:Can you show me some examples of the strange roads that it builds?
I put two examples on my previous post :p (theses roads are at the center of the screenshots, you'll quickly see it !)
Zutty wrote: Can't articulated vehciles stop at a non-drive through station? I didn't know that :oops: I write AI more than I actually play the game, clearly!
Huhu, i love to play with AI... i think Convoy, Admiral and your Pathzilla sounds very promising actually so i wish i could help to find bugs !
If you manage to make your AI compatible with articulated vehicules and drive-through stops it'll be very nice !

NB: To know how it spam towns, just start a game with 7 pathzilla, then look at theirs home towns. Watch the population number BEFORE they settle then watch it AFTER they put stops everywhere :D That is astonishing ! This isn't really a major problem because the town grow quickly with transport but it could break the "nice envirronement of sweet little towns" :D (i dunno how to explain it clearly)

H.

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

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

Post by Zutty »

Finaldeath wrote:From your question; the best way to sort if you want to connect towns which are either expensive to connect (bridges! massively expensive per tile) or are too far apart - well, the latter is easy, the former, I'd suggest either a cost calculation (so it can take into account mountains getting in the way and tunnel usage too) or simply limiting the size of bridges to be something like 10-20 tiles max - and not in the pathfinder - let the pathfinder "find" the optimal but if it returns a bridge in it's list of items, don't use it if the bridge is too long.

Would need some tweaking however, but the premise is sound - high water maps really suffer for roads anyway. Of course if you have the cash and it is a reasonable distance, why not build a 100 tile bridge for a profitable route? :)

(and to be honest, long bridges are aesthetically unpleasing anyway :) ).
At the moment I do have a maximum bridge length, but its set to 64 tiles 'cos I don't have a way to deal with a split road network! You see, if the graph somehow breaks in two (like if there are two big islands separated by a wide river), and there are any nodes on the graph that can't be reached from any other node, then the service selection system will stop working. Rather than deal with this I just allowed the AI to build very long bridges.

As for cost calculation, it sounds good but what precisely do you mean? I don't want to have to run the pathfinder over every link just to check for water between points A and B.
PathZilla - A networking AI - Now with tram support.

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 »

You already have an estimated cost to build a road between those nodes - else how could you figure out if the company could afford it in the first place? This is the cost I am referring to - the other types of cost (distance, "up and down", amount of turns) don't affect the profit of a route as much. :)

Not being able to break up the graph at all is rather tough too. Probably needs that fixing before removing any bridges or "unprofitable, unreachable towns" :)
Finaldeath

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

Re: PathZilla (v2) - A road networking AI

Post by Zutty »

Hi guys. I have uploaded version 2 (check first post), which includes a large amount of optimisation and various bug fixes. Performance has been vastly improved, which should make it more user friendly and better in the tournament.

It can now finish all its planning on a 256x256 map within the first day. It takes about 2 weeks on a 512x512 and a month and a half on a 1024x1024. It is also possible to play on a 2048x2048 map now as I have added a limit to number of towns that it will consider. I will change this eventually to system of regional development (one area at a time), but for now at least it is playable.

Interestingly enough it was not the number of towns that caused the problems on a 2048x2048 map, but the actual size it. One of the optimisations that I have implemented invloves the use of a sweep-line that moves from south to north. If you play on a 128x2048 map (i.e. the line is narrow) then it runs fine, but if you play on a 2048x128 map (i.e. the line is wide) then it runs very slowly. In practise a 2048x2048 map with the same number of towns as a 1024x1024 runs noticably slower, simply because the map is bigger. I don;t know if I can improve this, but I'm going to work on other things for the time being.

As for bug fixes, I tried to fix everything you guys spotted. I have stopped it trying to build next to competitor's stations, and prevented it from building 'wierd' roads when the local authority rating gets too low.

It still builds lots of stations and will probably still spam a town to death, but I am working on that! I also plan to implement save/load and add support for difficulty settings in v3.

Thanks to everyone who tested PathZilla and made suggestions. I really appreciate all your input guys. Keep it coming :)
PathZilla - A networking AI - Now with tram support.

dbkblk
Traffic Manager
Traffic Manager
Posts: 154
Joined: 29 Mar 2008 18:38

Re: PathZilla (v2) - A road networking AI

Post by dbkblk »

Erf, i tried a new game with 2 convoy (v9), 2 admiralai, 1 wrightai and 2 pathzilla and i've got errors messages in the pathzilla debug. Look at the pic !

I added a savegame. Happy Debug :D !
Attachments
Non nommé, 4 Fév 1950.png
(187.31 KiB) Downloaded 169 times
BugPathzilla.sav
(148.23 KiB) Downloaded 107 times

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

Re: PathZilla (v2) - A road networking AI

Post by Zutty »

dbkblk wrote:Erf, i tried a new game with 2 convoy (v9), 2 admiralai, 1 wrightai and 2 pathzilla and i've got errors messages in the pathzilla debug. Look at the pic !

I added a savegame. Happy Debug :D !
Wow that was quick! I admire you're commitment to testing dbkblk! :mrgreen:

But DAMN, though! :( I wonder why you didn't get this error with v1.1, as they both have the same structure?! What operating system do you use?

I think I know how to fix this, but it won't be for several hours yet.

Thanks very much dbkblk! :)

Edit: SOD IT! I've hacked together a quick v2.1! I can't test it here at work, as I'm pretty sure I'd get the sack for installing OpenTTD on my work computer!

I'd REALLY appreciate it if some Windows user could quickly test this for me. It need r14025-noai.

Edit: Retracted version 2.1, since its no longer necessary.
Last edited by Zutty on 11 Aug 2008 15:45, edited 1 time in total.
PathZilla - A networking AI - Now with tram support.

dbkblk
Traffic Manager
Traffic Manager
Posts: 154
Joined: 29 Mar 2008 18:38

Re: PathZilla (v2) - A road networking AI

Post by dbkblk »

I've tested it and i got strictly the same :x sorry :S

EDIT: I use Windows XP at my work (hmmm i'm only a "trainee"), mostly Windows Vista (or rarely Ubuntu at my home !). ..and build14025 of course !

EDIT2: I saw Truebrain's post, so it "apparently' could be repaired !

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

Re: PathZilla (v2) - A road networking AI

Post by Zutty »

Aha! OK I've changed the TAR in the first post as per TrueBrain's suggestion. It seem silly to make point release just for a little bit of white space. Could you maybe try it one more time?! :D

Thanks.
PathZilla - A networking AI - Now with tram support.

dbkblk
Traffic Manager
Traffic Manager
Posts: 154
Joined: 29 Mar 2008 18:38

Re: PathZilla (v2) - A road networking AI

Post by dbkblk »

Ok !!! Well done, the AI works now ! I'll make some tests :D

EDIT: I haven't seen any bugs.
Last edited by dbkblk on 11 Aug 2008 15:15, edited 1 time in total.

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

Re: PathZilla (v2) - A road networking AI

Post by Zutty »

dbkblk wrote:Ok !!! Well done, the AI works now ! I'll make some tests :D
Hooray! Thanks. :)

Edit:
dbkblk wrote:EDIT: I haven't seen any bugs.
Cool! Thanks for testing.
PathZilla - A networking AI - Now with tram support.

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

Re: PathZilla (v3) - A road networking AI

Post by Zutty »

I've just uploaded version 3 in the first post.

The biggest change for this release is save/load support. I've achieved this by storing the main data structures (such as road network graphs), and by rolling as much of the AIs state into these structures. There are still circumstances where the AI might behave differently if a process is interupted by a save/load, but these are rare (I think!).

I have also added support for difficulty settings, and an 'aggressive' setting like GeekToo. If you start the AI in easy or medium difficulty, 'aggressive' will be turned off and it will try to avoid building stations near to competitor's property. I hope that this will prevent it from spamming towns to death, if the player so chooses. Also the easier the difficulty, the more it will pause between building things.

As ever, if anyone would like to test this I'd be very grateful :) Many eyes make bug fixing easy!

Next to come is either DTRS/tram support or industry and ECS/PBI. I'll see how my mood takes me! I have plenty of free time next week so I might be able to get something cool done.

Thanks guys.
PathZilla - A networking AI - Now with tram support.

X_stream
Engineer
Engineer
Posts: 18
Joined: 04 Nov 2004 13:29
Location: Bussum => Netherlands
Contact:

Re: PathZilla (v3) - A road networking AI

Post by X_stream »

First off I have to say I really like your AI as I don’t really care for competition performance, but more for aesthetics in single player games.
Haven’t really checked how well your AI compares to others though, so don’t be offended by the above, as far as I know this could also be the most competitive AI out there.

I did find some path finding bug’s, so I made some screenshots for you.

Keep up the good work, I’m looking forward to the drive trough stations and tram support!
Slaborough Market Transport, 27 Feb 1978.png
(270.25 KiB) Downloaded 176 times
Slaborough Market Transport, 3 Mrt 1978.png
(270.87 KiB) Downloaded 166 times
EDIT: Any way to change the image size within the img tags?

EDIT 2: Found something else, the AI seems to handle tramway as normal road, this leads to unconnected stations. I have also added a screenshot of this behaviour.
Cuningville Transport, 15 Aug 1951.png
(181.97 KiB) Downloaded 158 times

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

Re: PathZilla (v3) - A road networking AI

Post by Zutty »

X_stream wrote:First off I have to say I really like your AI as I don’t really care for competition performance, but more for aesthetics in single player games.
Thank you very much, I appreciate that :)

This is exactly what I am going for with PathZilla. I want it to create something that looks nice and realistic, that a human player might create. I know its a lofty goal, but I think if I just go in baby steps I might get somewhere close eventually!
I did find some path finding bug’s, so I made some screenshots for you.
...
EDIT 2: Found something else, the AI seems to handle tramway as normal road, this leads to unconnected stations. I have also added a screenshot of this behaviour.
Ah this is very helpful thanks. The bug in the first two shots is known but I don't have a good solution for it yet. I think its another case of me using API functions in ways they weren't meant for! The second bug is new to me. I'll get that fixed for the next release.
Keep up the good work, I’m looking forward to the drive trough stations and tram support!
Thanks! DTRSs and trams it is then! :D
PathZilla - A networking AI - Now with tram support.

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

Re: PathZilla (v3) - A road networking AI

Post by Zutty »

Here's a bizarre screenshot to whet your appetite!

I might have to tweak the vehicle selection routine to account for eGRVTS!
Attachments
Unnamed, 25th Sep 1920#1.png
A tailback of over 100 horse drawn carriages in an unusual sight!
(489.85 KiB) Downloaded 237 times
PathZilla - A networking AI - Now with tram support.

User avatar
planetmaker
OpenTTD Developer
OpenTTD Developer
Posts: 9414
Joined: 07 Nov 2007 22:44
Location: Sol d

Re: PathZilla (v3) - A road networking AI

Post by planetmaker »

Zutty wrote:Here's a bizarre screenshot to whet your appetite!

I might have to tweak the vehicle selection routine to account for eGRVTS!
What a sight! Probably one of the earliest traffic jams - at least in OpenTTD :D

Besides that, I like an AI which doesn't play me in single player against the wall (though it might still do that, need to test it properly) but takes care for eye candy and good looks :) Good job!

User avatar
Zephyris
Tycoon
Tycoon
Posts: 2831
Joined: 16 May 2007 16:59

Re: PathZilla (v3) - A road networking AI

Post by Zephyris »

It would be good if you can check the vehicle length (ie. number of articulated components) when buying the vehicle - can you do this currently? It may be a useful API feature...

Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 3 guests