Ship Pathfinder (MinchinWeb's MetaLibrary)

[MinchinWeb]

When looking to expand my AI (WmDOT) last spring, I decided to add some ships. First though, I needed a pathfinder. I decided to create a pathfinder based on geometry rather than using the A* approach I used for roads. My pathfinder works like this:

• To initialize, a path with two points (the start and end) is added to the pathfinder. For each following loop:
  1. The shortest (unfinished) path is pulled from the pathfinder
  2. The path is walked, point-to-point, until land is reached
  3. If land is reached, two lines are drawn at right angles starting the midpoint (of the land). If water if reached, that point is then added to the path, and the path is added to the 'unfinished' list.
  4. If the shortest path is on the 'finished' list (i.e. all water), then that path is returned. Otherwise, the loop restarts.

With simple geometries, it works fast and well. However, on complex geometries, it doesn't work as well as I would like. The other problem I have is that the geometry only works on the basis that the start and end points are in the same waterbody, and so I created WaterbodyCheck() Lakes() to confirm this is the case; however it adds running time to the whole pathfinder. One the plus side, building the path is very simple: just build buoys at each point along the path!

So I post this here to share my work that it might be helpful/inspire someone else, and if anyone has suggestions on how to get around having to use WaterbodyCheck or how to speed up the pathfinder or WaterbodyCheck Lakes.

The pathfinder is included in my MetaLibrary (also available on Bananas). I have attached a small AI below that you can use to see to help you understand how the pathfinder works.

Update (2014-02-28): v7 of MetaLibrary has been release that includes Lakes. The AI has been updated to test the workings of the Ship Pathfinder, Waterbody Check, and Lakes. To see all the signs, set Debug Level to 8.

[skippern]

Are there still any development on this? I would like to see a proper Ship Pathfinder in the library

Further, I would like the distance between buoys to be larger, maybe have a parameter for this, and make sure that existing buoys are reused to avoid cluttering with buoys.

Also, check to see if both origin and destination is in the same body of water, if not, build a canal, same if they are in the same body of water, but have a significant detour build a canal short-cut.

Would also be nice if there was a function to re-check existing routes, so that a newly built canal can be used if it makes the distance shorter. Too tight buoy distnace and this becomes more complicated, if the buoy distance is large enough this might be automatic

[MinchinWeb]

Hi skippern! I'm glad you've taken an interest in my Ship Pathfinder. Unfortunately, this has not seen much attention of late. My last update to this seems to be '2012-06-23', bringing the Ship Pathfinder up to version 4. What work I have done in OpenTTD more lately has been focused on the road pathfinder and trying to build streetcar stations.

Part of the reason it has not seen a lot of updates is it works well enough for me as implemented in WmDOT, where the purpose was just to keep the AI from going bankrupt.

What I need/want to do next is rewrite the WaterBodyCheck that serves to determine if two tiles are in the same waterbody (in effect, if a ship can sail between them). I would also like to improve the documentation of the whole library to make it easier for others to use.

Part of the struggle is I haven't found an quick way to test the Ship Pathfinder in any but the simplest cases.

In regards to buoy placement: The pathfinder works by 'drawing' a series of lines between the start (origin) and the destination. A buoy will be placed in every corner. If one of these straight lines is long enough, buoys will be placed along the line. The default maximum distance between buoys (along a straight line) is set at 50 tiles. If you want to change it, you can:

Code: Select all

MyShipPathfinder.set(max_buoy_spacing, 25)

Be careful setting the distance between buoys too high; ship pathfinding (the movement of ships) in OpenTTD is very computational intensive, increasing exponentially as the distance between the ship and its next target location increases.

In regards to canals: This is a fairly complex problem in figuring out where to build a canal, working around obstacles, and determining whether the cost makes it worthwhile to still build a canal. One would probably have to build a 'canal pathfinder' to do these things well. It is a problem I've thought about, but haven't developed any code for (yet).

In regards to rechecking routes: why not just rerun the pathfinder? The would tell you if a new, shorter route was available. More complicated would be moving all the ships over to the new route.

My code for this is available online at: https://github.com/MinchinWeb/openttd-m ... r.Ship.nut
Or download MetaLibrary through the OpenTTD's in-game downloader.

If you make any improvements or additions, I would be happy to add them to my library. Good luck with your ship AI!

[Zuu]

Part of the struggle is I haven't found an quick way to test the Ship Pathfinder in any but the simplest cases.

Maybe I'm missing some critical thing, but why not make a test AI that wait for two signs "start" and "end" which will then path find using the ship pathfinder between these two tiles? Then you can test different scenarios by defining start/end tiles yourself rather than trying to come up with code that tests the situations that you want to test.

For other configuration, you can use in-game editable AI settings or sign settings (check for presence of a sign with some value).

[MinchinWeb]

...why not make a test AI that wait for two signs "start" and "end" which will then path find using the ship pathfinder between these two tiles?

The AI attached in the first post does exactly that.

The issue is, once it's running, to sort thought the (sometimes hundreds of) iterations and points to figure out why it's not working the way I expected it to.

Zuu (or anyone else, for the matter), do you know a way (on Windows) to capture the debug output of an AI in an external text tile?

[Zuu]

Zuu (or anyone else, for the matter), do you know a way (on Windows) to capture the debug output of an AI in an external text tile?

1. Use convert.exe to convert OpenTTD.exe from a windows to a console application.
2. In a terminal:

Code: Select all

openttd.exe > out.txt 2>err.txt

I'm not sure if the relevant output that you look for will end up in out.txt or err.txt. The first one will contain stdout and the second stderr which are the two output streams from console application that usually both are displayed in the terminal.

You will also need to supply the usual OpenTTD command line arguments to set the script debug level to a high enough level so that the AILog messages end up in the program log.

[R2dical]

I think a library ship pathfinder would be great! There was another ship pathfinder posted that built canals and locks, based on an old version of the library pathfinder. I made some headway updating it, mainly in bridges functionality and some optimising that went in the road lib one, but put on hold after I got stuck on the "unconventional" use of callbacks to build canals.

Anyway, maybe some of that could be used to add to this pathfinder?

[skippern]

Part of the struggle is I haven't found an quick way to test the Ship Pathfinder in any but the simplest cases.

I am almost done making a good heightmap that will give you a lot of water, and together with my upcoming ship AI that will give you a lot of opertunity for stress-testing your ship pathfinder. Happy to help

[MinchinWeb]

Zuu, thanks for the tip! I hope having textfile log output will make it easier to debug the pathfinder.

R2dical, if you have some success in canal building code (and you want to), I would be happy to add it to my library.

skippern, I look forward to your heightmap!

[R2dical]

R2dical, if you have some success in canal building code (and you want to), I would be happy to add it to my library.

Yeah ok ill take a look at it. Its still WIP and not working yet, the tricky bit is getting the actual path though...

Maybe something else useful I have is my current ship pathfinder. Based on A* but has some changes for speed and only water tiles, also uses every 5 tiles (by default) instead of direct neighbours to greatly speed up the process (at the cost of accuracy). It can find a path of 10000 or so tiles in 150 ticks but no guarantee the path is valid (as a "land bridge" of < 5 tiles width will be "skipped" by each node). As most water bodies are larger than this in most cases this doesn't matter. Also can hang if there is no possible path, but can maybe be given a limit after which to assume there is no path. I thought it could be used for your "waterbody check".

[MinchinWeb]

A new version (v.7) of MetaLibrary has been released, and most of the updates center around the Ship Pathfinder. Waterbody Check has been replaced by Lakes, which serves the same purpose, but approaches the problem from a different direction. Lakes remembers which tiles it has already looked at, making subsequent checks much faster. A recheck of an already checked route takes ~4 ticks.

Another benefit of Lakes is it is much better at deciding a route simply can't be found and telling you so.

My ship pathfinder has been updated to use Lakes. By doing so, it will check that each turning point is in the same waterbody as the start and end points before adding it to a possible path. (Before, it was too time consuming to do this, and it was skipped and we hoped for the best).

The test AI in the first post has been updated to support testing Lakes. To see all of the signs Lakes puts out to show you what it's doing, you'll need to set the Debug Level to 8.

R2dical: With an A* pathfinder, I found increasing '_distance_penalty' was an interesting way to speed up finding a path. I find a value of 5 works well for road pathfinders if you don't care how direct a path it finds. Your idea skipping five tiles at a time is interesting. Have you put together code to go from your pathfinder result to a ship running on that path yet?

I was thinking of updating my Ship Pathfinder with something like you've suggested, where it considers tiles on a 4x4 grid rather than every tile. I haven't gotten that quite yet...

[R2dical]

I have done some more work since and the idea has evolved somewhat from the initial idea as a means to see if two tiles are in the same waterbody. Now I use it as a way to plot the "macro path" then just join the dots with landscaping, as it were. Also I have planned to include my canals methods in the process rather than a separate thing. Currently the code is incomplete and kind of a mess, but I have a detailed outline for how it will work:

1) Run water pathfinder with step size n = 10 and land costing disabled.
This pathfinder rapidly checks iff all tiles are water n distance apart using aystar. Land tiles are not allowed. (updated of the version I posted above to include land cost and changed to include diagonals (like railpathfinder), which is significantly quicker than the previous version.
Null return means tiles are not connected (subject to n accuracy) by same water body. Now we either try again with n++ or switch to canal pathfinder (goto 2).
True means we found a prospective path (goto 3).

2) Run canal pathfinder.
Uses the water pathfinder but allows for "tunnels" across land masses based on modified road pathfinder, these are then later joined with canals based on modified road builder (goto 3).

3) Run path builder.
This does a few things, on a path object returned by the pathfinders:
- If a node is flagged as "tunnel", build locks at each end and run canal builder between them (goto 4, then resume 3).
- If distance between nodes is > 1, run water pathfinder with n = 1, and enable land costing (goto 1). This is to ensure path is viable by a more traditional pathfinding way, and seeing of there is any land blocking the route by landscaping any "skipped" land bridges. In most cases this is not needed so its quite fast.
- If path has an associated land cost, run landscaping for each node function to ensure each is at sea level (or whatever baseline level).
- Every x tiles, build a buoy and add to a list object which stores the final "route" for ships. This can also be used for demolish.
- If we fail at any point, like we hit a ship or some new thing in the way etc, this has some recover capability. Error handle (wait for ship to move, etc) or find new path from last successful tile (goto 1).

4) Run canal builder.
For building canals between two locks. Very similar to road builder and includes some recover ability for runtime error encounters and demolish on hard fail.

Once this is all finished we have a table of tiles with buoys on. This should be saved so we can demolish routes to cleanup map, and possibly integrate a feature into pathfinder to reuse existing paths by detecting nearby buoys. List is also used to create the ships routes.

The non-canal parts are mostly done so will see if I can't have a testable version up. I think something like this is nice as it can rapidly and accurately build ship routes across long distances, especially now since 4048*2 maps are in trunk