search

jmgq / php-a-star

A* (A Star) search algorithm for PHP
MIT License
63 stars 18 forks source link

Maybe consider generalizing the algorithm to allow for BFS, UCS, DFS, etc #13

Open pathway opened 9 years ago

pathway commented 9 years ago

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.

jmgq commented 9 years ago

This feature is worth considering. As there is already a plan to change the Node structure, maybe this could be considered at the same time: since changing the Node structure will break backwards compatibility too, changing both at the same time would save us to break it twice.

This change will also require to analyse exactly what needs to be changed from the current algorithm.

pathway commented 9 years ago

I think the main things that need to become parameters are:

1) Data structure used for openList. It can be in { priorityqueue, minheap } for astar or UCS, or stack or plain queue for DFS or BFS. 2) Cost function. Only applies to algos with ordered openLists like astar and ucs.

These two things can be passed as options to the algorithm. Just an idea.