1

I have a game where you have to move around a map collecting gold and then move to the exit. I am currently trying to write an AI that will play this game but I want to know what algorithm I should use the find the closest instance of an object. For instance, the closest piece of gold or the closest unknown map square. The issue is that there are walls that the player cannot move through, so rather than just finding the closest object I need to find the one to which there is the shortest route. Is there an algorithm that can do this?

1 Answer 1

6

The algorithm you're looking for is called A* Search Algorithm. It is a best-first search algorithm that works by beginning at the starting point and building up a series of possible paths (excluding going through obstacles since those aren't possible paths), then scoring those paths to find the least cost one. In your case you'd need to customize the scoring by decreasing the cost based upon the objects along the path and increasing the cost by distance.

There's some information that will help you with it here:

There's a nifty interactive demo here (code also on github): http://qiao.github.io/PathFinding.js/visual/

enter image description here

Other resources:

2
  • How would I modify this algorithm to work if the bot didn't know the whole map? Only an area around itself and any area it's previously been to. Feb 20, 2014 at 23:32
  • @CountBale You must at least know what the intended destination is. If you are simply exploring the map to find your resources (e.g. Gold) then I would suggest running through your algorithm several times, each time randomly choosing a coordinate on your map to go to. After a sufficient amount of your map is revealed start finding the path to your actual resources.
    – Jax
    Nov 10, 2015 at 19:46

Your Answer

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

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