Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Tue Oct 24, 2017 12:08 am

All times are UTC




Post new topic  Reply to topic  [ 27 posts ]  Go to page 1 2 Next
Author Message
PostPosted: Fri Dec 23, 2011 3:24 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Update (January 10, 2015) - Version 9 released!, both AI and GS versions (details)

Inspired by Zuu's SuperLib, I have released my own library: a collection of functions pulled from my AI, WmDOT. I hope this can help someone speed up their own AI writing.

At present, the library includes:
  • Ship Pathfinder - more details
  • Road Pathfinder, based on NoAI Team's. The pathfinder uses the A* search pattern and includes functions to find the path, determine its cost, and build it. Can bridge over rivers, canals, and railroad tracks.
  • Dominion Land System - a wrapper on the road pathfinder to encourage roads to be built on a grid.
  • Line Walker - walk the map between two points, or start at a given point and walk out at a given slope.
  • Spiral Walker - allows you to define a starting point, and then 'walk' all the tiles in a spiral outward. It was originally used to find a buildable spot for my HQ in WmDOT, but is useful for many other things as well.
  • Log - help (dynamically) control the amount of debugging output displayed
  • Atlas - given a list of 'sources' and 'attractions', will weight the combinations and generate a list of pairs to connect.
  • Lakes - serves to check whether two points are in the same waterbody (i.e. a ship could travel between them). It maintains a memory of previous calls, making re-checks very fast. It can be called separately, but was originally designed as a pre-run check for my Ship Pathfinder.
  • Array functions.
  • Marine and ship related functions.
  • Extra functions, for things like math, map geometry, ship support, etc.

Upcoming:
  • Pathfinder improvements

The library is available below or on Bananas.

Documentation is available at http://minchin.ca/openttd-metalibrary/.


Attachments:
File comment: MinchinWeb's MetaLibrary v.9 for AI's
MetaLib-9-AI.tar [260 KiB]
Downloaded 196 times
File comment: MinchinWeb's MetaLibrary v.9 for Game Scripts
MetaLib-9-GS.tar [260 KiB]
Downloaded 118 times

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Last edited by MinchinWeb on Sun Jan 11, 2015 12:23 am, edited 11 times in total.
Top
   
PostPosted: Fri Dec 23, 2011 3:29 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
ReadMe from version 1:
Code:
MinchinWeb's MetaLibrary Read-me
v.1, r.123, 2011-04-28
Copyright © 2011 by W. Minchin. For more info, please visit
    http://openttd-noai-wmdot.googlecode.com/

-- About MetaLibrary ----------------------------------------------------------
MetaLibrary started as a collection of functions from my AI, WmDOT. The hope is
    to provide a collection of classes and functions that will be useful to
    other AI writers. Your comments, suggestions, and bug reports are welcomed
    and encouraged!

-- Requirements ---------------------------------------------------------------
WmDOT requires OpenTTD version 1.1 or newer. This is available as a free
    download from OpenTTD.org
As dependances, WmDOT also requires:
    - Binary Heap, v.1 ('Queue.BinaryHeap-1.tar')
    - Fibonacci Heap, v.2
    - Graph.AyStar, v.6

-- Installation ---------------------------------------------------------------
The easiest (and recommended) way to install MetaLibrary is use OpenTTD's
    'Check Online Content' interface. Search for 'WmDOT.' If you have not
    already installed the required libraries, OpenTTD will prompt you to
    download them at the same time. This also makes it very easy for me to
    provide updates.
Manual installation can be accomplished by putting the
    'MinchinWebs_MetaLibrary-1.tar' file you downloaded in the
    '..\OpenTTD\ai\library'  folder. If you are manually installing,
    the libraries mentioned above need to be in the same folder.

To make use of the library in your AIs, add the line:
        import("util.MinchinWeb", "MetaLib", 1);
    which will make the library available as the "MetaLib" class (or whatever
    you change that to).
   
-- Included Functions ---------------------------------------------------------
Detailed descriptions of each of the function is given within the code files.
    See them for further details of each function.

[Arrays.nut] v.2
    Array.Create1D(length)
        .Create2D(length, width)
        .Create3D(length, width, height)
        .ToString2D(InArray)
            - this is useful to output an array to the debugging output
        .ContainedIn1D(InArray, SearchValue)
        .ContainedIn2D(InArray, SearchValue)
        .ContainedIn3D(InArray, SearchValue)
            - these return true or false, depending on if the value can be
                found
        .Find1D(InArray, SearchValue)
        .Find2D(InArray, SearchValue)
        .Find3D(InArray, SearchValue)
            - returns the location of the first time the SearchValue is found;
                the 1D version returns an interger, the 2D and 3D versions
                return an array with the indexes
        .RemoveValueAt(InArray, Index)
        .InsertValueAt(InArray, Index, Value)
        .ToStringTiles1D(InArrayOfTiles)
            - this is useful to output an tile array to the debugging output
        .FindPairs(InArray2D, SearchValue1, SearchValue2)
        .ContainedInPairs(InArray2D, SearchValue1, SearchValue2)
            - The idea is to provide an array of pairs, and find out if
                SearchValue1 and SearchValue2 is listed as one of the pairs
               
[Extras.nut] v.1
    Extras.DistanceShip(TileA, TileB)
            - Assuming open ocean, ship in OpenTTD will travel 45° angle where
                possible, and then finish up the trip by going along a cardinal
                direction
        .SignLocation(text)
            - Returns the tile of the first instance where the sign matches the
                given text
        .MidPoint(TileA, TileB)
        .Perpendicular(SlopeIn)
        .Slope(TileA, TileB)
        .Within(Bound1, Bound2, Value)
        .WithinFloat(Bound1, Bound2, Value)
        .MinAbsFloat(Value1, Value2)
        .MaxAbsFloat(Value1, Value2)
        .AbsFloat(Value)
            - Returns the absolute Value as a floating number if one is
                provided
        .Sign(Value)
            - Returns +1 if the Value >= 0, -1 Value < 0
        .MinFloat(Value1, Value2)
        .MaxFloat(Value1, Value2)
        .MinAbsFloatKeepSign(Value1, Value2)
        .MaxAbsFloatKeepSign(Value1, Value2)
       
[Pathfinder.Road.nut] v.7
This file is licensed under the original license - LGPL v2.1
    and is based on the NoAI Team's Road Pathfinder v3
The pathfinder uses the A* search pattern and includes functions to find the
    path, determine its cost, and build it.
   
    RoadPathfinder.InitializePath(sources, goals)
            - Set up the pathfinder
        .FindPath(iterations)   
            - Run the pathfinder; returns false if it isn't finished the path
                if it has finished, and null if it can't find a path
        .cost.[xx]
            - Allows you to set or find out the pathfinder costs directly. See
                the function for valid entries
        .Info.GetVersion()
            .GetMinorVersion()
            .GetRevision()
            .GetDate()
            .GetName()
                - Useful for check provided version or debugging screen output
        .PresetOriginal()
        .PresetPerfectPath()
        .PresetQuickAndDirty()
        .PresetCheckExisting()
        .PresetMode6()
        .PresetStreetcar()
            - Presets for the pathfinder parameters
        .GetBuildCost()
            - How much would it be to build the path?
        .BuildPath()
            - Build the path
        .GetPathLength()
            - How long is the path? (in tiles)
        .LoadPath(Path)
            - Provide your own path
        .InitializePathOnTowns(StartTown, EndTown)
            - Initializes the pathfinder using the seed tiles of the given towns   
        .PathToTilePairs()
            - Returns a 2D array that has each pair of tiles that path joins
        .TilesPairsToBuild()
            - Similar to PathToTilePairs(), but only returns those pairs where
                there isn't a current road connection
               
[Spiral.Walker.nut] v.2
The SpiralWalker class allows you to define a starting point, and then 'walk'
    all the tiles in a spiral outward. It was originally used to find a
    buildable spot for my HQ in WmDOT, but is useful for many other things as
    well.
   
    .SpiralWalker()
    .SpiralWalker.Start(Tile)
            - Sets the starting tile for SpiralWalker
        .Reset()
            - Clears all data within the SprialWalker
        .Restart()
            - Sends the SpiralWalker back to the starting tile
        .Walk()
            - Move out, one tile at a time. Returns the Tile the SpiralWalker
                is on
        .GetStart()
            - Returns the tile the SpiralWalker is starting on
        .GetStage()
            - Returns the Stage the SpiralWalker is on (basically, the line
                segments its completed plus one; it takes four to complete a revolution)
        .GetTile()
            - Returns the Tile the SpiralWalker is on
        .GetStep()
            - Returns the number of steps the SpiralWalker has done
       
[Waterbody.Check.nut] v.1
Waterbody check is in effect a specialized pathfinder. It serves to check
    whether two points are in the same waterbody (i.e. a ship could travel
    between them). It is optimized to run extremely fast (I hope!). It can be
    called separately, but was originally designed as a pre-run check for my
    Ship Pathfinder (not quite finished, but to also be included in this
    MetaLibrary).
       
    WaterbodyCheck.InitializePath(sources, goals)
            - Set up the pathfinder
        .FindPath(iterations)   
            - Run the pathfinder; returns false if it isn't finished the path
                if it has finished, and null if it can't find a path
        .cost.[xx]
            - Allows you to set or find out the pathfinder costs directly. See
                the function for valid entries       

-- Version History ------------------------------------------------------------
Version 1 [2011-04-28]
    Initial public release; released to coincide with the release of WmDOT v6
    Included Arrays v.2, Extras v.1, Road Pathfinder v.7, Spiral Walker v.2,
        and Waterbody Check v.1

-- Roadmap --------------------------------------------------------------------
These are features I hope to add to MetaLibrary shortly. However, this is subject to
    change without notice. However,I am open to suggestions!
v.2        Ship Pathfinder
        Atlas Generator (input possible sources and destinations and get the
            best pair)
           
-- Known Issues ---------------------------------------------------------------
Pathfinding can take an exceptionally long time if there is no possible path.
    This is most often an issue when the two towns in question are on different
    islands.
SpiralWalker skips the tile [+1,0] relative to ths starting tile.

-- Help! It broke! (Bug Report) -----------------------------------------------
If MetaLibrary cause crashes, please help me fix it! Save a screenshot (under
    the ? on the far right of the in-game toolbar) and, if possible, the
    offending AI, and report the bug to either:
                            http://www.tt-forums.net/viewtopic.php?f=65&t=57903
                            http://code.google.com/p/openttd-noai-wmdot/issues/

