Stack Overflow
Stack Overflow

Questions tagged [path-finding]

Pathfinding generally refers to the problem of finding the shortest route between two points, subject to any obstacles. Pathfinding has application in a wide range of areas including robotics and game development. Algorithms for pathfinding tend to be closely related to graph and tree search algorithms.

Pathfinding generally refers to the problem of finding the shortest route between two points, subject to any obstacles. Pathfinding has application in a wide range of areas including robotics and game development. Algorithms for pathfinding tend to be closely related to graph and tree search algorithms.

Significant Literature

External Links

Related Tags

1746 questions
567
votes
18 answers

What algorithms compute directions from point A to point B on a map?

How do map providers (such as Google or Yahoo! Maps) suggest directions? I mean, they probably have real-world data in some form, certainly including distances but also perhaps things like driving speeds, presence of sidewalks, train schedules, etc.…
A. Rex
  • 31,633
  • 21
  • 89
  • 96
322
votes
22 answers

Pacman: how do the eyes find their way back to the monster hole?

I found a lot of references to the AI of the ghosts in Pacman, but none of them mentioned how the eyes find their way back to the central ghost hole after a ghost is eaten by Pacman. In my implementation I implemented a simple but awful solution. I…
RoflcoptrException
  • 51,941
  • 35
  • 152
  • 200
76
votes
5 answers

Difference and advantages between dijkstra & A star

I read this: http://en.wikipedia.org/wiki/A*_search_algorithm It says A* is faster than using dijkstra and uses best-first-search to speed things up. If I need the algorithm to run in milliseconds, when does A* become the most prominent choice. From…
AturSams
  • 7,568
  • 18
  • 64
  • 98
50
votes
8 answers

Generating a tower defense maze (longest maze with limited walls) - near-optimal heuristic?

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's…
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
40
votes
4 answers

Is A* the best pathfinding algorithm?

It is generally said that A* is the best algorithm to solve pathfinding problems. Is there any situation when A* is not the best algorithm to find solution? How good is A* compared to BFS, DFS, UCS, etc?
Zombie
  • 493
  • 1
  • 8
  • 11
40
votes
9 answers

Longest word chain from a list of words

So, this is a part of a function I'm trying to make. I don't want the code to be too complicated. I have a list of words, e.g. words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse'] The idea of the word chain…
Matt
  • 809
  • 1
  • 10
  • 22
40
votes
5 answers

A* Admissible Heuristic for die rolling on grid

I need some help finding a good heuristic for the following problem: You are given an R-by-C grid and a six-sided die. Let start and end be two distinct cells on this grid. Find a path from start to end such that the sum of the faces of the…
Paul Manta
  • 30,618
  • 31
  • 128
  • 208
39
votes
7 answers

Where can I find information on the D* or D* Lite pathfinding algorithm?

There are links to some papers on D* here, but they're a bit too mathematical for me. Is there any information on D*/D* Lite more geared towards beginners?
tehalynn
  • 399
  • 1
  • 3
  • 3
38
votes
10 answers

Copy path/file name in Eclipse to clipboard

Is there a shortcut to copy the current path/file to the clipboard?
user710818
  • 23,228
  • 58
  • 149
  • 207
35
votes
4 answers

AI of spaceship's propulsion: land a 3D ship at position=0 and angle=0

This is a very difficult problem about how to maneuver a spaceship that can both translate and rotate in 3D, for a space game. The spaceship has n jets placing in various positions and directions. Transformation of i-th jet relative to the CM of…
javaLover
  • 6,347
  • 2
  • 22
  • 67
32
votes
9 answers

Algorithm to find two points furthest away from each other

Im looking for an algorithm to be used in a racing game Im making. The map/level/track is randomly generated so I need to find two locations, start and goal, that makes use of the most of the map. The algorithm is to work inside a two dimensional…
Mizipzor
  • 51,151
  • 22
  • 97
  • 138
30
votes
6 answers

Find the shortest fence that encloses an area on a 2D grid

I have a 50 x 50 2D grid. Grid cells can have one of three states: 1: "inside" 2: "empty" 3: "wall" My initial configuration is a grid with some cells (maybe 10% of them, mostly contiguous) marked as "inside". Randomly there are some "wall" cells…
John Shedletsky
  • 7,110
  • 12
  • 38
  • 63
30
votes
10 answers

Solve all 4x4 mazes simultaneously with least moves

I came across this quite interesting problem, where we have a 4x4 maze and a robot in it trying to get to the goal. The thing is, you have to find a sequence of predefined commands that will always result in the robot reaching the goal. Let's say we…
Olavi Mustanoja
  • 2,045
  • 2
  • 23
  • 34
27
votes
1 answer

Pathfinding (routing, trip planning, ...) algorithms on graphs with time restrictions

I have a database of bus/train/... stops and the arrival/departure times on each date and so on. I'm looking for a way to do a search for the fastest(shortest/cheapest/least transitions) trip between two locations. I would like to have arbitrary…
lacop
  • 2,024
  • 4
  • 22
  • 36
26
votes
11 answers

PacMan: what kinds of heuristics are mainly used?

Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find. I need some good path-finding…
IcySnow
  • 851
  • 2
  • 14
  • 23
1
2 3
…
99 100