pathfinding to building (A* with multiple coordinates)?

Question

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 :

for this exemple, (0;0) coordinates is at up-left of the image with this landmark : 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?

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?](https://stackoverflow.com/a/23779490/2521214) and [Algorithm Trax Winning Condition](https://stackoverflow.com/a/29765542/2521214) If by multiple coordinates you mean more destination points then that is entirely different question hinting TSP (traveling salesman problem) — Spektre, Sep 05 '17 at 06:43

harold · Answer 1 · 2017-09-05T13:47:34.903

0

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".

edited Sep 05 '17 at 13:47

answered Sep 04 '17 at 13:24

harold

61,398
6
86
164

sorry I don't realy understand, what is your methodology to get one coordinate, closest of area target? – Matrix Sep 04 '17 at 21:46
@Matrix what do you mean? – harold Sep 05 '17 at 08:36
1

@Matrix OK well A* gives to shortest path to *any* goal, so some closest goal is selected arbitrarily (but of course deterministically). However at the moment A* would exit, the Open list will also contain paths to the other closest goals. So at that moment you could pop everything with the lowest F score off the queue and that would give you all shortest paths to goals - anything not in the Open list or with higher F is not a closest goal. – harold Sep 05 '17 at 09:18
@Matrix actually upon reflection, I think there may be situations in which some of the paths to closest goals are not fully developed when the first closest goal is reached, but then you can simply continue the algorithm until those paths are also done. – harold Sep 05 '17 at 22:17

Spektre · Answer 2 · 2017-09-05T09:29:51.093

0

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:

Algorithm Trax Winning Condition

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:

2D Diamond (isometric) map editor for some inside building ideas

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:

edited Sep 05 '17 at 09:29

answered Sep 05 '17 at 09:23

Spektre

49,595
11
110
380

I have same version of A* (but in javascript for my usecase). the "problem" is A* take only one couple of coordinate to start AND to reach `A_star::compute(int x0,int y0,int x1,int y1)`. So I have to try A* on each couple of coordinates belonging to the building (you said we can break the loop when found a solution, but how can be sure it's the shortless if we don't try all way)? – Matrix Sep 05 '17 at 09:53
@Matrix You can test specific grid value (like marked area for building) in your map instead of passing each cell coordinate to your A* and test for matching cell position in each iteration. I usually encode everything into 32 bit DWORD cell so I got just single 2D array in which is booth world map, A* filling, specific flags ... – Spektre Sep 05 '17 at 10:35
@Matrix iterative A* filling fills in order so the first hit of target is the shortest path does not matter how much cells are marked as target ... unless youre using some weird recursive A* in which this would be a problem – Spektre Sep 05 '17 at 10:36

pathfinding to building (A* with multiple coordinates)?

2 Answers2