-- Helpful Links --------------------------------------------------------------
Get OpenTTD!                                                    www.openttd.org
TT-Forums - all things Transport Tycoon related               www.tt-forums.net
MetaLibrary's thread on TT-Forums: release announcements, bug reports,
    suggestions, and general commentary
                            http://www.tt-forums.net/viewtopic.php?f=65&t=57903
WmDOT on Google Code: source code, and WmDOT: Bleeding Edge edition
                                    http://code.google.com/p/openttd-noai-wmdot
To report issues:            http://code.google.com/p/openttd-noai-wmdot/issues

My other projects (for OpenTTD):
    WmDOT (an AI)           http://www.tt-forums.net/viewtopic.php?f=65&t=53698
    Alberta Town Names      http://www.tt-forums.net/viewtopic.php?f=67&t=53313
    MinchinWeb's Random Town Name Generator
                            http://www.tt-forums.net/viewtopic.php?f=67&t=53579

-- License -------------------------------------------------------------------
MetaLibrary (unless otherwise noted) is licensed under a
    Creative Commons-Attribution 3.0 license.

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Last edited by MinchinWeb on Fri Dec 23, 2011 4:28 pm, edited 1 time in total.

Top
   
PostPosted: Fri Dec 23, 2011 3:03 pm 
Offline
Tycoon
Tycoon

Joined: Wed Aug 26, 2009 6:33 am
Posts: 2493
Location: Poland
What about integrating this functions into SuperLib?

_________________
Correct me If I am wrong - PM me if my English is bad
AIAI - AI for OpenTTD


Top
   
PostPosted: Fri Dec 23, 2011 4:33 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Kogut wrote:
What about integrating this functions into SuperLib?
I'm not opposed to that, but Zuu and I would have to figure out a few details first...

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Thu Jan 12, 2012 3:12 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 2 has been released!

Added a Ship Pathfinder, a Line Walker, and a number of ship support functions. Full details below:

Code:
MinchinWeb's MetaLibrary Read-me
v.2, r.200, 2012-01-11
Copyright © 2011-12 by W. Minchin. For more info, please visit
    http://openttd-noai-wmdot.googlecode.com/

-- About MetaLibrary ----------------------------------------------------------
MetaLibrary started as a collection of functions from my AI, WmDOT. The hope is
    to provide a collection of classes and functions that will be useful to
    other AI writers. Your comments, suggestions, and bug reports are welcomed
    and encouraged!

-- Requirements ---------------------------------------------------------------
WmDOT requires OpenTTD version 1.1 or newer. This is available as a free
    download from OpenTTD.org
As dependances, WmDOT also requires:
    - Binary Heap, v.1      ('Queue.BinaryHeap-1.tar')
    - Fibonacci Heap, v.2   ('Queue.FibonacciHeap-2.tar')
    - Graph.AyStar, v.6     ('Graph.AyStar-6.tar')

-- Installation ---------------------------------------------------------------
The easiest (and recommended) way to install MetaLibrary is use OpenTTD's
    'Check Online Content' inferface. Search for 'MetaLibrary.' If you have not
    already installed the required dependancy libraries, OpenTTD will prompt you
    to download them at the same time. This also makes it very easy for me to
    provide updates.
Manual installation can be accomplished by putting the
    'MinchinWebs_MetaLibrary-2.tar' file you downloaded in the
    '..OpenTTDailibrary'  folder. If you are manually installing,
    the libraries mentioned above need to be in the same folder.

To make use of the library in your AIs, add the line:
        import("util.MinchinWeb", "MetaLib", 2);
    which will make the library available as the "MetaLib" class (or whatever
    you change that to).
   
-- Noteable Changes in Version 2 ----------------------------------------------
 * addition of the Ship Pathfinder, the Line Walker class, and Atlas class
 * added Marine class functions
 * added Constants, Station, and Industry classes fucntions to Extra.nut
 * some additions to the Array and Extra classes
 * RoadPathfinder.GetPath() will return the path as stored by the pathfinder
 * DistanceShip() moved to Marine class
 
-- Version History ------------------------------------------------------------
Version 2 [2012-01-11]
    Major update; released to coincide with the release of WmDOT v7
    Added the Ship Pathfinder (v2), Line Walker (v1), and Atlas (v1) classes
    Added Constants, Station, Industry, and Marine (v1) class functions
    Updated Extras (v.2) and Arrays (v.3)
   
Version 1 [2011-04-28]
    Initial public release; released to coincide with the release of WmDOT v6
    Included Arrays v2, Extras v1, Road Pathfinder v7, Spiral Walker v2,
        and Waterbody Check v1

-- Roadmap --------------------------------------------------------------------
These are features I hope to add to MetaLibrary shortly. However, this is
    subject to change without notice. However, I am open to suggestions!
v3      Road Pathfinder improvements (prebuild bridges and tunnels, upgrade
            bridges, bridge over rivers and railroad tracks)
        Switch buoy and water depot building to Spiral Walker
           
-- Known Issues ---------------------------------------------------------------
Pathfinding can take an exceptionally long time if there is no possible path.
    This is most often an issue when the two towns in question are on different
    islands.
