CODEWITHSUNDEEP
a-star
user1792042
user1792042

Reputation: 261

A star: finding nearest of multiple goals

I am working on project where i need to find a path to the nearest (of many) goal node in 2D grid (8 connections in any node: N,S,W,E,NW,NE,SW,SE). There can be walls blocking path on the way. There is no problem when it comes to find path to one goal node, but how could i find in reasonable time which goal is nearest? I don't think running A* for every goal node and getting length of every path found to compare is reasonable way, how else can it be done?

Is A* somehow capable of finding path to nearest node, or the nearest goal must be found other way and then passed to A* as only goal?

enter image description here

Legend:

White - walkable

Grey - walls

Blue - myself

Green - goals

Red - enemy (i am planing to keep distance from enemy at X SQM)

Upvotes: 0

Views: 1208

Answers (2)

B-Abbasi
B-Abbasi

Reputation: 823

A* is for informed searches where we have some data other than just goal state... According to your question it seems like there is no relevant data and we just know what our goal state is. If that is the case then you can simply apply BFS.

Upvotes: 1

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86146

Yes, just set EstimatedDistanceToEnd (aka. h(x)) to the minimum estimate over all end-nodes. Then just stop the search when you hit an end-node.

Upvotes: 2

Related Questions