0
\$\begingroup\$

This question already has an answer here:

I am making an RTS game, and I implemented path finding with A*. My A* algorithm uses 8 directions and terminates early in the case of no path found (I use 50*the vector distance between the unit and the point as the limit to dequeueing the fringe). If there's no path then they will go to the nearest valid point to the destination. This problem arises because a structure is bigger than 1 tile

I am having trouble now with attacking a structure, right now I have it so that it checks each "tile" of the structure, and gets the distance between the unit and the structure "tile". Plus, it will see if theres a path from that tile to the unit, and if there is then the tile is put in a priority queue, where priority is min distance.

Here, this can be a lot of path finding calls for 1 unit using this, the number of calls is dependent on the x*y size of the structure. Here is a picture to illustrate (with the orange being the unit, red being barrier (that can potentially move) and the blue being the structure)

enter image description here

Here there will be 9 calls to path finder, 8 of them will fail almost immediately , 9 will produce the path from the unit in orange to the bottom right corner of the structure.

It can get much worse with an example like this:

enter image description here

Here there will be 6 path finding calls which could take a long time depending on the space between the unit and the structure. So there must be a better way to path to a closest available tile of a structure without calling path finder for each tile in the structure and I need help with that. How would I go about treating the entire blue region as the goal? My node only encompasses one tile, so would I need multiple destinations (so multiple f values)?

\$\endgroup\$

marked as duplicate by BlueRaja - Danny Pflughoeft, Charanor, Gnemlock, Bálint, Vaillancourt Dec 14 '17 at 3:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ That is not the issue, I mention in the question how I deal with no path to a point \$\endgroup\$ – adrotter Dec 4 '17 at 0:31
  • \$\begingroup\$ So your trouble is in adapting your heuristic function to estimate distance to a rectangular region? With that, the accepted answer at the link Danny suggests should do what you need. \$\endgroup\$ – DMGregory Dec 4 '17 at 1:11
  • \$\begingroup\$ Would it help if I said that the barriers can potentially move (so they are other units) A naive approach would be to find the nearest tile alone using the distance, and then try attacking that tile, (so in picture 1, the unit in orange will essentially just wait until the red moved so he could start attacking), however why should he queue up to attack that closest one when there is a part of the structure available for attack, which is not the nearest tile. It's not a problem with getting there, its a question about efficiency \$\endgroup\$ – adrotter Dec 4 '17 at 1:24
  • \$\begingroup\$ Ohhhhh, you think you need to run a separate pathfinding query for each cell of the destination. No, you can run your pathfinding a single time, treating the entire blue region as the goal. If there's no path found to any part of that region in that single pathfinding query, then it can fall back to returning a path to the reachable point with the least heuristic distance, as described at the question Danny linked. \$\endgroup\$ – DMGregory Dec 4 '17 at 1:29
  • \$\begingroup\$ Yes, that's it. Ok, how would I go about treating the entire blue region as the goal? My node only encompasses one tile, so would I need multiple destinations (so multiple f values)? Can you point me to a question somewhere that explains this? \$\endgroup\$ – adrotter Dec 4 '17 at 1:34
1
\$\begingroup\$

Modify your goal check from something like:

if(currentNode == goalNode)

to if(goalRegion.Contains(currentNode)) or if(currentNode.isAGoal == true)

Now your search can stop on any goal tile, not just one specially-chosen one.

Next, adjust your heuristic. If you're using a Chebyshev distance from a single tile like this:

int h(int x, int y) {
    return max(abs(x - goal.x), abs(y - goal.y));
}

You can modify it to a distance from a rectangle like so:

int h(int x, int y) {
    goalX = clamp(x, goalRegion.minX, goalRegion.maxX);
    goalY = clamp(y, goalRegion.minY, goalRegion.maxY);
    return max(abs(x - goalX), abs(y - goalY));
}

Now you can run your pathfinding exactly once, and have it find the shortest path to any point in the goal region.

If you keep track of the tile with the smallest heuristic value h you've seen, as this answer describes, then you can fall back on a path to that tile in the event that your main search fails to find a reachable goal - getting you as close as possible instead.

\$\endgroup\$

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