SpiralWalker skips the tile [+1,0] relative to ths starting tile.

-- Help! It broke! (Bug Report) -----------------------------------------------
If MetaLibrary cause crashes, please help me fix it! Save a screenshot (under
    the ? on the far right of the in-game toolbar) and, if possible, the
    offending AI, and report the bug to either:
                            http://www.tt-forums.net/viewtopic.php?f=65&t=57903
                            http://code.google.com/p/openttd-noai-wmdot/issues/

-- Helpful Links --------------------------------------------------------------
Get OpenTTD!                                                    www.openttd.org
TT-Forums - all things Transport Tycoon related               www.tt-forums.net
MetaLibrary's thread on TT-Forums: release announcements, bug reports,
    suggetions, and general commentary
                            http://www.tt-forums.net/viewtopic.php?f=65&t=57903
WmDOT on Google Code: source code, and WmDOT: Bleeding Edge edition
                                    http://code.google.com/p/openttd-noai-wmdot
To report issues:            http://code.google.com/p/openttd-noai-wmdot/issues

My other projects (for OpenTTD):
    WmDOT (an AI)           http://www.tt-forums.net/viewtopic.php?f=65&t=53698
    Alberta Town Names      http://www.tt-forums.net/viewtopic.php?f=67&t=53313
    MinchinWeb's Random Town Name Generator
                            http://www.tt-forums.net/viewtopic.php?f=67&t=53579

-- Licence -------------------------------------------------------------------
MetaLibrary (unless otherwise noted) is licenced under a
    Creative Commons-Attribution 3.0 licence.

-- Included Functions ---------------------------------------------------------
Detailed descirptions of each of the function is given within the code files.
    See them for further details of each function.

[Arrays.nut] v.3 - Updated
    Array.Create1D(length)
         .Create2D(length, width)
         .Create3D(length, width, height)
         .ToString1D(InArray)
         .ToString2D(InArray)
            - this is useful to output an array to the debugging output
         .ContainedIn1D(InArray, SearchValue)
         .ContainedIn2D(InArray, SearchValue)
         .ContainedIn3D(InArray, SearchValue)
         .ContainedIn1DIn2D(InArray2D, SearchArray1D)
            - these return true or false, depending on if the value can be
                found
         .Find1D(InArray, SearchValue)
         .Find2D(InArray, SearchValue)
         .Find3D(InArray, SearchValue)
            - returns the location of the first time the SearchValue is found;
                the 1D version returns an interger, the 2D and 3D versions
                return an array with the indexes
         .RemoveValueAt(InArray, Index)
         .InsertValueAt(InArray, Index, Value)
         .ToStringTiles1D(InArrayOfTiles, ArrayLength = false)
            - this is useful to output an tile array to the debugging output
         .FindPairs(InArray2D, SearchValue1, SearchValue2)
         .ContainedInPairs(InArray2D, SearchValue1, SearchValue2)
            - The idea is to povide an array of pairs, and find out if
                SearchValue1 and SearchValue2 is listed as one of the pairs
         .Compare1D(InArray1D, TestArray1D)

[Atlas.nut] v.1 - New
The Atlas takes sources (departs) and attractions (destinations) and then
    generates a heap of pairs sorted by rating. Ratings can be generated based
    on distance alone or can be altered by user defined ratings (e.g. industry
    productions or town populations).
   
    enum ModelType
    {
        ONE_D,
        DISTANCE_MANHATTAN,
        DISTANCE_SHIP,
        DISTANCE_AIR,
        DISTANCE_NONE,
        ONE_OVER_T_SQUARED,
    }

    Atlas()
    Atlas.Reset()
            - Resets the Atlas (dumps all entered data)
        .AddSource(Source, Priority)
            - Adds a source to the sources list with the given priority
            - Assumes Source to be a TileIndex
        .AddAttraction(Attraction, Priority)
            - Adds an attraction to the attraction list with the given priority
            - Assumes Source to be a TileIndex
        .AddBoth(AddedTile, Priority)
            - Adds a tile to the BOTH the sources list and the attractions
                list with the (same) given priority
        .RunModel()
            - Takes the provided sources and destinations and runs the
                selected traffic model, populating the 'pairs' heap
        .Pop()
            - Returns the top rated pair as an array and removes the pair from
                the model
        .Peek()
            - Returns the top rated pair (as an array) but DOES NOT remove the
                pair from the model
        .Count()
            - Returns the amount of items currently in the list.
        .Exists
            - Check if an item exists in the list. Returns true/false.
        .SetModel(newmodel)
            - Sets the model type to the provided type
        .GetModel()
            - Returns the current model type (as the enum)
        .PrintModelType(ToPrint)
            - given a ModelType, returns the string equivalent
        .ApplyTrafficModel(StartTile, StartPriority, EndTile, EndPriority,
                Model)
            - Given the start and end points, applies the traffic model and
                returns the weighting (Smaller weightings are considered better)
            - This function is indepedant of the model/class, so is useful if
                you want to apply the traffic model to a given set of points. It
                is what is called internally to apply the model
        .SetMaxDistance(distance = -1)
            - Sets the maximum distance between sources and attractions to be
                included in the model
            - Negative values remove the limit
        .SetMaxDistanceModel(newmodel)
            - Sets the model type to the provided type
            - Used to calculate the distance between the source and attraction
                for applying maxdistance
            - DISTANCE_NONE is invalid. Use MinchinWeb.Atlas.SetMaxDistance(-1)
                instead.
            - ONE_OVER_T_SQUARED is invalid.
         
[Extras.nut] v.2 - Updated
    Constants.Infinity() - returns 10,000
             .FloatOffset() - returns 1/2000
             .Pi() - returns 3.1415...
             .e() - returns 2.7182...
             .IndustrySize() - returns 4
             .InvalidIndustry() - returns 0xFFFF (65535)
             .InvalidTile() - returns 0xFFFFFF
             .MaxStationSpread() - returns the maximum station spread
             .BuoyOffset() - returns 3
             .WaterDepotOffset() - return 4
       
    Extras.SignLocation(text)
            - Returns the tile of the first instance where the sign matches the
                given text
          .MidPoint(TileA, TileB)
          .Perpendicular(SlopeIn)
          .Slope(TileA, TileB)
          .Within(Bound1, Bound2, Value)
          .WithinFloat(Bound1, Bound2, Value)
          .MinAbsFloat(Value1, Value2)
          .MaxAbsFloat(Value1, Value2)
          .AbsFloat(Value)
            - Returns the absolute Value as a floating number if one is
                provided
          .Sign(Value)
            - Returns +1 if the Value >= 0, -1 Value < 0
          .MinFloat(Value1, Value2)
          .MaxFloat(Value1, Value2)
          .MinAbsFloatKeepSign(Value1, Value2)
          .MaxAbsFloatKeepSign(Value1, Value2)
          .NextCardinalTile(StartTile, TowardsTile)
            - Given a StartTile and a TowardsTile, will given the tile
                immediately next(Manhattan Distance == 1) to StartTile that is
                closests to TowardsTile
               
    Industry.GetIndustryID(Tile)
            - AIIndustty.GetIndustryID( AIIndustry.GetLocation(IndustryID) )
                sometimes fails because GetLocation() returns the northmost
                tile of the industry which may be a dock, heliport, or not
                part of the industry at all.
            - This function starts at the tile, and then searchs a square out
            (up to Constants.StationSize) until it finds a tile with a valid
            TileID.

    Station.IsCargoAccepted(StationID, CargoID)
            - Checks whether a certain Station accepts a given cargo
            - Returns null if the StationID or CargoID are invalid
            - Returns true or false, depending on if the cargo is accepted
 
[Line.Walker.nut] - New
The LineWalker class allows you to define a starting and endpoint, and then
    'walk' all the tiles between the two. Alternately, you can give a starting
    point and a slope.
   
    LineWalker()
    LineWalker.Start(Tile)
            - Sets the starting tile for LineWalker
        .End(Tile)
            - Sets the ending tile for LineWalker
            - If the slope is also directly set, the start and end tiles
                define a bounding box
        .Slope(Slope)
            - Sets the slope for LineWalker
            - Assumes that the slope is in the first or second quadrant unless
                ThirdQuadrant == true
        .Reset()
            - Resets the variables for the LineWalker
        .Restart()
            - Moves the LineWalker to the orginal starting position
        .Walk()
            - 'Walks' the LineWalker one tile at a tile
        .IsEnd()
            - Returns true if we are at the edge of the bounding box defined
                by the Starting and Ending point
        .GetStart()
            - Returns the tile set as the LineWalker start
        .GetEnd()
            - Returns the tile set as the LineWalker end
 
[Marine.nut] v.1 - New
    Ship.DistanceShip(TileA, TileB)
            - Assuming open ocean, ship in OpenTTD will travel 45° angle where
                possible, and then finish up the trip by going along a
                cardinal direction
        .GetPossibleDockTiles(IndustryID)
            - Given an industry (by IndustryID), searches for possible tiles to
                build a dock and returns the list as an array of TileIndexs
            - Tiles given should be checked to ensure that the desired cargo is
                still accepted
        .GetDockFrontTiles(Tile)
            - Given a tile, returns an array of possible 'front' tiles that a
                ship could access the dock from
            - Can be either the land tile of a dock, or the water tile
            - Does not test if there is currently a dock at the tile
            - Might do funny things if the tile given is next to a river (i.e.
                a flat tile next to a water tile)
        .BuildBuoy(Tile)
            - Attempts to build a buoy, but first checks the box within
                MinchinWeb.Constants.BuoyOffset() for an existing buoy, and
                makes sure there's nothing but water between the two. If no
                existing buoy is found, one is built.
            - Returns the location of the existing or built bouy.
            - This will fail if the Tile given is a dock (or any tile that
                is not a water tile)
        .BuildDepot(DockTile, Front)
            - Attempts to build a (water) depot, but first checks the box
                within Constants.WaterDepotOffset() for an existing depot, and
                makes sure there's nothing but water between the depot and
                dock. If no existing depot is found, one is built.
            - Returns the location of the existing or built depot.
            - This will fail if the DockTile given is a dock (or any tile that
                is not a water tile)
 
[Pathfinder.Road.nut] v.7
This file is licenced under the originl licnese - LGPL v2.1
    and is based on the NoAI Team's Road Pathfinder v3
