Finding the closest point on a grid with obstacles

https://stackoverflow.com/questions/21908082

14-10-2022
|

Question

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?

Solution

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:

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow