Improve the NodeList's efficiency

[jmgq]

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.

[jmgq]

As part of v2.0.0, a new interface called NodeCollectionInterface has been released. The first draft of the new AStar class allowed the user to pass their own open and close lists via the constructor, but it was later on removed (in commit 686b0b6f4bcf2c005a00cfb2d5aafab977bd917a). It is better for the constructor to not have those parameters until some other implementations of NodeCollectionInterface have been created and tested, so that NodeCollectionInterface is not part of the public API until it's strictly necessary.

[jmgq]

I'll leave here some of my old notes regarding open and closed lists:

Open list

• Priority queue: https://stackoverflow.com/questions/45577114/a-star-algorithm-open-and-closed-lists
• The best choice is a list that has both a fast insert and extract minimum operation. The performance of the insert operation is more important than extract minimum since the algorithm typically doesn’t extract all nodes inserted into the open list, with the exception being when no path exists). See https://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html

Closed list

• We may not need a closed list. Some implementations of the A* algorithm have a closed list, but some others just mark the nodes as visited instead. Do the latter require that the heuristic is admissible? I need to investigate this further before completely getting rid of the closed list.
• https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/

[pathway]

Do the latter require that the heuristic is admissible

You always need an admissible heuristic, unless you are ok with sub-optimal routes. How important that is can be domain-specific.

Depending on the specific case, finding the truly optimal route may be hugely expensive (imagine a 200x exaggeration of the image from your link above), so you may be happy with just finding something "reasonable". So I think an option to allow sub-optimal routes could be sometimes useful.

The "closed list" is just permanently (for the current search) flagging each node as "done", so you can handle it any way you want -- a flag, a list, a map. Yes doing this in the cheapest way is good. Choice of how you track closed list, doesn't interact with the heuristic or with admissibility at all. You also want a way that is easy/cheap to "reset" for the next search.

[jmgq]

Hi @pathway, nice to see you again! Apologies for my late reply, somehow I missed it.

I think an option to allow sub-optimal routes could be sometimes useful.

I agree, this is already possible with the current implementation, as it's up to the user to provide the heuristic implementation.

Choice of how you track closed list, doesn't interact with the heuristic or with admissibility at all.

Thanks for clarifying, I believe you're correct. I was a bit confused when doing my research, because some implementations of the A algorithm don't use a closed list at all. This is the case in the pseudo-code provided in [Wikipedia](https://en.wikipedia.org/wiki/A_search_algorithm#Pseudocode). This leads me to believe that the closed list is strictly not necessary, but using one would make the algorithm more efficient. And we can make it even more efficient by choosing the right implementation of the closed list, it could even be a flag in the node, as you said, instead of an actual list or independent structure.