Questions tagged [path-finding]
Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.
102
questions
68
votes
7
answers
20k
views
How does A* pathfinding work?
I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.
- 1,775
80
votes
5
answers
43k
views
How does Dwarf Fortress keep track of so many entities without losing performance?
In Dwarf Fortress you can have hundreds of Dwarves, animals, goblins, etc in game at any one time, each with their own complex AI and pathfinding routines. My question is how does this not produce ...
- 1,422
11
votes
3
answers
3k
views
How do I calculate paths for objects with limited acceleration?
For example, say I have a car and a car has a specific minimum turning radius and I want to drive that car from point a to point b, but the car isn't facing point b. How do I compute a path to point ...
- 484
6
votes
2
answers
2k
views
How can I maneuver an AI pirate ship for a sea battle?
I'm trying to picture in my head what would be required to make an AI controlled enemy do the following in a top down pirate sailing game:
Approach the player ship
Bring player in line with port / ...
- 163
34
votes
12
answers
9k
views
How can I make A* finish faster when the destination is impassable?
I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an ...
- 559
26
votes
1
answer
42k
views
Path finding algorithms?
I posted this question on stack overflow first, but I guess no one is very interested in video games there...
What are some path finding algorithms used in games of all types? (Of all types where ...
- 381
15
votes
2
answers
9k
views
How do I implement group formations in a 3D RTS?
I managed to get pathfinding work for a single unit, and I managed to avoid agent-agent collision, but now I need to be able to send a group of agents to some location.
This is my set-up so far:
...
- 488
7
votes
3
answers
6k
views
Path finding in grid for objects that occupy more than one tile
In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?
- 595
2
votes
3
answers
3k
views
Pathfinding for units of variable size
I'm using a grid map for a top-down RTS, and I am using the a*
algorithm for pathfinding. Specifically, I've found one implementation which is heavily optimized, and I've been using it for a while, ...
- 595
40
votes
4
answers
19k
views
How does Flow Field pathfinding work?
Supreme Commander 2 has something called flow field path finding. How does it work? Is there some article available I can read up on how it works?
- 1,461
13
votes
2
answers
5k
views
Tweaking AStar to find closest location to unreachable destination
I've implemented AStar in Java and it works ok for an area with obstacles where the chosen destination is reachable.
However, when the destination is unreachable, the calculated "path" is in no way ...
- 1,400
8
votes
2
answers
2k
views
Multi-tile agent path-finding algorithm?
Suppose we have a uniform rectanglular grid as shown below. The a is an agent, o is obstacle and ...
- 363
5
votes
1
answer
1k
views
Help me please to choose proper path-finding algorithm
I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario:
Units - any shape. But in most cases rectangles of different ...
- 161
3
votes
1
answer
4k
views
Pathfinding with different sized units [duplicate]
I am actually working on a general purpose pathfinding library (find it here), mostly oriented for grid-based maps.
I was looking for ways to integrate support for pathfinding with units of different ...
- 131
1
vote
2
answers
616
views
Efficiently determining which buildings are connected by roads
I have a question about the most effective way to detect road connection in a tile based world. Some time ago I already asked for "How to improve performance for expensive functions in 2d city builder"...
- 305
1
vote
1
answer
2k
views
finding a path from one point to another with obstacles help
Im building a tile based game and im implementing my path finding algorithm. Currently, it can find a path from point A to point B with no problems. However, if there are obstacles between point A and ...
- 33
0
votes
1
answer
756
views
Can't figure out what's making the player teleport back to spawn
I've been working on a multiplayer game that uses pathfinding and I'm really confused over this one weird bug. On your screen, the other player glitches between the spawn point and his current ...
- 3
65
votes
6
answers
7k
views
Pathfinding for fleeing
As you know there are plenty of solutions when you wand to find the best path in a 2-dimensional environment which leads from point A to point B.
But how do I calculate a path when an object is at ...
- 119k
19
votes
3
answers
17k
views
Real Time Dynamic Pathfinding?
I'm currently doing some pathfinding research and my simulation is the following:
I have a 3d scene with a start and end point represented, I'm capable of creating navigational meshes, waypoints and ...
- 191
16
votes
9
answers
8k
views
Dynamic pathing algorithm for tower defense game
I'm making a Tower Defense and I need a good pathing algorithm for it.
I have thought about Dijkstra but I need one that can be dynamic; it must be able to update itself when one edge is removed or ...
- 549
12
votes
2
answers
6k
views
How to calculate the vector of an interception?
Given are a twodimensional space, and 1 friendly spaceship standing still, one foe is moving NOT directly to the friendly ship with known actual position, speed and direction.
The friendly ship wants ...
- 231
12
votes
3
answers
7k
views
Moving around/avoiding obstacles
I would like to write a "game", where you can place an obstacle (red), and then the black dot tries to avoid it, and get to the green target.
I'm using a very easy way to avoid it, if the black dot is ...
- 257
11
votes
3
answers
2k
views
Algorithm to see if two voxels are interconnected
I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to ...
- 195
10
votes
3
answers
9k
views
A star pathfinding and discrete/smooth positions
The A* (A-star) algorithm usually represents a path on a grid.
Once a path has been found, however, the path looks blocky and is not suited if you move your units with floating point datatypes.
Here ...
- 5,243
9
votes
1
answer
8k
views
How can I adapt A* pathfinding to work with platformers?
I have an A* implementation that works in "top down" situations where gravity is not taken into account for pathfinding. But, I am looking to modify to work in a 2d platformer situation. I am using ...
7
votes
4
answers
10k
views
Smoothing found path on grid
I implemented several approaches such as A* and Potential fields for my tower defense game. But I want smooth paths, first I tried to find path on very small grid ( 5x5 pixels per tile) but it is ...
- 242
3
votes
1
answer
683
views
Tile Based A* Pathfinding, but with a bomb
I've written a simple A* path finding algorithm to quickly find a way through a tile based dungeon in which the tiles contain the information of walls.
An example of a dungeon (only 1 path for ...
- 33
3
votes
1
answer
2k
views
A* Pathfinding Finding One of Many Goals
I have my A* pathfinding algorithm right now working such that given a graph it can find the route from one starting node to one goal node.
This works well for many problems, but sometimes I find ...
- 33
1
vote
2
answers
3k
views
How to make a gui button follow a path after a touch?
I would like a button in my gui menu to follow a specific path if we selected it, I am wondering how I could do it: if we touch the button, then it can only move on the specific path, it is an arc ...
- 679
1
vote
2
answers
3k
views
How can I implement platformer pathfinding?
I've gone through A* pathfinding but could find anything on this. What I'm looking for is pathfinding for something kind of like a super smash bros level with different platforms. Can anyone point me ...
- 13
16
votes
1
answer
8k
views
A* navigational mesh path finding
So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world ...
- 261
16
votes
6
answers
2k
views
How to make my characters turn smoothy while walking on a path(list of coordinates)?
I have a list with coordinates - output from A* algorithm - and I would like to make my characters smoothly follow this path with rotations.
So I have something like A and I want to get C
How can I ...
- 397
15
votes
1
answer
7k
views
How does the Simple Stupid Funnel Algorithm work?
Working with the funneling algorithm shown on Digesting Duck I'm not sure how the detection of the funnel works.
Can someone explain the method clearly to me or suggest an alternative way of ...
- 159
13
votes
1
answer
3k
views
Efficient path-finding in free space
I've got a game situated in space, and I'd like to issue movement orders, which requires pathfinding. Now, it's my understanding that A* and such mostly apply to trees, and not empty space which does ...
- 5,518
12
votes
1
answer
13k
views
Pathfinding with 2D, non-grid based movement over uniform terrain
I'm looking for the best solution to pathfinding in my game. The map is ultimately grid-based, but entities are positioned using floats, and can move in any direction to any point on the map. The '...
- 265
9
votes
2
answers
4k
views
What is the most appropriate path-finding solution for a very large proceduraly generated environment?
I have been reading quite a bit in order to make the following choice: which path-finding solution should one implement in a game where the world proceduraly generated, of really large dimensions?
...
- 476
8
votes
2
answers
7k
views
How to find a safe path for an AI snake?
I have been working on a game in which a player can compete with a snake ai to get the most apples. The current path finding technique i use (A* Pathfinding) works fine. But I am struggling with ...
- 208
5
votes
1
answer
789
views
Verify which bubble is connected to top using DFS
I am working on a bubble shooter game in this game i have implemented searching using DFS as suggested in this link, and this is working fine.
Update
Here is my ...
- 61
4
votes
2
answers
5k
views
Forward A-star pathfinding vs Reverse A-star pathfinding
Under what condition does doing Forward path finding or Reverse pathfinding get better result? Most tutorials for open grid tower defence games says to pathfind from the Goal to the monster. Why is it ...
- 1,431
4
votes
4
answers
6k
views
Efficient path-finding on 2D tile-based multilevel map
It's a question I've been thinking about for some time... How do you effiently find a path on a 2D tile-based multilevel map? The map I use, for example, is 2048 on 2048 tiles wide. It has 14 levels ...
- 43
3
votes
2
answers
16k
views
Pseudo-code examples of A*? [closed]
I'm looking for pseudo-code examples of the A* pathfinding algorithm that actually works. I tried plenty of different ones where it's not really clear how to implement them at all times. Keep in mind ...
3
votes
3
answers
1k
views
Possible A* Optimizations [closed]
I have implemented A* in my game. However, I am not happy with the performance and need some help deciding what to do next.
I have already done the following optimizations:
Not having a closed list ...
- 352
3
votes
1
answer
2k
views
Pathfiding for groups of agents
How can we refine this path search method to make group movement more elegant? I'm trying to make a RTS-style game, using a 2d tiled gameworld. I have implemented an A* pathfinding algorithm which ...
- 766
2
votes
3
answers
3k
views
Displaying possible movement tiles
What's the fastest way to highlight all possible movement tiles for a player on a square grid? Players can only move up, down, left, right. Tiles can cost more than one movement, multiple levels are ...
- 254
51
votes
11
answers
58k
views
What path finding algorithms are there? [closed]
I'd like to read up on path finding algorithms. Is there a primer available or any material or tutorials on the Internet that would be a good start for me?
47
votes
9
answers
34k
views
How does pathfinding in RTS games work?
[crossposted from stackoverflow]
In a game such as Warcraft 3 or Age of Empires, the ways that an AI opponent can move about the map seem almost limitless. The maps are huge and the position of other ...
- 471
30
votes
6
answers
7k
views
what is the standard solution to pathfinding towards a moving target?
I am working on a 2D RTS like game, basic A* works perfectly for moving a unit from point A to point B.
But now I facing the continuous path-finding problem, like A attack a moving object B, call A* ...
- 501
30
votes
2
answers
5k
views
Is A* efficient even when the obstacles are moving?
I'm just starting to learn about path-finding and have been looking into the A* algorithm and my main concern is that it all of the examples I have seen show static obstacles that it computes around.
...
- 752
28
votes
3
answers
35k
views
How does Navigation Mesh path-finding work?
I want to understand how navmeshes work, how to implement them and why it is better than other types of pathing systems.
- 742
27
votes
4
answers
12k
views
Is the Manhattan distance monotonic when used as heuristic function?
I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1.
I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
- 515