Improve the NodeList's efficiency about php-a-star

[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/

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

[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 686b0b6). 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.

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