Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Wed Dec 19, 2018 2:33 am

All times are UTC




Post new topic  Reply to topic  [ 111 posts ]  Go to page 1 2 3 4 5 6 Next
Author Message
PostPosted: Tue Jan 20, 2009 7:43 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
As promised I will post my new PAXLink ai when it has a good chance to not get bankrupt. And I consider that done by now. (at the very bottom you find a screenshot if you want to look on it before reading all this long text)

What makes PAXLink special?
PAXLink is a passenger only AI that builds bus services in towns and then when the town is big enough it builds an inter city airport station next to the town and feeds all the passengers to the airport instead, using transfer orders. Using planes it makes the big money by transporting passengers from one town to another. Actually before I added the inter-city part it struggled hard to not go bankrupt as each bus station cost about 700 pounds per year around 1950, which is a high cost compared to the little money you earn by intra (in city) transport.

Now PAXLink is not just that. While coding it I have had the goal to build a robust AI by not storing any meta state information in Squirrel, instead it reads all state information from the map. - If there is at least 2 bus stops in a town, then we can build a bus depot. If there is at least 2 bus stops and a depot, then we can buy buses. If the town has an inter-city station and it is served by air-vehicles then put the town buses in feeder mode, else use local mode. etc. etc.

Town grid
When building bus stations in town it uses a grid as shown below. The red dots shows the grid tiles and the light blue shows the 8 adjacent tiles. PAXLink will first try the red tile, and if that fails pick one of the light blue based on their score (which involves a few parameters). For a placement to succeed it need to be adjacent to a road tile. The size of the grid depends on town size but also for a station to be built it need to catch enough cargo (to not cost 700/year for no use) and have road access. (the AI don't connect grid bus stations to road currently)
Attachment:
TownGrid.png
TownGrid.png [ 1.27 KiB | Viewed 27549 times ]


A problem right now is that if it only builds one road stop in a town it need to leave it there, as removing it will only cause it to be re-built soon again, as the AI don't store any state information. To fix this I need to rewrite the grid bus stop building to first check that after construction there will be at least 2 stations before building.

To not make multiple PAXLink AIs conflict too much I think about adding a grid offset that then will be picked either by random or by knowing which PAXLink company in order the company is. This offset will then need to be stored in savegame and as a squirrel variable, or the AI might not find its existing stations.

Regulating of network
One of the nice things that it already does is that it expands its bus network as the town grows and updates the bus schedules with the new stations. If a station get far to little cargo (someone destroyed buildings) it removes grid bus stations. Also it regulates the number of buses in a town as well as the number of airplanes on an air-connection.

Todo
The AI is currently neither really good on management of the bus network nor the airplane network. Some TODOs:
  • Don't only check if a town has an airport, also check that the airport
    a) has bus stops
    b) accepts passengers
    before counting it as an inter city station.
  • Check the IC station regularly to see that it has all road stops built
  • Don't build airports that will not accept passengers
  • Buses in feeder mode need a better sort of stations in the order list.
  • Upgrading of airports, and blocking of big planes from using small airports
  • Don't build only one road station in towns, either accept a second with a bit worse score than usual or by building road for a second. Or don't build the first one at all. Having an unserved station in towns seams to give bad rating over time in that town.
  • Increasing and especially decreasing of a vehicle fleet needs more work. (now it just decreases the fleet with capacity 50 when it decides to decrease, which causes problem with vehicles with more than 50 in capacity)
  • Give vehicles with high capacity some extra scores when the capacity limit of a network has been reached, or at least replace low-capacity vehicles with high-capacity vehicles when the number of possible vehicles a network can handle has been reached.
  • Adopt to game settings such as none breakdowns, or even worse if a used mode of transport is disabled by the user.
  • Better calculations of maximum vehicles a network can handle. (now it allows 5 vehicles per station)
  • ... <- there are even more things that can be done

Save/load
Save/load should work due to the design of the AI (no saving of state in squirrel). A half-constructed inter city airport is not fixed on load etc. but on the other hand it can happen because a town refuses to allow it to be completely constructed, so it is not really a save/load problem but can happen from other interruptions too.


Changelog
new in version 4: improved checking for slopes when building grid bus stations (Thanks Yexo for both noticing about the issue and providing code to get the maximum height of a tile)


Attachments:
File comment: Screenshot of town with both feeder bus network and an inter city airport.
Unnamed, 27th Aug 1954.png [209.37 KiB]
Downloaded 795 times
File comment: GPL v2
PAXLink-v4.tar [69.5 KiB]
Downloaded 1448 times

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Top
   
PostPosted: Thu Jan 22, 2009 5:54 pm 
Offline
Transport Coordinator
Transport Coordinator
User avatar

Joined: Wed May 02, 2007 12:29 pm
Posts: 319
Location: Sheffield, England
There goes my plan :) and with extras...

Loading it into my current game, I'l let you know how it goes (^_^)

_________________
Rasing Awareness: Aspergers Syndrome 1 (NAS UK)2 (BBC)3 (YaleDDC)


Something is driving you insane... It is me.


Top
   
PostPosted: Thu Jan 22, 2009 7:04 pm 
Offline
Transport Coordinator
Transport Coordinator

Joined: Sat Jan 03, 2009 5:55 pm
Posts: 301
Hello Zuu!
I tried your PAXLink and i have to say the IC idea is really good.
It goes good with:
-Admiral
-Otvi
-Convoy
-ME ;)

Respect!


Top
   
PostPosted: Thu Jan 22, 2009 10:34 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
AntBUK wrote:
There goes my plan :) and with extras...

Loading it into my current game, I'l let you know how it goes (^_^)

Hope you find it interesting, still much to do on it before it becomes excellent. :)


Timmaexx wrote:
Hello Zuu!
I tried your PAXLink and i have to say the IC idea is really good.
It goes good with:
-Admiral
-Otvi
-Convoy
-ME ;)

Respect!

Thank you for the warm words. Unfortunately it still struggles to make money, due to the added complexity with feeders and that it is neither very good on buses nor airplanes. But I agree that it is a nice idea. ;)

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Fri Jan 23, 2009 11:22 am 
Offline
Transport Coordinator
Transport Coordinator

Joined: Sat Jan 03, 2009 5:55 pm
Posts: 301
I have to add: It doesn't complain with WrightAI.
Every time they build their Airports Wall-To-Wall.
I think this is a new feature by Instant-Join-Stations.
But i don't think its good. Because they snap the passengers of the other Airport.


Top
   
PostPosted: Sat Jan 24, 2009 1:46 pm 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Hi Zuu,

This is a really good idea, nicely implemented. It should be able to turn an enormous profit once its been tuned a bit. I noticed some problems though at later dates when larger airports are available.

In 1950 Paxlink manages to turn a profit after a few months but in 1990 the higher cost of the larger airports means if often goes bankrupt.

Attachment:
paxlink-1990.png [300.01 KiB]
Downloaded 128 times


I've also noticed that with larger airports it sometimes doesn't always build enough bus stops at the airport. Again, it didn't seem to do this in 1950 (unless I'm not looking hard enough). Sometimes no bus stops are joined to it at all, even though the little bits of road were in place, e.g... (this shot is from the attached .sav below)

Image

I imagine this will be easy to fix, but I thought I'd mention it.

I also noticed that the airport bus stop were sometimes not connected to the town.

Attachment:
paxlink-1965.png [299.01 KiB]
Downloaded 151 times

Attachment:
File comment: Saved in r15235 using PAXLink v4 w/ eGRVTS and av8
paxlink-1965.sav [105.99 KiB]
Downloaded 227 times


Hope this helps. Keep up the good work Zuu :)

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


Top
   
PostPosted: Sat Jan 24, 2009 2:23 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
Zutty wrote:
Hi Zuu,

This is a really good idea, nicely implemented. It should be able to turn an enormous profit once its been tuned a bit. I noticed some problems though at later dates when larger airports are available.

In 1950 Paxlink manages to turn a profit after a few months but in 1990 the higher cost of the larger airports means if often goes bankrupt.

Attachment:
paxlink-1990.png


In this picture it failed to build some of the bus stops because the town authorities did not allow it to build all it wanted.

