3
\$\begingroup\$

the issue I'm having will be best described with pictures more so than with code, so lets have a look if you will.

example scenario

So all the mobs followed the player and started attacking him, but as soon as 4 spots to the E, S, W, N were taken, mobs 1 and 2 are no longer able to find the path.

When mob from E/S/W/N spot dies they can of course find a way to the player. example scenario 2

My question therefore is what is the way to implement this so that mobs can get to the player when only corners are free?

Diagonal movement is not allowed and i'm using Euclidean distance. I've read this How do I avoid pathfinding characters getting stuck in corners? and other questions, but they dont quite cover what I need here. I'm sorry if this isnt specific enough, happy to clarify.

\$\endgroup\$
  • \$\begingroup\$ Can the bats attack diagonally, or only N/S/E/W like the movement? ie. Is there any benefit to sitting in the corner? \$\endgroup\$ – DMGregory Feb 3 '16 at 19:44
  • \$\begingroup\$ of course, they attack from 1.5 tile distance , so diagonally as well \$\endgroup\$ – TheAlmightyOne Feb 3 '16 at 20:38
4
\$\begingroup\$

Edit: I initially assumed both moving and attacking only happened N/S/E/W, and that your problem was other monsters were failing to approach the pile-up at all.

Now I understand that your attacking range is larger than your movement step, so enemies should prefer navigating to a tile diagonally-adjacent to the player over waiting behind an attacking monster when all 4 adjacent spots are blocked.

New Answer (get to a valid attack location, even if it's diagonal)


As mentioned in a comment, we can fix this with a small modification to A*.

We still invoke A* once, with the goal as the player position. Anytime we evaluate the heuristic, we do it with respect to the player position. That's all the same.

What we change is the acceptance criterion. Rather than returning a path only when currentNode == goal, we accept a path if:

AttackDistance(currentNode, goal) < attackRange

So if we find a path that gets us to a spot diagonal to the player, within attacking range, job done! Return that path as though we'd reached the goal. Now an entity will get a valid path as long as any space in attacking range is reachable.

You can improve this further with the suggestion below about treating allies as high cost rather than total blockages, so that distant monsters will still approach a player who's completely surrounded.

Another possible improvement would be to cache this path, but not return it right away, to see if a closer option is available. Then we fall back on the initial find only if no closer option is found. This keeps a monster from stopping once it's in range and blocking everyone behind it, and will help for monsters that have ranged abilities but still prefer attacking in melee.

Original answer (solves approaching a blocked target)


Have you considered making the pathfinding treat cells occupied by the monster's allies, not as blocked, but as some exorbitantly high cost?

That way, whenever there is a path that doesn't require moving through a fellow monster, the agent will still prefer such a path.

But if there's absolutely no free path to the player, then the agent will settle for a path that takes it through another monster (on the assumption that this monster is also piling up on the same target, and will eventually die or move).

Since your pathfinding can now return paths with other entities in them, you'll need to make sure your movement logic checks the cell before moving into it, rather than trusting that the path is always free. If it's blocked, the monster can either idle there until a clear path is found, or play some other behaviour (like ranged attacks or circling the mob).


The other common solution to multi-monster swarming like this is to ditch A* and instead use something like Dijkstra's algorithm, working outward from the player and storing the path distance from the player to each cell, counting only terrain obstructions.

While this is more work, now every monster can share this one set of pathfinding data (which may pay off when you have many monsters). On its turn, a monster looks at the open cells around (and under) it, and moves to the one with the shortest stored distance to the player. (Gradient descent)

\$\endgroup\$
  • \$\begingroup\$ I really like the second part of your answer. I will definitely update if I end up doing that. \$\endgroup\$ – TheAlmightyOne Feb 3 '16 at 7:07
  • \$\begingroup\$ that did it! It now works exactly how I originally wanted it, thank you for your help. link \$\endgroup\$ – TheAlmightyOne Feb 4 '16 at 7:12
0
\$\begingroup\$

You didn't provide a lot of information about how your pathfinding currently works, so I'm going to assume what Nils has assumed, which is that your bats are seeking a path to the player, not to the places adjacent to the player.

My solution to this would be: - Find every spot next to the player. - For every one of those spots, find a path to it. - If no paths are found, quit. - If any paths are found, take the shortest one.

For efficiency, you could even put this after your current algorithm, eg, - Find path to player. - If no path can be found, do the above.

\$\endgroup\$
  • \$\begingroup\$ I feel like this, despite lack of detail on how my algorithm works, is a really bad answer. I would then be doing 10x work needed to find the path if its obstructed in any way, wouldn't I? \$\endgroup\$ – TheAlmightyOne Feb 3 '16 at 4:03
  • 1
    \$\begingroup\$ @TheAlmightyOne not necessarily. We can improve codepants' answer by only pathfinding to the square the player is on (so all heuristic checks still refer to only that one destination), and modifying A*'s "Have I reached my goal?" determination from currentCell == goal to distance(currentCell, goal) < attackRange. That way the pathfinding will terminate successfully as soon as it finds a path to any cell sufficiently near the player, rather than only those which are movement-adjacent. \$\endgroup\$ – DMGregory Feb 4 '16 at 1:17
2
\$\begingroup\$

I think your issue is that you pathfind towards the players tile rather than to a tile that he can be attacked from. Since there is no actual path to the player in that case, since diagonal movement isn't allowed, of course they can't find a path.

If you just want them to get closer you can put a maximum on the number of tried nodes and always move towards the minimum of your heuristic.(In which case I'd recommend the manhatten metric)
Or you could change your metric a bit so that it's 0 when you're at a distance you can attack from.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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