Stack Overflow
Stack Overflow

Questions tagged [a-star]

A* is a graph shortest-path algorithm that uses a heuristic function to speed up the search

A* is a single source shortest path algorithm that use a heuristic function in order to speed up its search. The algorithm is similar to dijkstra's algorithm, but uses the heuristic evaluation of each node to determine which node should first be explored.

The A* algorithm is both complete [will always find a path if one exists] and optimal [finds the shortest path] if the heuristic function provided is admissible. If more than one path exists with the same "lowest" cost score, the algorithm will return the path first explored.

Usage example: Finding a path for an agent on a grid-like plane, from a single source to a target.

1187 questions
175
votes
12 answers

How does Dijkstra's Algorithm and A-Star compare?

I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm. (Video of Mario A* Bot In Action) My question is, how does A-Star…
KingNestor
  • 65,976
  • 51
  • 121
  • 152
114
votes
7 answers

What is the difference between graph search and tree search?

What is the difference between graph search and tree search versions regarding DFS, A* searches in artificial intelligence?
Rayhanur Rahman
  • 1,141
  • 2
  • 8
  • 4
72
votes
9 answers

A* Algorithm for very large graphs, any thoughts on caching shortcuts?

I'm writing a courier/logistics simulation on OpenStreetMap maps and have realised that the basic A* algorithm as pictured below is not going to be fast enough for large maps (like Greater London). The green nodes correspond to ones that were put…
drspa44
  • 1,041
  • 8
  • 12
47
votes
4 answers

Consistent and Admissible Heuristics

Any consistent heuristic is also admissible. But when is a heuristic admissible but not consistent (monotone)? Please provide an example in which this is the case.
RoarG
  • 793
  • 1
  • 7
  • 20
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
2 answers

How to implement an A* algorithm?

Which should be the way to get a simple implementation of A* (A star) algorithm in C#?
A New Chicken
  • 703
  • 1
  • 8
  • 18
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
35
votes
3 answers

Python - Speed up an A Star Pathfinding Algorithm

I've coded my first slightly-complex algorithm, an implementation of the A Star Pathfinding algorithm. I followed some Python.org advice on implementing graphs so a dictionary contains all the nodes each node is linked too. Now, since this is all…
DizzyDoo
  • 1,489
  • 6
  • 21
  • 32
34
votes
10 answers

How to optimally solve the flood fill puzzle?

I like playing the puzzle game Flood-It, which can be played online at: https://www.lemoda.net/javascript/flood-it/game.html It's also available as an iGoogle gadget. The aim is to fill the whole board with the least number of successive…
felix
  • 647
  • 1
  • 6
  • 10
30
votes
1 answer

AStar - explanation of name

I am looking for an explanation why the AStar / A* algorithm is called AStar. All similar (shortest path problem) algorithms are often named like its developer(s), so what is AStar standing for?
lale liley
  • 333
  • 3
  • 8
26
votes
0 answers

How do I implement an A* pathfinding algorithm, with movement costs for every programming language?

Can we get people to post code of simple, optimized implementations of the A* pathfinding algorithm, in every single language? This is mostly for fun and to play with what stackoverflow itself is capable of... although I actually am interested in…
IQpierce
  • 501
  • 2
  • 8
  • 17
25
votes
6 answers

A* heuristic, overestimation/underestimation?

I am confused about the terms overestimation/underestimation. I perfectly get how A* algorithm works, but i am unsure of the effects of having a heuristic that overestimate or underestimate. Is overestimation when you take the square of the direct…
Mads Andersen
  • 3,123
  • 5
  • 38
  • 44
24
votes
6 answers

Using A* to solve Travelling Salesman

I've been tasked to write an implementation of the A* algorithm (heuristics provided) that will solve the travelling salesman problem. I understand the algorithm, it's simple enough, but I just can't see the code that implements it. I mean, I get…
Puppy
  • 144,682
  • 38
  • 256
  • 465
23
votes
2 answers

A* admissible heuristics on a grid with teleporters?

Suppose that you have a 2D grid of cells, some of which are filled in with walls. Characters can take a step from one square to any square that is one step horizontal or vertical from it, but cannot cross walls. Given a start position and an end…
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
22
votes
7 answers

Pathfinding on large map

I'm creating a game with a 10,000 by 10,000 map. I would like for a user to be able to set a location and have the computer instantly find the best path. However, since the map is 10,000 by 10,000, there are 100,000,000 nodes, and to find this path…
James McDowell
  • 2,668
  • 1
  • 14
  • 27
1
2 3
…
78 79