Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
50 votes

Efficiently pathfinding many flocking enemies around obstacles

This sounds like a use case for Flow Fields. In this technique, you do a single pathfinding query outward from your player object(s), marking each cell you encounter with the cell you reached it from....
user avatar
  • 113k
47 votes
Accepted

How can I make A* finish faster when the destination is impassable?

Some ideas on avoiding searches that result in failed paths altogether: Island ID One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are ...
user avatar
  • 3,022
47 votes
Accepted

Why do some networked games use interpolation and some use pathfinding for remote movement?

I've worked on the networking code for two real time AAA networked games, one for smartphones and one for a handheld console. To directly answer your question "why", well, some games use one or the ...
user avatar
  • 13.2k
33 votes

A* Algorithm for Tactical RPGs?

Climbing, and gaps, are just different cost functions. For a unit that can jump the gap has a normal(?) cost, while for a non-jumping unit it has arbitrarily high cost. Climbing costs extra, as does ...
user avatar
  • 1,997
27 votes
Accepted

Is A* efficient even when the obstacles are moving?

There are multiple algorithms that are much faster than A* when you need to recalculate a path with moving obstacles. See here under "Simple Recalculations". However, you're not likely going to find ...
user avatar
25 votes

How can I make A* finish faster when the destination is impassable?

AStar is a complete planning algorithm, meaning if there exists a path to the node, AStar is guaranteed to find it. Consequently, it must check every path out of the start node before it can decide ...
user avatar
  • 3,567
23 votes
Accepted

How can I adapt A* pathfinding to work with platformers?

You don't need to adapt A* at all. The only consideration is where you put your nodes and how you connect them. The linked article seems to convert from a platformer-friendly model to a grid based ...
user avatar
  • 718
22 votes
Accepted

Pathfinding with lock and key?

Standard pathfinding is Good Enough -- your states are your current location + your current inventory. "moving" is either changing rooms or changing inventory. Not covered in this answer, but not too ...
user avatar
  • 8,954
21 votes

How can I make A* finish faster when the destination is impassable?

Run a dual A* search from the target node in reverse as well at the same time in the same loop and abort both searches as soon as one is found unsolvable If the target has only 6 tiles accessible ...
user avatar
21 votes

A* pathfinding for dynamic obstacles and player made blockages?

I haven't looked at specific implementation of A* by Aaron but with a normal A* you could include the 'block tower' as passable terrain but update the heuristic so that the 'cost' is much higher than ...
user avatar
  • 542
19 votes

How do I make A* agents avoid other agents?

Rather than solving your problem, here's a way to take the lemons and make lemonade. Many years ago a friend of mine was working on a very well-known FPS which had precisely the problem you describe: ...
user avatar
18 votes
Accepted

How do I make A* agents avoid other agents?

You can start by letting the pathfinding fail. On failure, choose a random time in the future to re-try pathfinding. Some low level networking protocols work that way, and quite well. What you have ...
user avatar
18 votes
Accepted

How to reduce the time taken to path-find to an unreachable location?

Using a bidirectional path finder usually solves this issue if the area the player is stuck in is small. They basically advance from the player's position and the destination at the same time and when ...
user avatar
  • 14.5k
15 votes
Accepted

How do I avoid pathfinding characters getting stuck in corners?

Scenario It seems your pathfinding and collision detection have different ideas of what's OK, when it comes to walking around corners. Say your pathfinding plans out this path (brown squares are ...
user avatar
  • 13.3k
15 votes

What kind of steering behaviour or logic can I use to get mobiles to surround another?

Give your agents a weak "electrostatic charge" to make them repel each other, along the lines of Coulomb's law. Assuming for simplicity that mobs should push each other away with equivalent strength, ...
user avatar
  • 13.3k
15 votes
Accepted

How to find path in graph without crossing the walls?

The problem is with how you are formulating your navigation graph. If you'll allow me to butcher your diagram: Here is what the navigation graph should look like. For each node in the original graph ...
user avatar
15 votes
Accepted

How can I generate a (relatively) linear dungeon path?

Requirements You want multiple paths from A to B. You want to work in grid space, presumably this is tile space for your side-scroller. You don't want paths to cross, or it will spoil game ...
user avatar
  • 29.1k
14 votes

A* pathfinding in 3D

Actually A* does not use dimensions. A* works with nodes and each nodes have paths to other nodes. In the case of a 2D grid every cell is a node and every boundary is an implicit path (left, right, ...
user avatar
13 votes

Is it possible to use nav-mesh in 2d game in Unity?

In case anyone Googles this later, you CAN use nav meshes in Unity. I'm using unity 2018.2 and set up a navmesh in a purely 2D top down tilemap game I'm working on. Check this thread in the Unity ...
user avatar
13 votes

Pathfinding with lock and key?

Backwards A* will do the trick As discussed in this answer to a question about forward vs backward pathfinding, pathfinding backwards is a relatively simple solution to this problem. This works very ...
user avatar
  • 2,430
13 votes

How to reduce the time taken to path-find to an unreachable location?

You should make a sort of connectivity map - by flood-filling all unconnected walkable areas and marking each one with a different tag, once at game start (and every time when terrain changes). Then, ...
user avatar
  • 10k
13 votes

A* Algorithm for Tactical RPGs?

When you want all possible movement options of a unit, use Dijkstra's Algorithm. The difference between A* and Dijkstra is that Dijkstra gives you all the possible shortest routes achievable with a ...
user avatar
  • 111k
12 votes
Accepted

Is there a way to display navmesh agent path in Unity?

It's actually really simple. First you put a line renderer component on your nav mesh agent object. If you notice, there is an array called positions. So if you attach the following script to your nav ...
user avatar
12 votes

How can I make A* finish faster when the destination is impassable?

Assuming the issue is the destination is unreachable. And that the navigation mesh isn't dynamic. The easiest way to do this is have a much sparser navigation graph (sparse enough that a full run ...
user avatar
12 votes
Accepted

Pathfinding: Tile-Based Navigation Mesh

Yes, navigation meshes are still applicable to tile based games. Although, they would primarily be used as a optimization. For example, I've converted the lower left of your image to use a navigation ...
user avatar
  • 72.7k
12 votes

Determine route between rooms

You have a common misconception. A* isn't made for grids, it usually uses graphs. A grid is just a specialized graph with each node having 4 edges (apart from the edges and corners).
user avatar
  • 14.5k
11 votes
Accepted

Reconciling Flocking and A* (Theory)

The contradiction Indeed the two systems are quite exclusive to one another. As you mentioned: A*: that's just used to find a path, and during movement flocking is the only > way it manages ...
user avatar
  • 421
10 votes
Accepted

How are flow fields different from potential fields?

A potential field is a type of scalar field. In contrast, a flow field is a vector field. These are essentially just multidimensional arrays that are used as low level data structures for various ...
user avatar
  • 2,308
10 votes
Accepted

How do I calculate paths for objects with limited acceleration?

I haven't worked through the full equations for this yet, but here's some visuals to help wrap our heads around the problem. It boils down to some geometry: (Car icons via Kenney) From any given ...
user avatar
  • 113k
10 votes

Is A* efficient even when the obstacles are moving?

Yes. A* is still the way to go in almost every case. It's your node cost calculation that becomes dynamic and therefore more complex to calculate and track. If you already know where the moving ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible