A Ship Pathfinder. More...

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

function	WaterHo (StartTile, Slope, ThirdQuadrant=false)
	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)

Author: W. Minchin (MinchinWeb)

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

See also: _MinchinWeb_WBC_; _MinchinWeb_Lakes_; _MinchinWeb_RoadPathfinder_

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:

Add image showing the Cartesian quadrants.

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:

Pathfinder.Ship.nut

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

Member Data Documentation