jmgq/php-a-star — pull request #5 by pathway (2014-10-18 23:31:23+00:00)
Title: Scale

Scale branch includes these changes:

1) Added large terrains to see performance on larger problems.
2) Replaced openList with SplPriorityQueue.

Using hhvm on an old Ubuntu desktop, timings to find solutions of different sized problems are below.
Columns are Goal Distance / Seconds

openList is array
0	0.065372943878174
50	0.57873010635376
100	1.9482820034027
150	5.3835060596466
200	11.145383119583
250	18.085386991501
300	28.876262903214
350	44.296004056931
400	65.069844007492
450	89.366780996323

openList is PriorityQueue:
0	0.13503909111023
50	0.65088295936584
100	1.6774241924286
150	4.1498160362244
200	7.7588210105896
250	11.37260389328
300	16.837527036667
350	23.381567001343
400	31.248064041138
450	38.205113887787

On the largest problem, 2.3x faster using PriorityQueue.

The phpunit tests are passing. However one test now finds a different solution with the same cost (Terrain/StaticExampleTest::testShouldPrintSolution3) so I updated the solution to match.

I look forward to your comments.