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....
- 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 ...
- 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 ...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 11.7k
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
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: ...
- 617
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 ...
- 10.1k
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.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 ...
- 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, ...
- 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 ...
- 21.1k
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.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, ...
- 11.7k
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,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, ...
- 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 ...
- 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 ...
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 ...
- 8,323
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 ...
- 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).
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 11.7k
Only top scored, non community-wiki answers of a minimum length are eligible