Download the PHP package stratadox/pathfinder without Composer

On this page you can find all versions of the php package stratadox/pathfinder. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.

FAQ

After the download, you have to make one include require_once('vendor/autoload.php');. After that you have to import the classes with use statements.

Example:
If you use only one package a project is not needed. But if you use more then one package, without a project it is not possible to import the classes with use statements.

In general, it is recommended to use always a project to download your libraries. In an application normally there is more than one library needed.
Some PHP packages are not free to download and because of that hosted in private repositories. In this case some credentials are needed to access such packages. Please use the auth.json textarea to insert credentials, if a package is coming from a private repository. You can look here for more information.

  • Some hosting areas are not accessible by a terminal or SSH. Then it is not possible to use Composer.
  • To use Composer is sometimes complicated. Especially for beginners.
  • Composer needs much resources. Sometimes they are not available on a simple webspace.
  • If you are using private repositories you don't need to share your credentials. You can set up everything on our site and then you provide a simple download link to your team member.
  • Simplify your Composer build process. Use our own command line tool to download the vendor folder as binary. This makes your build process faster and you don't need to expose your credentials for private repositories.
Please rate this library. Is it a good library?

Informations about the package pathfinder

Pathfinder

A motion planning solution for PHP.

Build Status Coverage Status Scrutinizer Code Quality

Installation

Install using composer require stratadox/pathfinder

Examples

Shortest path(s) through a graph:

Shortest path in a grid:

Complete set of all shortest paths:

Features

The pathfinder module offers two kinds of features: to build up an environment, and to search shortest paths through that environment.

Search Algorithms

There are many algorithms in existence that perform graph traversals. The Pathfinder module implements several.

Dijkstra

The original path finding solution: Dijkstra's algorithm is a breadth-first search algorithm that makes no assumptions about unknown routes. (I.e. it is free of heuristics)

Illustration of Dijkstra's algorithm finding a path from a start node to a goal node

This algorithm can be used for both single- and multi path searches: as well as finding the shortest path from point A to B, it can find the shortest paths from point A to all other reachable points in one go.

It is generally slower than A* for finding single paths, unless no heuristics are available. When looking for all paths from a single source, however, Dijkstra's algorithm is usually the preferred pathfinding choice.

A*

A quick algorithm for finding paths at runtime is the A* search.

A* is a best-first search algorithm that finds the shortest (cheapest) path by maintaining a priority queue containing the considered nodes, using the cost of the path so far plus the estimated cost of the rest of the path as (inverse) priority indicator.

Illustration of A* search for finding path from a start node to a goal node

Using the A* algorithm can lead to better performance compared to Dijkstra in cases where consistent heuristics are applicable.

By default, the Euclidean distance is used as heuristic (to estimate the cost of the rest of the path). Alternatively, Taxicab distance can be used, as well as Chebyshev distance or the result of the Floyd-Warshall algorithm.

Bellman–Ford

Commonly known as the Bellman–Ford algorithm, yet invented by Alfonso Shimbel, this algorithm is slower but more versatile than Dijkstra's algorithm for finding all shortest paths from a given source.

The speed sacrifice is made when the graph may contain negative-cost cycles, in which case this algorithm beats Dijkstra's hands-down, since Dijkstra's would continue searching for eternity.

The Bellman-Ford algorithm has the ability to stop and detect such negative cycles, throwing an exception instead of eating infinite resources.

Floyd-Warshall

The Floyd-Warshall algorithm (invented by Bernard Roy) is used to find all paths, between each possible start vertex and each possible end vertex.

With an O(v^3) runtime, v being the amount of vertices, the Floyd-Warshall algorithm is probably much too slow to be used at runtime. Since the algorithm finds all possible shortest paths through the environment, however, it's exceptionally well-suited to build an index of shortest paths at deploy time.

For static environments, this means a significant reduction in path finding costs at runtime: with all shortest paths already known, there is no need to search for paths at runtime.

In environments that are likely to change only slightly, the result of the Floyd-Warshall algorithm may be used as a heuristic for the A* search.

Flavours

Dynamic Pathfinder

The Dynamic Pathfinder is an automatically composing pathfinder that alternates between using the Dijkstra's algorithms based on the type of request and environment.

For finding multiple paths, it uses Dijkstra's algorithm - except when the graph contains negative edge weights, in which case Bellman-Ford is applied.

In searching for a single path, Dijkstra's algorithm can also be applied. A* is used when:

Euclidean distance is used by default, a different one can be specified using, for example:

When available, a map of the environment (the Floyd-Warshall result) can be provided using:

Since the environment is assumed to be dynamic, the map is only used as A* heuristic.

Static Pathfinder

The Static Pathfinder assumes the environment to be unchanging, and possesses a map with the shortest paths through that environment.

While limited to unchanging environments, the static pathfinder is by far the fastest solution. Under the hood, all it does is a bunch of lookups, the amount of which exactly equals the length of the path.

Graphs

Main article: Graphs.

The pathfinder works on directional graphs that contain weights. Each vertex in the graph has at least one label, to serve as identification.

The cost of a path through the graph is determined by the sum of the weight of its edges.

Environments

When finding paths through graphs with spatial properties, single-target search can be optimised by using heuristics.

The graphs as created in the example section of this document are examples of such environments.

Any number of Euclidean spatial dimensions can be used, limited only by the configuration of the heuristic.

Networks

Not all graphs have associated geographic information. Those that do not are called networks.

Although the pathfinder cannot make use of heuristics to speed up the search, it can still adequately find the cheapest path.

Using your own network

What if you already have a graph mechanism? Maybe your graph is already modeled, maybe it follows a certain structure of a particular A/R ORM.

In such cases, simply implement the Environment interface (either directly or through an adapter) and you're good to go!

For an example of how such an adapter would look like, see the graphp finder package.


All versions of pathfinder with dependencies

PHP Build Version
Package Version
Requires php Version >=7.2
stratadox/immutable-collection Version ^1.1
Composer command for our command line client (download client) This client runs in each environment. You don't need a specific PHP version etc. The first 20 API calls are free. Standard composer command

The package stratadox/pathfinder contains the following files

Loading the files please wait ....