The pathfinder uses the A* search pattern and includes functions to find the
    path, determine its cost, and build it.
   
    RoadPathfinder.InitializePath(sources, goals)
            - Set up the pathfinder
        .FindPath(iterations)   
            - Run the pathfinder; returns false if it isn't finished the path
                if it has finished, and null if it can't find a path
        .Cost.[xx]
            - Allows you to set or find out the pathfinder costs directly. See
                the function for valid entries
        .Info.GetVersion()
             .GetMinorVersion()
             .GetRevision()
             .GetDate()
             .GetName()
                - Useful for check provided version or debugging screen output
        .PresetOriginal()
        .PresetPerfectPath()
        .PresetQuickAndDirty()
        .PresetCheckExisting()
        .PresetMode6()
        .PresetStreetcar()
            - Presets for the pathfinder parameters
        .GetBuildCost()
            - How much would it be to build the path?
        .BuildPath()
            - Build the path
        .GetPathLength()
            - How long is the path? (in tiles)
        .LoadPath(Path)
            - Provide your own path
        .GetPath()
            - Returns the path stored by the pathfinder
        .InitializePathOnTowns(StartTown, EndTown)
            - Initializes the pathfinder using the seed tiles of the given towns   
        .PathToTilePairs()
            - Returns a 2D array that has each pair of tiles that path joins
        .TilesPairsToBuild()
            - Similar to PathToTilePairs(), but only returns those pairs where
                there isn't a current road connection

[Pathfinder.Ship.nut] v.2 - New
The ship pathfinder takes two water tiles, checks that they are in the same
    waterbody, adn then returns an array of tiles that a ship would have to
    travel via to travel from one to the other.
   
    ShipPathfinder.InitializePath(source, goal)
            - is provided with a single source and single goal tile (but both
                are supplied as arrays)
        .Info.GetVersion()
            .GetRevision()
            .GetDate()
            .GetName()
        .Cost.[xx]
            - Allows you to set or find out the pathfinder costs directly. See
                the function for valid entries
        .FindPath(iterations)
            - Run the pathfinder; returns false if it isn't finished the path
                if it has finished, and null if it can't find a path
        .LandHo(TileA, TileB)
            - walks between the two tiles and returns a two item array
                containing the first land tile hit from either direction
        .WaterHo(StartTile, Slope, ThirdQuadrant = false)
            - Starts at a given tile and then walks out at the given slope
                until it hits water
            - "ThirdQuadrant" refers to whether to search the first and second
                quadrants (0°-90°, 271°-359°) or the third and fourth
                quadrants (91°-270°)
            - LandHo() and WaterHo() are static functions and thus likely to be
                moved to a different sublibrary in the near future
        .GetPathLength()
            - Runs over the path to determine its length
        .CountPathBuoys()
            - Returns the number of potential buoys that may need to be built
        .BuildPathBuoys()
          - Build the buoys that may need to be built
            - changes the internal storage of the path to be the list of these
                buoys
        .GetPath()
            - Returns the path, as currently held by the pathfinder      
               
[Spiral.Walker.nut] v.2
The SpiralWalker class allows you to define a starting point, and then 'walk'
    all the tiles in a spiral outward. It was originally used to find a
    buildable spot for my HQ in WmDOT, but is useful for many other things as
    well.
   
    .SpiralWalker()
    .SpiralWalker.Start(Tile)
            - Sets the starting tile for SpiralWalker
        .Reset()
            - Clears all data within the SprialWalker
        .Restart()
            - Sends the SpiralWalker back to the starting tile
        .Walk()
            - Move out, one tile at a time. Returns the Tile the SpiralWalker
                is on
        .GetStart()
            - Returns the tile the SpiralWalker is starting on
        .GetStage()
            - Returns the Stage the SpiralWalker is on (basically, the line
                segments its completed plus one; it takes four to complete a revolution)
        .GetTile()
            - Returns the Tile the SpiralWalker is on
        .GetStep()
            - Returns the number of steps the SpiralWalker has done
       
[Waterbody.Check.nut] v.1
Waterbody check is in effect a specialized pathfinder. It serves to check
    whether two points are in the same waterbody (i.e. a ship could travel
    between them). It is optimized to run extremely fast (I hope!). It can be
    called separately, but was originally designed as a pre-run check for my
    Ship Pathfinder (not quite finished, but to also be included in this
    MetaLibrary).
       
    WaterbodyCheck.InitializePath(sources, goals)
            - Set up the pathfinder
            - source and goals must be arrays
        .FindPath(iterations)   
            - Run the pathfinder; returns false if it isn't finished the path
                if it has finished, and null if it can't find a path
        .Cost.[xx]
            - Allows you to set or find out the pathfinder costs directly. See
                the function for valid entries
        .GetPathLength()
            - Runs over the path to determine its length
        .PresetSafety(Start, End)
            - Caps the pathfinder as twice the Manhattan distance between the
                two tiles
            - source and goals must be integers (TileIndexes)

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Sun Jan 22, 2012 12:27 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 3 has been released. Available at the top or on Bananas.

