pathfinding to building (A* with multiple coordinates)?

1
votes

1) I think about a game where we can build building who take many tiles, for example 3x3.

So before start the build, I need to move character to adjacent tile. So there is an algorithm to find shortest path to the building area?

Are we obligated to use A * on each tile of area's building and select shortest?

EDIT, exemple :

map : enter image description here

for this exemple, (0;0) coordinates is at up-left of the image with this landmark : enter image description here imagine your character is at (0;0)

I looking for algorithm to move character cloest to the left bulding on image. [ coordinates: (1;2), (8,2), (1,10), (8, 10) ]

the target is not a single coordinate like "normal" case, but an aera (with 4 points).

So what is the best way to find closest position (excluding diagonal) from a single start coordinate [here, (0,0)] to an area [here : (1;2), (8,2), (1,10), (8, 10) ] ?

I want the algo return arrays of solutions, so in case of multiple way like in this exemple: [ (0,2), (1,1) ] , not chose a solution, juste give me all equivalant solutions.

2) Same question with a system of map without tile, but just coordinates?

2
algorithmpath-finding
if you got tiles then you got 2D/3D array/grid/map so I would use grid variant of A* instead of graph version (which you suggest) which is more suitable for vector data. see How to speed up A* algorithm at large spatial scales? and Algorithm Trax Winning Condition If by multiple coordinates you mean more destination points then that is entirely different question hinting TSP (traveling salesman problem) – Spektre
I edit with an exemple, most clear? – Matrix

2 Answers

0
votes

Well array/grid version of A* can stop on any hit in target area so just grow from start point until hit any of the destination coordinate and then backtrack.

And Yes you can do this also with the graph/vector version you just set any obstacles as nodes.

In case your tiles are (semi) walkable then grid version of A* is better as You can take advantage of it. You just make 2D representation of each of your tile marking walkable and wall areas. Something like this:

Which will allow you to navigate through your buildings too ... I do not see inside of your buildings however so my bet is that you did not think of this till now. Take a look at:

I am using 3D grids so I got 3D terrain and buildings can have also levels ... you just need to adjust the view to optionally cut the levels above player something like this:

levels

0
votes

Are we obligated to use A * on each tile of area's building and select shortest?

No, A* can take goal predicate, which does not have to be "when the current coordinate equals this coordinate", it can easily be "when the current coordinate is contained in some set/area". This does not change anything about the global structure of the algorithm, just the exit-test.

Naturally you have to keep your heuristic admissible.

To clarify, instead of this "narrow" pseudocode for A*: (copied from wiki)

    current := the node in openSet having the lowest fScore[] value
    if current = goal
        return reconstruct_path(cameFrom, current)

You can have this:

    current := the node in openSet having the lowest fScore[] value
    if current ∈ goals
        return reconstruct_path(cameFrom, current)

Or this:

    current := the node in openSet having the lowest fScore[] value
    if satisfiesGoalCondition(current)
        return reconstruct_path(cameFrom, current)

Which can be some test such as "current coordinate is inside goal rectangle".