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
  • 130k
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,106
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
  • 130k
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,019
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 ...
JackFrost's user avatar
  • 542
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.8k
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 ...
Engineer's user avatar
  • 29.3k
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
  • 118k
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,450
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.6k
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
  • 118k
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.8k
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 ...
DMGregory's user avatar
  • 130k
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
10 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
  • 591
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
  • 130k
8 votes
Accepted

Special Pathfinding Algorithm

A* would work fine for this task, but since your map is small, Breadth First Search would work too, and it's even simpler than A*. These are “graph search” algorithms, which require you to tell them ...
amitp's user avatar
  • 6,036
8 votes

Cossacks game pathfinding

I don't know which technique was specifically used in Cossacks, but I guess you are also interested in the problem at hand in general terms. In fact, nowadays, there are ways trough which such result ...
MAnd's user avatar
  • 4,907
8 votes
Accepted

What is best method for 2D pathfinding in procedural world?

As you shall see, the spirit of this answer is that, in game programming, there is rarely a dead-on answer like A is always better than B. But let's dive a bit more into the details. So my main ...
MAnd's user avatar
  • 4,907
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
  • 130k
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
  • 328
7 votes

What is the most appropriate path-finding solution for a very large proceduraly generated environment?

I'm going to take a stab and recommend a hierarchical pathfinding algorithm, such as HPA*. Even though I'm not an expert in AI, I'm fairly confident in this guess because your generator sounds almost ...
congusbongus's user avatar
  • 14.8k
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,609
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

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