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