Improvements include:
  • Road Pathfinder will now bridge over rivers, canals, and railroad tracks
  • Road Pathfinder can now apply a penalty to (road/rail) level crossings and to drive-thru stations
  • Ship Pathfinder's BuildBuoys() will now update the stored path with (re-)used existing buoys

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Tue Jan 31, 2012 5:08 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 4 has been released. Available at the top or on Bananas.

Improvements include:
  • Logging interface, and support of debugging output throughout the library
  • bug fixes to SpiralWalker
  • added Extra.GetOpenTTDRevision() function

I have also posted details on how the Ship Pathfinder works.

Details of the Logging interface:
Code:
[Log.nut] v.3
To get this to fully work, you will need to add a setting to your AI (in your
    info.nut )

   function GetSettings() {
      AddSetting({name = "Debug_Level", description = "Debug Level ",
         min_value = 0, max_value = 7, easy_value = 3, medium_value = 3,
         hard_value = 3, custom_value = 3, flags = CONFIG_INGAME});
   }
   
Log reads the setting each time it is called and so the Debug Level can be set
    in-game dynamically, if wished. If no setting is found, a Debug Level of 3
   is assumed.
   
   Log.Note(Message, Level=3)
      .Warning(Message)
      .Error(Message)
      .Sign(Tile, Message, Level = 5)
      .PrintDebugLevel()

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Thu Jun 28, 2012 3:24 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 5 has been released! Available at the top or on Bananas.

Improvements include:
  • Ship depot builder no longer will build the depot right next to the dock
  • added Station.IsNextToDock(TileID)
  • added Marine.RankShips(EngineID, Life, Cargo) - this is designed to be used as a valuator
  • added Marine.NearestDepot(TileID)

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Tue Jan 01, 2013 1:57 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 6 has been released! Available at the top or on Bananas!

The biggest change is the inclusion of the Dominion Land System. Roughly based on how roads are laid out in Western Canada (i.e. on a 2x1 mile grid), DLS serves as a sort of wrapper on the Road Pathfinder to encourage roads to follow a grid.

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Wed Apr 03, 2013 10:58 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Mon Jun 09, 2003 6:21 pm
Posts: 4532
Location: /home/sweden
I've noticed that version 6 of your MetaLibrary uses Fibonacci Heap 2. However, it doesn't depend on Fibonacci Heap 2 in bananas. (because a version 3 was released)

_________________
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)


Top
   
PostPosted: Fri Aug 02, 2013 2:47 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 6 has been released for GameScripts. See attachment in first post!

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Thu Jan 23, 2014 11:00 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Wed Oct 30, 2013 1:57 pm
Posts: 171
Trying to find good pathfinders for my AI's, trying to study if this does what I want.

_________________
Skippern
OpenTTD Mac user


Top
   
PostPosted: Fri Jan 24, 2014 9:11 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
The library has both Road and Ship pathfinders, including both route finding and route 'building' code. Both are used by my AI WmDOT if you want to see them in action. Feel free to post any particular questions you might have.

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Sun Feb 02, 2014 1:16 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Over the last three days, I have written up documentation for the included functions and the result can be seen live at my site at http://minchin.ca/openttd-metalibrary/. I'm excited to have it up. I hope it will help others make use of my library. :D Suggestions and comments appreciated.

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Sun Feb 02, 2014 1:35 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Wed Oct 30, 2013 1:57 pm
Posts: 171
MinchinWeb wrote:
Over the last three days, I have written up documentation for the included functions and the result can be seen live at my site at http://minchin.ca/openttd-metalibrary/. I'm excited to have it up. I hope it will help others make use of my library. :D Suggestions and comments appreciated.

Thanks mate, maybe I can find out why my AI fails at surveying routes :) Start looking at it tomorrow

_________________
Skippern
OpenTTD Mac user


Top
   
PostPosted: Sun Mar 02, 2014 1:17 am 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
Version 7 has been released! Available at the top or on Bananas.

Translation from the AI version to the GS version has been automated, and so the GS version has also been updated.

The biggest change is the inclusion of Lakes as a replacement from Waterbody Check. It serves the same purpose of checking if two points are within the same waterbody. However, Lakes maintains a memory, and so rechecks are very fast (the order of 4 ticks). It is also much more definitive about figuring out if there is NO connection between the two points.

Other improvements include:
  • Ship Pathfinder now uses Lakes rather than WaterBodyCheck
  • Ship Pathfinder now makes sure every point is in the same waterbody before adding it to the path
  • WaterBodyCheck is now deprecated in favour of Lakes
  • Documentation for MetaLibrary is now online at Minchin.ca
  • Fix array creation bugs in Array.Create2D(), Array.Create3D()
  • Added Array.RemoveDuplicates(Array)
  • Added Array.ToAIList(Array)
  • Added Extras.MinDistance(TileID, TargetArray); can be used as a valuator
  • Split Constants from Extras (file only, function access remains the same)
  • Split Industry from Extras (file only, function access remains the same)
  • Split Station from Extras (file only, function access remains the same)
  • Bumped maximum Log `Debug_Level` to 8
  • Added separate Changelog file
  • Rename `Readme.txt` to `Readme.md`
  • Update requirement to Fibonacci Heap, v.3 (AI version only)

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department


Top
   
PostPosted: Mon Mar 03, 2014 12:28 pm 
Offline
Traffic Manager
Traffic Manager

