[WIP] The quest for a better ship pathfinder

[Kernigh]

Pathfinding for ships is too slow. YAPF uses too much cpu. Ships seem to be the most common cause of "lag" in multiplayer games. It happens so often with Reddit server 1 that some players join the server, find an unplayable game with a low frame rate, and immediately blame the boats. I saw a game become unplayable because someone had perhaps 50 or 100 boats using too much cpu for a simple journey of a few hundred tiles along the coast. I looked at the map, and the path seemed obvious to me, but YAPF used too much cpu. My slower cpu lagged the server's faster cpu, and my client tried to catch up by skipping frames. The mouse cursor became jerky and the game became unplayable.

It's too easy to wreck a multiplayer game with ships. OpenTTD requires Manhattan distance under 130 tiles when adding orders to ships, but doesn't enforce this limit after the last order. So the player with the long coastal route used buoys from dock 1 to dock 2, but forgot to use buoys for the return trip. Over time, the ships bunched together. There was much lag as the largest bunch of ships left dock 2 for the return trip to dock 1. This lag lessened as the ships approached dock 1. YAPF recalculates the route for each ship in a bunch, even if they're all going the same way. Also, YAPF recalculates the route whenever each ship enters the next tile, even if the route doesn't change.

For my own ships, I might build a chain of buoys every 10 or 20 tiles, and order my ships along the buoys in both directions. I do pathfinding with buoys because YAPF can't do enough pathfinding. I would prefer ships without buoys, so I'm on the quest for a better ship pathfinder.


I start my quest with a 4-year-old patch from March 2012: JazzyJaffa's region pathfinder. It divides the map into regions of perhaps 100 tiles each. It modifies YAPF so each ship finds a long path of regions to its destination, and then a short path of tiles into the next 2 regions. (This can make the path slightly longer as the ship moves toward the center tile of each region, when a shorter path would stay closer to the coast.) I updated the patch for newer OpenTTD trunk. The patch didn't know about aqueducts, and my test game crashed as soon as a ship left an aqueduct and asked for a route. I continued to have different problems with aqueducts until I added enough logic to handle them.

region_pathfind_r27523.patch

(63.72 KiB) Downloaded 182 times

I attach patch for OpenTTD trunk r27523. This patch modifies the format of save files. Vanilla OpenTTD can't load save files from this patch. Also, this patch can't load save files from the 4-year-old patch. Even if the load seems to work, it might corrupt your game.

Changes from region_pathfind_r24052.patch:

• Added the last 2 commits from http://github.com/benjeffery/openttd (branch region)
• Edited source.list to add the new files.
• Edited docs/landscape.html to show where tiles store the region index.
• In RegionDescriptionWater, replaced most of the logic in IsRoutable() and IsPassable() with calls to GetTileTrackStatus(), so that more tiles become routable and passable. Needed this for aqueducts.
• Connected regions when the other end of an aqueduct is in another region.
• Extended StartTileModification() to accept 2 tiles, for both sides of an aqueduct.
• Allowed rail tiles to have regions, because some rail tiles have half water. A rail tile stores its region index in m6 and m7.
• Added checks for tile modifications when building an aqueduct and when making a rail tile with half water (either by building the rail or flooding the tile).
• Added typedef uint16 RegionID;
• Simplified the reservation of ID numbers for regions.
• Added CRegion<TRD>::Get(RegionID) so that a public field can become private.
• In CRegionManager, removed Regions() and AddRegion().
• In CRegionManager::RefindRegion(), fix a bug where the region manager removed the wrong region from a set, and left a pointer to a deleted region in the set.
• Made other tweaks such as removing extra #include lines.

There are still some problems:

• It might still be possible to crash the game. Certain changes to the map need StartTileModification(t) before the change, and EndTileModification() after the change. If these calls are missing, then regions become corrupt. I don't like how the patch stores the region index in the tile data. Most water tiles use m2, water tiles with depots use m3/m4, station tiles use m3/m4, aqueducts use m2, and rail tiles use m6/m7. Because of this mess, tiles tend to forget their region during changes. StartTileModification(t) remembers the tile's region so EndTileModification() can pass the region to the region manager.
• Sometimes two regions are connected but a ship can't use the connection. This causes conflicts between the region pathfinder and tile pathfinder, as the region pathfinder tries to use the faulty connection and the tile pathfinder tries to make a long detour around it. If I forbid 90 degree turns, I can build pathfinder traps using them. These traps might cause lag (if the tile pathfinder's detour is too long), cause ships to become lost, or send ships along infinite loops.

