MinchinWeb's MetaLibrary  v.9 Library functions of OpenTTD AI writers.
_MinchinWeb_ShipPathfinder_ Class Reference

A Ship Pathfinder. More...

class  Cost

class  Info

## Public Member Functions

function InitializePath (source, goal)
Initializes the pathfinder. More...

function FindPath (iterations)
Runs the pathfinder. More...

function GetPathLength ()
Runs over the path to determine its length. More...

function CountPathBuoys ()
Returns the number of potential buoys that may need to be built. More...

function BuildPathBuoys ()
Build the buoys along the path. More...

function GetPath ()
Get the current path. More...

function OverrideWBC ()
Skip Waterbody Check. More...

## Static Public Member Functions

function LandHo (TileA, TileB)
Find land! More...

To the sea! (Find water) More...

## Private Member Functions

constructor ()

function _PathToTilesArray (PathIndex)
Turns a path into an index to tiles. More...

function _InsertPoint (TileIndex)
Inserts a point into the point list. More...

function _PathLength (PathIndex)

## Private Attributes

_heap_class = import("queue.fibonacci_heap", "", 3)

_WBC_class = _MinchinWeb_Lakes_
Class used to check if the two points are within the same waterbody. More...

_WBC = null
actual instance of class used to check if the points are within the same waterbody More...

_max_cost = null
The maximum (pathfinder) cost for a route. More...

_cost_tile = null
The (pathfinder) cost for a single tile. More...

_cost_turn = null
The (pathfinder) cost that is added to _cost_tile if the direction changes. More...

cost = null
Used to change the (pathfinder) costs. More...

_max_buoy_spacing = null
The maximum spacing between buoys. More...

_first_run = null

_first_run2 = null

_waterbody_check = null

_points = null
Used to store points considered by the pathfinder. Stored as TileIndexes. More...

_paths = null
Used to store the paths the pathfinder is working with. Stored as indexes to _points. More...

_clearedpaths = null
Used to store paths that have already been cleared (i.e. all water). More...

_UnfinishedPaths = null
Used to sort in-progress paths. More...

_FinishedPaths = null
Used to store finished paths. More...

_testedpaths = null

_mypath = null
Used to store the path after it's been found for Building functions. More...

_running = null
Is the pathfinder running? More...

info = null

## Detailed Description

A Ship Pathfinder.

