jmgq / php-a-star Goto Github PK

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.

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.

Tools to consider:

• PHPStan
• Psalm
• Phan

Acceptance Criteria:

• The tools are run as part of the CI pipeline.
• The tools can be run individually via a composer command.
• The tools can be run all together via a composer command.
• The tools can be run from the docker container.
• The Readme file mentions these tools.
• The Changelog reflects this new feature.

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

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.

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:

1. Use any terrain defined in a text file, as opposed to a hard-coded terrain.
2. Customize the for loop (terrain size increase per loop iteration).
3. Adjust the terrain on each iteration of the for loop. The script in #5 always use the full terrain array, but I think that the main terrain should be cropped to the desired size on each iteration.
4. Create a terrain generator. It should accept a size and a destination file path as parameters, as well as the minimum and maximum tile cost.
5. As an alternative (or complement) to item 1, use a random terrain. The downside is that we wouldn't be able to use the same terrain in two different benchmarks, so in this case, the for loop should be executed several times and then display averages. Or it could accept the RNG's seed as an optional parameter, that way the same terrain can be generated in different benchmarks, and there is no need to run the benchmark several times or calculate averages.
6. Use the symfony/Console component, as it is a very convenient library to create console commands, including utilities like progress bars, tables, and so on.
7. After the benchmark is run, display the used configuration and a table with the results.

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.

This project should be making use of the features provided by Scrutinizer. Tasks:

• Add the repository to Scrutinizer.
• Add Scrutinizer's badge to the Readme.
• Enable the Code Coverage feature in Scrutinizer.
• Make sure that it's using all the relevant analysis tools.

Only the following should be included when composer installs from dist:

• src folder
• composer.json file
• README.md file
• LICENSE file

Different ways to implement this functionality are discussed here.

As suggested by @pathway in #12, the benchmark should be extended to display the number of nodes that were expanded during the execution.

As a prerequisite for this, the algorithm code needs to be changed so that it can report this metric during debug mode.

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.

Add CodeSniffer to the Travis build to ensure that all the code is PSR-2 compliant.