jmgq / php-a-star Goto Github PK
View Code? Open in Web Editor NEWA* (A Star) search algorithm for PHP
License: MIT License
A* (A Star) search algorithm for PHP
License: MIT License
NodeList is currently implemented by a regular PHP array. As pointed out by @pathway in #5, the algorithm efficiency can be improved by changing the NodeList's underlying structure. In #5, an \SplPriorityQueue is used. It may be worth to also implement it using other structures, like \SplMinHeap, compare them and choose the best.
I think the approach should be to create an interface called, for instance, NodeList
, or NodeCollection
and then create several implementations, like ArrayNodeCollection
, PriorityQueueNodeCollection
, MinHeapNodeCollection
and so on.
This project should be making use of the features provided by Scrutinizer. Tasks:
The Node interface contains two method signatures that are actually not needed and should be removed: getChildren
and addChild
.
The implementation of those methods should remain intact in AbstractNode
, in case they are being used by any third party. However, they should be marked as deprecated via PHPDoc.
Using the example code to represent a graph. I made a graph that had separate links in both directions between each node. Simplest case had just 3 nodes, with links in both directions as shown:
startnode <==> node1 <==> goalnode
The search failed because after node1 was expanded, it followed the link back to the start node and set its parent, resulting in a parent loop.
node1 parent was set to start node
then, start node parent was set to node1
...resulting in a recursive data structure, so the solution could not ever be found (timeout).
Inspired by the script provided by @pathway in #5 (examples/Terrain/scaletest01.php), I think it would be a good idea to have a benchmark utility that worked in more general cases. The benchmark utility should be able to:
Profiling using the scale testing branch (including the priority queue): php xdebug and kcachegrind
A lot of time is spent constructing nodes, including __Constructor, and fromNode.
Would you consider an approach which did not require as much node construction. For example, if each nodeID need only be created once.
As suggested by @pathway in #12, it would be interesting to include a memory usage report in the benchmark results. The event returned by the stopwatch in BenchmarkRunner.php
allows you to get the maximum memory usage with the following method: $event->getMemory()
. Unfortunately, I couldn't make it work properly, as it always returned the exact same amount, so a different approach may be needed.
Add CodeSniffer to the Travis build to ensure that all the code is PSR-2 compliant.
Currently the user has to implement the Node
interface, which requires him to implement several methods, like getID
, setParent
, getParent
, getF
, and so on. Luckily, the user can extend from AbstractNode
, which implements everything but getID
.
However, this is just highlighting the fact that the only user-related method in the Node
interface is getID
, the rest of the methods are algorithm-related, and they shouldn't be exposed to the user.
The user shouldn't be accessing algorithm-related methods, it's not his responsibility to change the G or H value of a node, for instance; the algorithm should take care of that.
There are other problems related to the current approach. For instance, when the user extends the AStar
class, he has to implement three methods (generateAdjacentNodes
, calculateRealCost
and calculateEstimatedCost
), all of them have Nodes as parameters. If the user changed any of the Node parameters (for instance, the parent, or the G value) while he's implementing one of the previous three methods, it could lead to a fail in the algorithm.
Possible solution:
interface NodeIdentifier
{
public function getUniqueID();
}
class Node
{
// This is pretty much the current AbstractNode, plus the following:
private $userData;
public function __construct(NodeIdentifier $userData)
{
$this->userData = $userData;
}
public function getID()
{
return $this->userData->getUniqueID();
}
public function getUserData()
{
return $this->userData;
}
}
So now the user won't create a class that extends from AbstractNode
(as it won't exist anymore), his class should just implement NodeIdentifier
. For instance, instead of MyNode extends AbstractNode
, it would be MyNode implements NodeIdentifier
. Then, when the user extends from AStar
, the three methods' parameters won't be of type Node
, they will be of type MyNode
.
As this is a major change and it would break backwards compatibility, the major version of the library should be increased as well.
Generally the changes required to enable these are very small. But the algorithm would need to be written in a slightly more general way.
Here is a nice example from python: https://github.com/anubhav-coder/Pacman-AI-Project-in-Python/blob/master/Pacman/search.py , you can see the variations can be very small.
This suggestion would work well with your plan for benchmarking, because it would nicely illustrate the effects of the different algorithms.
It would also provide a basis for a wider range of algorithm variants on top of these.
Tools to consider:
Acceptance Criteria:
Only the following should be included when composer installs from dist
:
src
foldercomposer.json
fileREADME.md
fileLICENSE
fileDifferent ways to implement this functionality are discussed here.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.