Version
v.5 (2014-02-28)
Since
MetaLibrary v.2

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.
• 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.
3. 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 _MinchinWeb_Lakes_ (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!

Note
_MinchinWeb_WBC_ has been depreciated in favour of _MinchinWeb_Lakes_.
Depends On:
Fibonacci Heap v.3
_MinchinWeb_WBC_
_MinchinWeb_Lakes_
Todo:
Add image showing how the Ship Pathfinder works

Definition at line 55 of file Pathfinder.Ship.nut.

## Member Function Documentation

 function _MinchinWeb_ShipPathfinder_::_InsertPoint ( TileIndex )
private

Inserts a point into the point list.

Does a check to insure that the same point does not show up twice at different indexes.

Returns
The index of the (added) point.

Definition at line 588 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::_PathLength ( PathIndex )
private

Definition at line 484 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::_PathToTilesArray ( PathIndex )
private

Turns a path into an index to tiles.

Just the start, end, and turning points.

Definition at line 558 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::BuildPathBuoys ( )

Build the buoys along the path.

Build the buoys that may need to be built. Changes this._mypath to be the list of these buoys.

Definition at line 625 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::constructor ( )
inlineprivate

Definition at line 81 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::CountPathBuoys ( )

Returns the number of potential buoys that may need to be built.

Definition at line 601 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::FindPath ( iterations )

Runs the pathfinder.

Parameters
 iterations Number of cycles to run the pathfinder before returning. If set to -1, will run until a path is found.
Note
One of the first things the pathfinder will do is confirm the start and end points are in the same waterbody. If iterations is not set to -1, it will return after completing this. Therefore, if iterations is set to a finite amount, this function will need to be called at least twice to return a path.
Returns
null if a path cannot be found.
the path, if a path is found.
false if the pathfinder is unfinished.

Definition at line 282 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::GetPath ( )

Get the current path.

Returns
The path, as currently held by the pathfinder.

Definition at line 656 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::GetPathLength ( )

Runs over the path to determine its length.

Returns
Path length in tiles

Definition at line 569 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::InitializePath ( source , goal )
inline

Initializes the pathfinder.

Parameters
 source Starting tile, as a TileID as the first element of an array. goal Ending tile, as a TileID as the first element of an array.
Note
Assumes only one source and goal tile.

Definition at line 113 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::LandHo ( TileA , TileB )
static

Find land!

Starting one two water tiles, this function will walk the line between them, starting at the outside ends, and return the tiles where it hits land.

Parameters
 TileA A water tile TileB Another water tile
Returns
A two element, one dimensional array of the tile indexes of the first land tiles hit after starting at TileA and TileB.
[-1, -1] if the path is all water (no land).

Definition at line 493 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::OverrideWBC ( )

Skip Waterbody Check.

This function skips the Waterbody Check at the beginning of the Ship Pathfinder run. This is intended for if you have already run Waterbody Check or otherwise know that the two points are in the same waterbody.

Warning
The Ship Pathfinder's behaviour without this check in place is not tested, as the Ship Pathfinder assumes the two points are in the same waterbody.... Use at your own risk.
Note
This is less of an issue with the introduction of Lakes. While Lakes may take a long time on the first run, by reusing the pathfinder, subsequent checks of the same path are very fast (in the order of 4 ticks).

Definition at line 666 of file Pathfinder.Ship.nut.

 function _MinchinWeb_ShipPathfinder_::WaterHo ( StartTile , Slope , ThirdQuadrant = false )
static

To the sea! (Find water)

Starts at a given tile and then walks out at the given slope until it hits water.

Parameters
 StartTile A land tile. Slope The slope of the line to follow out. ThirdQuadrant Whether to follow the slope in the third or fourth quadrant.
Returns
The first water tile hit.
Todo:

Move to _MinchinWeb_Marine_

Definition at line 536 of file Pathfinder.Ship.nut.

## Member Data Documentation

 _MinchinWeb_ShipPathfinder_::_clearedpaths = null
private

Used to store paths that have already been cleared (i.e. all water).

Definition at line 73 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_cost_tile = null
private

The (pathfinder) cost for a single tile.

Definition at line 61 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_cost_turn = null
private

The (pathfinder) cost that is added to _cost_tile if the direction changes.

Definition at line 62 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_FinishedPaths = null
private

Used to store finished paths.

Definition at line 75 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_first_run = null
private

Definition at line 68 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_first_run2 = null
private

Definition at line 69 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_heap_class = import("queue.fibonacci_heap", "", 3)
private

Definition at line 57 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_max_buoy_spacing = null
private

The maximum spacing between buoys.

Definition at line 65 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_max_cost = null
private

The maximum (pathfinder) cost for a route.

Definition at line 60 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_mypath = null
private

Used to store the path after it's been found for Building functions.

Definition at line 77 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_paths = null
private

Used to store the paths the pathfinder is working with. Stored as indexes to _points.

Definition at line 72 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_points = null
private

Used to store points considered by the pathfinder. Stored as TileIndexes.

Definition at line 71 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_running = null
private

Is the pathfinder running?

Definition at line 78 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_testedpaths = null
private

Definition at line 76 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_UnfinishedPaths = null
private

Used to sort in-progress paths.

Definition at line 74 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_waterbody_check = null
private

Definition at line 70 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_WBC = null
private

actual instance of class used to check if the points are within the same waterbody

Definition at line 59 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::_WBC_class = _MinchinWeb_Lakes_
private

Class used to check if the two points are within the same waterbody.

Definition at line 58 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::cost = null
private

Used to change the (pathfinder) costs.

Definition at line 63 of file Pathfinder.Ship.nut.

 _MinchinWeb_ShipPathfinder_::info = null
private

Definition at line 79 of file Pathfinder.Ship.nut.

The documentation for this class was generated from the following file: