Scale

[pathway]

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.

[coveralls]

Coverage decreased (-61.02%) when pulling 4e0b765f5036b0f5c6a71615c445b4bcf65bfdbc on pathway:scale into f59ab606b3c2ec7234d496a28c5035388472112f on jmgq:master.

[jmgq]

Hello @pathway, thank you for this new pull request.

Improving the efficiency of the open list (by using other data structures like \SplPriorityQueue or \SplMinHeap) is actually one of the things I had in my TODO list, but I never implemented it, so I'm really glad you did it. What I'm going to do is to copy my TODO list from my local computer to the GitHub's issue tracker, so everyone can be aware of the pending tasks.

And what I absolutely love is that benchmark you did. That proves that your solution is better than the current implementation, so we should definitely incorporate your changes. However there are a couple of issues we need to solve first:

1. We need to modify this code to comply with the project's coding standards. This are listed in the README.md file. The main thing is to follow PSR-2. There is a tool that fixes the code automatically. I've never used it, though. What I usually do is to activate CodeSniffer in PHPStorm, so I can check on the fly that the code I'm writing follows PSR-2.
2. The code coverage has dropped from 100% to 39%, so we need to create tests for the new code.

I think that probably the easiest solution could be this: I can create a new branch off master called feature/efficientOpenList, then you could change the target of this pull request from jmgq:master to jmgq:feature/efficientOpenList, so we can both work in that branch at the same time. Once we are happy with the final result, I'll merge that branch into master. Does that sound right?

Also, the fact that you had to change testShouldPrintSolution3 means that the original test I wrote was poor. It should either have only one best path, or check that the solution found by the algorithm is one of the two possible solutions. So thanks for spotting that too :smiley:

[pathway]

Please excuse my ignorance, shall i create a new pull request? I do not see how to change the target branch.

[pathway]

I am not too proud of the NodePriorityQueue code on my branch, and it is quite rough. Im sure you could do a better job on that.

If you want, you can take my tests and ignore or completely rewrite a node queue as you wish; my only request is, I would like to see my name+email in writing somewhere that I can point to as a project contributor, whether in repo history from a pull, or in comments or credits file. Thank you.

[jmgq]

I think you are right, you cannot change the target of a pull request. Would you mind to create a new pull request with the same commits, but this time pointing to feature/efficientOpenList instead of master, please?

Regarding your second paragraph, I would love that you appeared in the contributors section. In fact, if you check the commit history, you'll see that your commit is there. I knew that your commit broke the tests, but the reason I merged it into master to then revert it was just because I wanted you to show up in the contributors section. But for some reason you are not there. My guess is that you don't appear in that list because your pull request wasn't directly merged into master (I made some changes to master, then rebased your branch and merge it. I think that could have confused GitHub).

However, what I plan to do now is to merge your new pull request into feature/efficientOpenList as soon as I receive it. That should make you appear in the contributors section right away. If that doesn't work either, I will create a CONTRIBUTORS.md text file and I will add you there. In fact, please feel free to create that file yourself in a new commit in your new pull request.

Thanks again for your help.

[jmgq]

@pathway, I have added you to the contributors file. Please feel free to add other personal information like your e-mail or website, or anything you consider relevant :smiley:

[pathway]

Thank you @jmgq you are very kind.

[jmgq]

No worries, and thank you very much for all your help.