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....
- 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 ...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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. ...
- 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 ...
- 231
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 ...
- 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, ...
- 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 ...
- 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).
- 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 ...
- 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 ...
- 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 ...
- 11.9k
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. ...
- 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
...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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.
...
- 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 ...
- 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 ...
- 7,041
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 ...
- 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 ...
Only top scored, non community-wiki answers of a minimum length are eligible