Questions tagged [path-finding]

Methods used to map out a path of travel from one point to another, typically avoiding obstacles in the way.

Filter by
Sorted by
Tagged with
67
votes
7answers
15k 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.
79
votes
5answers
35k 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 ...
9
votes
3answers
2k 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 ...
24
votes
1answer
39k 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 ...
33
votes
12answers
7k 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 ...
14
votes
2answers
7k 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: ...
7
votes
2answers
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 ...
11
votes
2answers
3k 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 ...
7
votes
3answers
3k 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?
1
vote
1answer
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 ...
0
votes
1answer
261 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 ...
61
votes
6answers
5k 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 ...
19
votes
3answers
14k 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 ...
36
votes
4answers
13k 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?
16
votes
9answers
7k 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 ...
12
votes
3answers
6k 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 ...
8
votes
3answers
6k 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 ...
11
votes
2answers
5k 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 ...
11
votes
3answers
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 ...
5
votes
1answer
804 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 ...
3
votes
2answers
555 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 / ...
2
votes
3answers
2k views

Pathfinding for units of variable size

I'm using a grid map for a top-down RTS, and using a* for pathfinding. Specifically, I've found one implementation which is heavily optimised, and I've been using it for a while, but now I've realised ...
2
votes
1answer
327 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 ...
1
vote
2answers
2k 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 ...
16
votes
6answers
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 ...
15
votes
1answer
6k 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 ...
12
votes
1answer
9k 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 '...
7
votes
2answers
2k 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? ...
4
votes
4answers
5k 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 ...
12
votes
1answer
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 ...
6
votes
4answers
8k 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 ...
5
votes
1answer
680 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 ...
3
votes
1answer
3k 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 ...
3
votes
1answer
1k 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 ...
7
votes
2answers
4k 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 ...
1
vote
2answers
2k 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 ...
4
votes
2answers
2k 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 ...
3
votes
2answers
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
3answers
902 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 ...
43
votes
7answers
26k 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 ...
49
votes
11answers
48k 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?
30
votes
2answers
4k 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. ...
28
votes
6answers
6k 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* ...
19
votes
7answers
6k views

How do I make A* agents avoid other agents?

I'm implementing a multi agent A* algorithm on a tile map. Agents move only in the X and Y axes. I avoid collisions between them by checking where the others are when calculating paths. It works fine ...
9
votes
3answers
11k views

How can I generate a 2d navigation mesh in a dynamic environment at runtime?

So I've grasped how to use A* for path-finding, and I am able to use it on a grid. However, my game world is huge and I have many enemies moving toward the player, which is a moving target, so a grid ...
8
votes
1answer
3k views

Pathfinding: Tile-Based Navigation Mesh

I'm developing a real time, tile-based RTS. This is an example map: This map consists of 4 regions with 256 tiles each. Blue tiles represent obstacles. Units can move in the standard eight directions....
27
votes
3answers
30k 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.
25
votes
4answers
8k 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 ...
16
votes
6answers
1k views

Making the AI take different paths to each other

I have a top down 2d game where the AI spawn at the edges of the map and run towards the center. I'm using A* and a node mesh to do the pathfinding. Right now, the AI spawn at a point on the edge of ...
14
votes
1answer
4k 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 ...