2

I have a non-language-specific problem which I'm having trouble finding a workable answer for.

I have a 10x10 grid containing integer values from 1-10. Each value represents the cost of travelling across that square, moving north, east, south or west (cost is incurred while stepping off a square rather than onto it).

I need to find a method to navigate the cheapest path from a starting square to an end point.

I was using a recursive javascript function whereby each square could ask an adjacent square what the cost was if the journey went that way; the square asked would then ask its neighbours etc. until the cheapest route was found. However, as might be expected this takes far too long, even if each square was marked as busy so it couldn't be asked again (in order to prevent circular routes which might never end).

I'm sure this must have been done before. Does anyone have a method they feel would work?

Thanks for your help :)

4
  • 7
    it's called path finding, your solution looks like a floodfill starting from the destination, best solution (given good hueristic) is A* otherwise look up dijkstra's algorithm
    – ratchet freak
    Commented Feb 21, 2014 at 12:48
  • 1
    Does Javascript compile down to actual machine language, or are you getting eaten alive by interpreter overhead?
    – John R. Strohm
    Commented Feb 21, 2014 at 12:49
  • 2
    @JohnR.Strohm: He's getting eaten alive by the complexity. Recursive function asking it's neighbours is clearly a brute-force and O(2^n) is not going to fly even for |V|=100.
    – Jan Hudec
    Commented Feb 21, 2014 at 12:59
  • @JohnR.Strohm You could be right, there will ceratainly be a lot of interpreting going on!
    – CompanyDroneFromSector7G
    Commented Feb 21, 2014 at 13:00

1 Answer 1

Reset to default
-1

Solved problem. I suggest the following references.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://en.wikipedia.org/wiki/A*_search_algorithm

https://github.com/bgrins/javascript-astar

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.