PAXLink - a PAX-only AI that uses feeder systems

[Zuu]

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)

TownGrid.png (1.27 KiB) Viewed 35623 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)

[AntBUK]

There goes my plan and with extras...

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

[Timmaexx]

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!

[Zuu]

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.

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.

[Timmaexx]

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.

[Zutty]

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.

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)



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.

paxlink-1965.png

(299.01 KiB) Downloaded 151 times

paxlink-1965.sav

Saved in r15235 using PAXLink v4 w/ eGRVTS and av8

(105.99 KiB) Downloaded 415 times

Hope this helps. Keep up the good work Zuu

[Zuu]

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.

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.

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)

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

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.

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.

[Roest]

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.

[Zuu]

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.

PAXLink-v5.tar

(70.5 KiB) Downloaded 439 times

[Roest]

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?

[Zuu]

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.

[Roest]

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.

[Zutty]

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: Select all

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

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

Edit: Oops, little mistake!

[Zuu]

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: Select all

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));
}

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: Select all

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.

[Zuu]

@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.. Much to consider

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

[Roest]

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

[Rubidium]

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 */.

[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?

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: Select all

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);

[Zutty]

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...

TSPSolve.jar.txt

Requires Java 6. Remove the ".txt" so the extension is just .jar

(11.09 KiB) Downloaded 313 times

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

[Zuu]

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.