Joined: Mon Mar 18, 2013 10:22 pm
Posts: 165
Hey, was keen to take this for a spin, to see how my A* shippathfinder compares...

- Seems Bananas still has only version 6.
- Possibly having an utter noob moment but it didn't want to load till I extracted and renamed the archive to the old convention you used (MinchinWebs_MetaLibrary-7), else I get the compile error with "import("util.MinchinWeb", "MinchinWeb", 7);".
- Get a crash with the ship pathfinder:

Code:
   AILog.Info("Finding minchinweb path.")
   local meta_finder = MinchinWeb.ShipPathfinder();
   meta_finder.InitializePath([start_tile], [end_tile]);
   local path = false;
   while(path == false) {
      path = meta_finder.FindPath(50);
      AIController.Sleep(1);
   }
Attachment:
crash.png [20.29 KiB]
Downloaded 2 times


Top
   
PostPosted: Mon Mar 03, 2014 6:35 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
R2dical: I have attached an updated version of MetaLibrary that should fix the error. Let me know if it works for you and if it does, I'll release it on BaNaNaS.

R2dical wrote:
Seems Bananas still has only version 6
I'm not sure why this would be... v.7 is listed on the BaNaNaS website.

R2dical wrote:
it didn't want to load till I extracted and renamed the archive to the old convention you used (MinchinWebs_MetaLibrary-7)...
Creating tar files on Windows seems to be hit or miss. Right now I'm using Python's tarfile library. The folder name itself shouldn't matter, unless you have two folders with the same name. If you can figure more out what's causing the problem, I'll keep working to fix it.


Attachments:
File comment: MetaLib v7.1
MetaLib-7.1-AI.tar [260 KiB]
Downloaded 90 times

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department
Top
   
PostPosted: Mon Mar 03, 2014 8:41 pm 
Offline
Traffic Manager
Traffic Manager

Joined: Mon Mar 18, 2013 10:22 pm
Posts: 165
Thanks for the reply.

MinchinWeb wrote:
I'm not sure why this would be... v.7 is listed on the BaNaNaS website.
Sorry, meant the ingame content list which still shows v6, maybe it just needs to refresh still.

MinchinWeb wrote:
Creating tar files on Windows seems to be hit or miss. Right now I'm using Python's tarfile library. The folder name itself shouldn't matter, unless you have two folders with the same name. If you can figure more out what's causing the problem, I'll keep working to fix it.
Yeah that solved the problem, I think I had a combination of file conflict in content_download/ai and /ai and the tar issue you mentioned, which was why both extracting AND renaming got it to work originally. Works fine now, fyi I use 7zip to make tar in windows with no issues.

Another crash:
Attachment:
anothercrash.png [695.42 KiB]
Downloaded 2 times


What is the sort of timeframe for the ship pathfinder? I was trying to use it to find a path as shown in the backgrd (~6000 tiles long, start and ends are just off the screen), the crash happened after ~3.5 years of searching. I understand that its maybe only the first search that takes a while? Or is that due to the warnings shown...


Top
   
PostPosted: Mon Mar 03, 2014 11:55 pm 
Offline
Traffic Manager
Traffic Manager
User avatar

Joined: Tue Feb 01, 2011 12:41 pm
Posts: 226
R2dical wrote:
Thanks for the reply.
Another crash:
Attachment:
The attachment anothercrash.png is no longer available
Can you show me what tile 0x7F6F looks like? (Or alternately upload your test map here.) Did this tile used to be land and then was terraformed to be water?

I any case, I have attached an update to MetaLibrary below that should fix this bug, although I don't have a great way of testing it myself.

R2dical wrote:
What is the sort of timeframe for the ship pathfinder?
In terms of how long does it take to run? I haven't done a lot of testing, and it's hard to give good numbers because it depends significantly on the water layout (the pathfinders doesn't do well with peninsulas, for example). But I have run a few tests (in all cases, from a 'cold start'):
  1. 9 tiles, open ocean -> 21 ticks (Lakes) + 10 ticks (pathfinding)
  2. 32 tiles, around an island -> 151 ticks (Lakes) + 412 ticks (pathfinding)
  3. 69 tiles, around a peninsula that started on the edge of the map -> 4858 ticks (Lakes) + 14 years and counting (pathfinding)

So extrapolating, a 6,000 tile path could take 14k-422k ticks (Lakes) + 7k-77k ticks (or more!) (pathfinding) ... in any case, many years (a game day is about 74 ticks, so a year is about 27k ticks). I keep working on the pathfinder so I hope to bring both those numbers down.

On a practical level, do you plan on running ships along 6,000 tile routes? Once your ships take more than ~4 months to travel the route (one way), it gets much more complicated to determine whether a route is making you money...


Attachments:
File comment: MetaLibrary v7.2
MetaLib-7.2-AI.tar [260 KiB]
Downloaded 90 times

_________________
Alberta Town Names - 1500+ real names from 'Acme' to 'Zama City'
MinchinWeb's Random Town Name Generator - providing 2 million plus names...
WmDOT v13 - An AI that doubles as your highway department
Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 27 posts ]  Go to page 1 2 Next

All times are UTC


Who is online

Users browsing this forum: Google Adsense [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2017 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2017.
Hosted by Zernebok Hosting.