Mardhattan Transport, 1st Oct 1969.sav

(127.34 KiB) Downloaded 180 times

I also attach my test game, Mardhattan Transport. This save file is from OpenTTD 1.5.1, so you may open it with or without the patch. There are planes (for making money) and ships. Some boats follow a twisty route of canals and aqueducts. Other boats go across the map. There are a few buoys, but you can remove them if you click Tennton Buoy, click its ship button, and remove all buoy orders from those ships. There are only 3 order lists that use buoys, and all of them go through Tennton Buoy.

[Eddi]

another approach that i once thought about:

separate pathfinding from ship movement, instead call the pathfinder upon placing a buy[dock,shipyard,...] and store the paths to all "nearby" destinations (in some off-map storage). ship pathfinding would then be run upon arriving at a buoy, and only calculate which buoys to hop over, then take the cached path.

[Alberth]

Perhaps Jump Point Search?

"Online Graph Pruning for Pathfinding on Grid Maps", by Daniel Harabor and Alban Grastien, 25th National Conference on Artificial Intelligence. AAAI, 2011

The article cannot be used as-is, since it assumes a tile moves out in 8 directions. In OpenTTD, an edge moves out in 6 directions instead. I think it can be converted though.

[mrjack2]

Could you have player-created "shipping lanes" for ships to follow? (Or else have the pathfinder generate shipping lanes to follow)? That way you could reduce it to roughly the equivalent of rail/road pathfinding.

[cnww]

Sorry to bump a thread that's been dormant for a while, but I had a thought and this was the most recent related thread that Google came up with.

Why not implement a simple infinite-range A* pathfinder for ships, and then cache the results?

IMHO individual trip pathfinding made more sense in the original TTDX: Maps (and thus paths) were small and 64MB of RAM was more than you could reasonably expect a player to have, but these days we've got massively larger maps and even handheld systems generally have more than 1GB of RAM.

Unlike trains and road vehicles, ships don't need to respond to changing conditions other than player actions: The optimal path between two docks will remain exactly the same until some construction or landscaping action changes it. That being the case, upwards of 99% of the time a ship departing a dock will be using an origin/destination pair recently used by another ship (or the same ship, considering that paths are reversible), and wouldn't need to do any pathfinding at all.

On a really large map (and slow computer) it might take a few seconds to calculate a long route, but in most cases it would be possible to do the calculations ahead of time (e.g. A ship just arrived at dock A, the next item in its timetable is a conditional order jump to either dock B or C, so I'll go ahead and calculate the paths A<->B and A<->C now while the ship is loading/unloading).

Whenever a water tile (sea/canal/river/lock) is added or removed, all the existing cached paths could be flagged as "dirty" resulting in them being subject to a quick re-check (to see that they're still valid) the next time they're used, and a full re-evaluation (to see if they're still optimal) when there's CPU time available. Even then, the game only needs to do one path-finding operation per route rather than one per trip.

Thoughts?

[jfs]

That actually sounds like a reasonable idea. Assuming ships rarely change their orders lists, the available water routes rarely change, and you don't use dynamic orders, you have a clear set of station-station pairs you need routes for. Those default routes between station pairs can be cached (don't need to store in the savegame) and be followed whenever possible. If the ship needs to stray from the cached route, it can do that for a bit, then look for a path leading back onto the intended route and resume following that.

Another way to handle it might also be using "virtual buoys": Generate long line segments from the calculated route, and use the original pathfinder (or even something simpler than that) to attempt to sail in a straight line between the waypoints. Don't require the ship to touch the waypoints exactly, like buoys don't require either, so ships can attempt to evade and not sail on top of each other. The list of waypoints likely takes very little memory, but generating it can be somewhat slow and take a bunch of memory.

[Alberth]

The cpu killer is 'lost ships', which have no route, and no destination. Caching won't do much good in that case.

One alternative could be JPS, which is faster than A*. One problem is that the original article uses the center of a tile, while openttd uses an edge to branch to different directions, so it needs an adjustment in the algorithm. Haven't considered that puzzle yet.

[jfs]

Oh but I have a very simple solution to destination-less ships: Stop, don't move, no pathdinding needed. As in, actually stop (red flag), and prevent from starting again until there is a valid destination.

Does the JPS algorithm (I haven't looked at it yet) directly depend on every node having 8 exits? If not, then just using an addressing mode for tile edges so they can be nodes should be enough?

[Eddi]

Oh but I have a very simple solution to destination-less ships: Stop, don't move, no pathdinding needed. As in, actually stop (red flag), and prevent from starting again until there is a valid destination.

that doesn't work, as you must run the pathfinder to determine whether you are lost, and you must run the pathfinder again to find out whether the destination became valid

One problem is that the original article uses the center of a tile, while openttd uses an edge to branch to different directions, so it needs an adjustment in the algorithm.

surely that just means you're operating on the dual graph? so just flip vertices and edges?

[Alberth]

One problem is that the original article uses the center of a tile, while openttd uses an edge to branch to different directions, so it needs an adjustment in the algorithm.

surely that just means you're operating on the dual graph? so just flip vertices and edges?

Not entirely, from the center of a tile, you can always move in 8 directions. From an edge, you can only move in 6 directions (ie not parallel with the edge direction).

The solution shouldn't be that dificult though. The basic step in JPS is a pure X or Y movement (ie NE/SE/NW/SW in openttd). The combined X/Y movement then scans the area. In their setup you spawn one X and one Y search after each diagonal step. In OpenTTD I think you should do either an X or an Y search every diagonal step, since moving from edge to edge (horizontal to vertical or vice versa) is half the distance of moving from center to center.

[jfs]

Oh but I have a very simple solution to destination-less ships: Stop, don't move, no pathdinding needed. As in, actually stop (red flag), and prevent from starting again until there is a valid destination.

that doesn't work, as you must run the pathfinder to determine whether you are lost, and you must run the pathfinder again to find out whether the destination became valid

Okay so three cases that probably need individual handling:
1. Ship has empty orders list, and has not been ordered to go to a depot..
2. The destination for the current order is not a valid station/stop, someone deleted it.
3. The destination is valid, but it's not possible to find any route to it from the current location.

Cases 1 and 2 are easy to detect. I propose handling both by stopping the ship and disallow starting it again until it has a valid order. If there is a lingering station sign, maybe try to path towards that.

Case 3 requires an exhaustive pathfinding run to detect. When it's detected, set a counter flag on the ship, counting down from e.g. 10 days, and only attempt pathing to the destination again after the counter has expired. While the counter is set, the ship won't move. Additionally, keep a count of how many pathing attemps have failed in a row. When the second and fifth attempts fail, send a news message to the player. When the tenth attempt fails, send a news message to the player and stop the ship entirely. When restarting the ship, only allow it to start if it can find a path to the destination, and apply the same pathing-attempt-delay to these start attempts, such that a failed start attempt blocks you from attempting to start the ship for another 10 days.

[Eddi]

Cases 1 and 2 are easy to detect. I propose handling both by stopping the ship and disallow starting it again until it has a valid order. If there is a lingering station sign, maybe try to path towards that.

those are not the currently problematic cases anyway.

[wallyweb]

Could you have player-created "shipping lanes" for ships to follow? (Or else have the pathfinder generate shipping lanes to follow)? That way you could reduce it to roughly the equivalent of rail/road pathfinding.

I became frustrated by ships not following a shorter direct diagonal path between ports and ships bumping against coasts while looking for the next port. So I created Sea Lanes, Channels and Buoys, an object based solution. It does not address pathfinder issues. For long distances, objects do not support drag and drop so it might take time to set up a route. Bottom line is that it cuts down on shipping time for diagonal routes.

[prissi]

I would suggest a look at the optimised simutrans pahtfinder for ships, which tries first something like lines and then search from the endpoints of these lines. That dramatically reduces the number of visited nodes without the need to do regions. (It is an implementation of the previously mentioned paper from 2011)

Seethe code at https://github.com/aburch/simutrans/blo ... j/route.cc from line 300 on.

[_dp_]

Oh but I have a very simple solution to destination-less ships: Stop, don't move, no pathdinding needed. As in, actually stop (red flag), and prevent from starting again until there is a valid destination.

that doesn't work, as you must run the pathfinder to determine whether you are lost, and you must run the pathfinder again to find out whether the destination became valid

It requires a player action to make destination valid. And it would be a pretty easy change to cache lost state between specific player actions.