Skip to main content
Share Your Experience: Take the 2024 Developer 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....
DMGregory's user avatar
  • 135k
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 ...
Jack Aidley's user avatar
  • 2,126
28 votes

How can I shorten the length of time spent on finding a path using my A* pathfinding code?

Let's start with some general C# optimization advice: Avoid heap allocations in your hot path. That means anywhere you have new Foo(...) where ...
DMGregory's user avatar
  • 135k
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 ...
BlueRaja - Danny Pflughoeft's user avatar
24 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 ...
Liam Lime's user avatar
  • 728
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 ...
Jimmy's user avatar
  • 9,029
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 ...
Bálint's user avatar
  • 14.9k
14 votes

Maintaining unit formation while following path

My approach would be: Designate one soldier of the formation "the leader". (this does not necessarily need to be the actual commanding officer of the formation. You can pick any soldier. ...
Philipp's user avatar
  • 120k
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 ...
Chris Langtiw's 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 ...
Jibb Smart's user avatar
  • 2,460
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, ...
Kromster's user avatar
  • 10.7k
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 ...
Philipp's user avatar
  • 120k
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).
Bálint's user avatar
  • 14.9k
11 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 ...
DMGregory's user avatar
  • 135k
11 votes
Accepted

How to adapt pathfinding algorithms to restricted movement?

Welcome to the wonderful world of non-holonomic motion planning. I recommend doing this using a lattice grid path planner. Other alternatives include the kinodynamic RRT, and trajectory optimization. ...
mklingen's user avatar
  • 601
10 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 ...
MrBrushy's user avatar
  • 411
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 ...
Stephane Hockenhull's user avatar
9 votes
Accepted

Tile Based A* Pathfinding, but with a bomb

The typical approach here would be to treat your remaining bomb count as an additional dimension in the pathfinding space. So given this situation ...
DMGregory's user avatar
  • 135k
8 votes

How to generate a random path on a 2d Grid

One common way to solve this type of problem is to still use a shortest path algorithm like A* that takes into account traversal costs. We just lie to it about what's "shortest" ;) Here we assign our ...
DMGregory's user avatar
  • 135k
8 votes

Efficiently pathfinding many flocking enemies around obstacles

A* is not performance heavy. I would approach this situation by varying the algorithms. Do A* from time to time and in between check whether the next step is free to step onto or you need evasion. ...
D3d_dev's user avatar
  • 338
7 votes

Why is my A* Pathfinding incredibly slow?

I see a few issues. you are doing a lot of linear scans over vectors (at least 2 for each neighbour for each node you examine). This will be pretty slow. You don't even need the closed set if you ...
ratchet freak's user avatar
7 votes
Accepted

RTS pathfinding

With RTS pathfinding, your requirements are: You have to compute paths for all selected units fast. The pathfinding must take into account that a path may not be found (blocked) The pathfinding must ...
Ian Young's user avatar
  • 2,649
7 votes

How does HPA*(Hierarchical Pathfinding A*) really work?

One of the creators of HAA* (a generalization of HPA*) wrote a very accessible article explaining how it works on aigamedev.com. Unfortunately that site seems to be dead, but fortunately archive.org ...
BlueRaja - Danny Pflughoeft's user avatar
7 votes
Accepted

How would I actually implement A* pathfinding in a 3D world?

What A* needs to work is the following: Given the current node, get the list of possible nodes it can move to, with their costs. The ability to evaluate the heuristic function. Please notice I've ...
Theraot's user avatar
  • 27k
6 votes
Accepted

Pathfinding in non-quantized space?

Typically you would generate a visibility graph and perform pathfinding on that. Refer to this excellent page on map representations by amitp. Given an open space with polygonal obstacles, the ...
congusbongus's user avatar
  • 14.8k
6 votes

Pathfinding with lock and key?

Edit: This is written from the point of view of an AI that is out to explore and discover a goal, and does not know the location of keys, locks, or destinations ahead of time. First, assume that the ...
Tim Holt's user avatar
  • 10.3k
6 votes
Accepted

A* Pathfinding Finding One of Many Goals

There are just two changes you need to make to your A* implementation to handle pathfinding to multiple goals / multiple destinations: When expanding a node, instead of evaluating ...
DMGregory's user avatar
  • 135k
5 votes

How to find a safe path for an AI snake?

Take a look at https://github.com/stevennl/Snake, a project demonstrating a few AI algorithms for the game Snake. The project README has a very nice explanation of the algorithm. The key is for the ...
congusbongus's user avatar
  • 14.8k
5 votes
Accepted

How do you handle pathfinding for non-tilemap 2d games?

There is nothing about A* that is specific to a tile map or grid. A* is usable in any kind of directed graph so long as there is a usable heuristic - e.g., distance to destination. When there isn't a ...
Sean Middleditch's user avatar

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