Zutty wrote:
I've also noticed that with larger airports it sometimes doesn't always build enough bus stops at the airport. Again, it didn't seem to do this in 1950 (unless I'm not looking hard enough). Sometimes no bus stops are joined to it at all, even though the little bits of road were in place, e.g... (this shot is from the attached .sav below)

Image


In this case my guess is that the town authorities didn't allow any bus stop, next to the airport.


Zutty wrote:
Attachment:
paxlink-1965.png


Here it didn't build any road stumps nor connected the airport to town. I would guess it had cash problem here.


But the main problem is not the reasons for why it sometimes failed to complete an airport with bus stations and connect it. The main problem is that it does not check from time to time that it is connected and has all desired bus stations built. When that is implemented it can be discussed if it really need that many bus stations at the airport station right from start.


Zutty wrote:
Hope this helps. Keep up the good work Zuu :)

Thanks for your feedback. Mostly it is know issues (see the long todo in the first post), but still I appreciate that you took your time and tested it. The cash-problem, when constructing an airport is not something I have stumbled across myself. But the problem that it easily goes bankrupt is well known. :-)

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Sat Jan 31, 2009 3:06 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Thu Apr 03, 2008 8:18 am
Posts: 215
Nice concept, that works pretty good on my passenger only map. However it had a small hickup at the Hamburg airport.

edit: I let it run for some years and the bug seems to happen more often. It deletes the airport, builds some random roads and planes get stuck there. Other than that i really like it. I usually have inner city bus or tram lines to develop these cities.


Attachments:
paxlink_bug.png [108.77 KiB]
Downloaded 206 times
paxlinkbug.sav [696.36 KiB]
Downloaded 241 times
Top
   
PostPosted: Sat Jan 31, 2009 7:44 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
Roest, thank you for your report.

I would say that it tries to build a grid station (bus stop in town, placed in grid) and for some reason it decides to delete the airport and try to build a road station there.

New version
I have improved the code so it will not try to destroy any own buildings when it tries to build a bus station.

Also I did a few improvements to the decision making of what vehicles to buy and how many aircrafts are maximum allowed between two airports.

Also I have added a setting, similar to AdmiralAI that let one decide if debug signs should be built or not. This setting is off by default, and has exactly the same name as AdmiralAI (as I copied the code that tells OpenTTD about the setting from AdmiralAI). And I guess from users perspective it would be good if AIs uses the same name of things.

This new version have been uploaded to BaNaNaS, but is also available here in case someone has problems to use the in-game content service.
Attachment:
PAXLink-v5.tar [70.5 KiB]
Downloaded 239 times

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Sun Feb 01, 2009 10:10 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Thu Apr 03, 2008 8:18 am
Posts: 215
Thanks for the update, the airport bug seems to be gone. Though it still shows some weird road building behavior (Hamburg in the savegame).

Also when using grid layouts for towns, would it be possible to prevent the AI from building at locations where the town is supposed to expand?


Attachments:
paxlinkstrangeroads.sav [744.4 KiB]
Downloaded 222 times
Top
   
PostPosted: Sun Feb 01, 2009 10:42 am 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
The reason for the strange roads it builds, but no road station I strongly believe is because it does currently not detect when it fails because town authority rejects building a road station, in which case it should not continue to try other places.

About town expansion. I think I added some code to give a end of a straight road reduced score when it gives score to the 8 possible neighbors around a grid tile. Currently it will build it on the grid tile if that is possible, and only if that fails check the 8 neighbor tiles. However I realize that my code that should make it less likely that it places road stops at the end of a straight road will not work if there is a curve or a junction at the tile infront of the road stop.

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Sun Feb 01, 2009 11:04 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Thu Apr 03, 2008 8:18 am
Posts: 215
It does indeed have apalling ratings in many towns. Not sure why it is that way tho. With a decent service i should at least get a good rating.

Can an AI read the current grid setting? Then i should be easy enough to prevent strange road building and wrong placement of stations.


Top
   
PostPosted: Sun Feb 01, 2009 11:52 am 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Roest wrote:
It does indeed have apalling ratings in many towns. Not sure why it is that way tho. With a decent service i should at least get a good rating.

Can an AI read the current grid setting? Then i should be easy enough to prevent strange road building and wrong placement of stations.


Do you mean "Economy" > "Towns" > "Select town-road layout". That can be queried with...

Code:
local n = AIGameSettings.GetValue("economy.town_layout").tointeger();


n == 3 for 2x2 or 4 for 3x3.

Edit: Oops, little mistake!

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


Top
   
PostPosted: Sun Feb 01, 2009 3:23 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
While working on next version I have encountered a strange behavior of AIEngine. The main problem I have is that my AI fails to filter out the cargo lifter in the Av8 GRF, which can not be refitted to passengers. And since it has good running cost vs capacity it thinks it is a good air-engine to build.

When debugging my code I decided to print the contents of the engine_list. And got quite strange results for some engines in the AI debug window. (See attached screenshot) Code used to generate list of engine names:
Code:
local engine_list = AIEngineList(vehicle_type);

for(local i = engine_list.Begin(); engine_list.HasNext(); i = engine_list.Next())
{
   AILog.Info("Engine name: " + AIEngine.GetName(i));
}

Attachment:
Unnamed, 26th Oct 2951.png [109.02 KiB]
Downloaded 138 times


To sort out vehicles which can not carry passengers I use the following code:
Code:
engine_list.Valuate(AIEngine.CanRefitCargo, Helper.GetPAXCargo());
engine_list.KeepValue(1);


Which seam to work on everything but the cargo lifter from Av8. Buses uses the same code to get best engine. The only difference is the value of vehicle_type.


Edit: The only GRFs I had was Av8 and Stolen trees.
Also I have just tested without any GRFs and there is no such errors with engine names without any GRFs.

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Sun Feb 01, 2009 4:31 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
@Roest:

Fixing the placement of stations is not at top of my list currently. I have added code so it shouldn't keep on trying if local authorities refuses in version 6.

@Zutty:
Thanks for pointing that out. Still I guess you need to figure out from the map at which offset the town grid is. Or is towns simply building roads when tile_x%3 == 0 || tile_y%3 == 0 on 3x3 layouts?


New version: 6
Yep, time for another new version. This version has some changes:
* Stop trying to build stations at grid point when local authorities refuses to allow construction of depot.
* The management of bus orders (in feeder mode) have been improved. The main improvement lays on the routine that updates the orders from how they look currently to a list of desired orders. The new routine gives a order list that looks exactly like the given list. (the old code just added missing stations at the bottom). The change in behavior of the AI is that now when new stations is added the grid stations are sorted by the grid order, so buses will always take one row at the time of the grid.


What I am currently aiming at is to improve the management of vehicles. Even with the small improvement of bus station ordering it is still far from a good order of the orders. There is many possibilities here. But since passengers are transfered at the airport I want to have an efficient route, as passengers will not pay extra to go back and fourth around in the town.
  • Solve the travel sales man (TSP) problem for all the grid stations plus the airport. There are many heuristics for TSP that could be used.
  • Use some heuristics to solve a variant of the vehicle routing problem. The VRP problem is much more complex that TSP which might cause performance problems. Especially take into account that this will need to run for every town maybe once a year at least, or when a new road station is built.
  • Use the grid that PAXLink already has. With few buses just solve the TSP problem or just go down the first row, up next, down next, etc. When the number of buses grows above 2 per row, then let each row become a route. So if there are two rows, half of the vehicles will only service the first row and half of the vehicles will only service the second row.

For travel sales man problem and vehicle routing problem, the cost between all nodes need to be calculated. Using manhattan distance this shouldn't bee to expansive. But using a road path-finder to find the exact distance might become to heavy on bigger towns.

For balancing vehicles into different routes using a method based on optimization it is important that the input is relatively stable or the found solution will change from time. I would love to have access to the number of passengers that entered a given station last month, or last year. A sum of those who got served and those who did not get served. Currently you can get the number of waiting cargo, but it is harder to determine how much cargo did you move away from the station. Using last years income of all buses in a town and quite some calculations you might be able to quantify how much cargo a town puts onto the airport.

The difficulty to get stable input to an optimization based method to load balance the buses speaks for using only optimization to plan the routes based on geometric costs. And then from time to time do load basing based on number of waiting passengers.


Yet another thing that makes things interesting is that PAXLink can not just max out its feeder bus services, since it doesn't
get paid a single pound for passengers that get pushed out to the airport, if they never get onto an aircraft away from the city. So it need to balance the capacity of the feeder service against the capacity of the inter city services.

Blah blah blah.. :D Much to consider :)

Here is your version 6 if you can't use the in-game download:


Attachments:
PAXLink-v6.tar [78 KiB]
Downloaded 226 times

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Top
   
PostPosted: Sun Feb 01, 2009 4:34 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Thu Apr 03, 2008 8:18 am
Posts: 215
Zuu wrote:
Thanks for pointing that out. Still I guess you need to figure out from the map at which offset the town grid is. Or is towns simply building roads when tile_x%3 == 0 || tile_y%3 == 0 on 3x3 layouts?


yes afaik


Top
   
PostPosted: Sun Feb 01, 2009 4:42 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Thu Feb 09, 2006 7:15 pm
Posts: 3815
Roest wrote:
Zuu wrote:
Thanks for pointing that out. Still I guess you need to figure out from the map at which offset the town grid is. Or is towns simply building roads when tile_x%3 == 0 || tile_y%3 == 0 on 3x3 layouts?
yes afaik
The correct answer is no.
It's %4 for 3x3 layouts (3 houses, then a road). Furthermore the grid 'originates' from the town center, i.e. town->xy. So the correct calculation would be something like abs(tile_x - TileX(town->xy)) % 4 || /* same but for y */.


Top
   
PostPosted: Sun Feb 01, 2009 4:56 pm 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Rubidium wrote:
Roest wrote:
Zuu wrote:
Thanks for pointing that out. Still I guess you need to figure out from the map at which offset the town grid is. Or is towns simply building roads when tile_x%3 == 0 || tile_y%3 == 0 on 3x3 layouts?
yes afaik
The correct answer is no.
It's %4 for 3x3 layouts (3 houses, then a road). Furthermore the grid 'originates' from the town center, i.e. town->xy. So the correct calculation would be something like abs(tile_x - TileX(town->xy)) % 4 || /* same but for y */.

All towns are aligned with each other though and the common grid seems to originate at 0,0. The following works perfectly for me...

Code:
local n = AIGameSettings.GetValue("economy.town_layout").tointeger();
local dx = abs(tile % AIMap.GetMapSizeY());
local dy = abs(tile / AIMap.GetMapSizeY());
local onGrid = (dx % n == 0 || dy % n == 0);

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


Top
   
PostPosted: Sun Feb 01, 2009 7:05 pm 
Offline
Director
Director
User avatar

Joined: Tue Jan 22, 2008 4:33 pm
Posts: 565
Zuu wrote:
Solve the travel sales man (TSP) problem for all the grid stations plus the airport. There are many heuristics for TSP that could be used.

Heres a very simple TSP solver written in Java. I haven't tried a Squirrel implementation yet...

Attachment:
File comment: Requires Java 6. Remove the ".txt" so the extension is just .jar
TSPSolve.jar.txt [11.09 KiB]
Downloaded 222 times


It uses some very crude stochastic optimisation with a very basic heuristic, but for a small number of nodes it works quite well.

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


Top
   
PostPosted: Wed Feb 18, 2009 8:42 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4538
Location: /home/sweden
Update,
  • Avoid/forbid building on town grid based on AISetting
  • Don't try building road stations or depots on steep slopes. (removes building of roads to steep slopes that then can't be used anyways)
  • Up to date with the API changes some days ago

When avoid building bus stops and depots on town grid is enabled then neighbour tiles to the station grid get a big penalty if they are on the town road grid. It will still try with the station grid tile first, and only if that fail try with the 8 neighbours.

When you enable the forbid option, then the function that builds road stations and depots will simply return false if the building tile is on town grid. If you enable this, keep in mind that the AI only searches 9 tiles for each bus station grid location. This option removes up to 5 tiles of those 9.


Attachments:
PAXLink-v7.tar [80 KiB]
Downloaded 260 times

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 111 posts ]  Go to page 1 2 3 4 5 6 Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2018 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2018.
Hosted by Zernebok Hosting.