Introducing
The Slant team built an AI & it’s awesome
Find the best product instantly
Add to Chrome
Add to Edge
Add to Firefox
Add to Opera
Add to Brave
Add to Safari
Try it now
4.7 star rating
0
Development
Game Development
What are the best 2D pathfinding algorithms?
3
Options
Considered
28
User
Recs.
Jan 24, 2024
Last
Updated
Related Questions
Activity
Have feedback or ideas?
Join our community
on Discord
Ad
3
Options
Considered
Best 2D pathfinding algorithms
Price
Last Updated
--
A* Algorithm
-
Jan 24, 2024
--
Dijkstra's Algorithm
-
Mar 8, 2023
--
Breadth-first search
-
Jun 7, 2020
See Full List
--
A* Algorithm
My Rec
ommendation
for
A* Algorithm
My Recommendation for
A* Algorithm
All
4
Pros
3
Cons
1
Top
Pro
•••
Complete
A* is complete, which means that it will always find a solution if it exists.
See More
Top
Con
•••
Not useful if you have many target nodes
If you have many target nodes and you don't know which one is closest to the main one, A* is not very optimal. This is because it needs to be run several times (once per target node) in order to get to all of them.
See More
Top
Pro
•••
Can be morphed into other algorithms
A* can be morphed into another path-finding algorithm by simply playing with the heuristics it uses and how it evaluates each node. This can be done to simulate Dijkstra, Best First Search, Breadth First Search and Depth First Search.
See More
Top
Pro
•••
Heuristic
A* expands on a node only if it seems promising. It's only focus is to reach the goal node as quickly as possible from the current node, not to try and reach every other node.
See More
Hide
See All
Get it
here
Recommend
20
--
Dijkstra's Algorithm
My Rec
ommendation
for
Dijkstra's Algorithm
My Recommendation for
Dijkstra's Algorithm
All
4
Pros
2
Cons
2
Top
Pro
•••
Uninformed algorithm
Dijkstra is an uninformed algorithm. This means that it does not need to know the target node beforehand. For this reason it's optimal in cases where you don't have any prior knowledge of the graph when you cannot estimate the distance between each node and the target.
See More
Top
Con
•••
A* is strictly superior
See More
Top
Pro
•••
Good when you have multiple target nodes
Since Dijkstra picks edges with the smallest cost at each step it usually covers a large area of the graph. This is especially useful when you have multiple target nodes but you don't know which one is the closest.
See More
Top
Con
•••
Fails for negative edge weights
If we take for example 3 Nodes (A, B and C) where they form an undirected graph with edges: AB = 3, AC = 4, BC=-2, the optimal path from A to C costs 1 and the optimal path from A to B costs 2. If we apply Dijkstra's algorithm: starting from A it will first examine B because it is the closest node. and will assign a cost of 3 to it and therefore mark it closed which means that its cost will never be reevaluated. This means that Dijkstra's cannot evaluate negative edge weights.
See More
Hide
See All
Get it
here
Recommend
5
1
--
Breadth-first search
My Rec
ommendation
for
Breadth-first search
My Recommendation for
Breadth-first search
All
4
Pros
2
Cons
2
Top
Pro
•••
Complete
BFS is complete, which means that it will always find a solution if it exists.
See More
Top
Con
•••
Requires a large amount of memory
When traversing one tree level, you need a way to know which nodes to traverse once you get to the next one. The way this is done is by storing the pointers to a level's child nodes while searching it. The pointers are stored in a FIFO way, this means that BFS needs a relatively large amount of memory in order to store the pointers. The amount of course depends on the complexity of the graph tree and the amount of nodes and/or levels.
See More
Top
Pro
•••
Optimal for finding the shortest path in a graph
BFS is very useful when you want to find the shortest and most optimal path by traversing as few edges as possible.
See More
Top
Con
•••
Trivial to implement
See More
Hide
See All
Get it
here
Recommend
2
Don't see your favorite option? Add it.
Built By the Slant team
Find the best product instantly.
4.7 star rating
Add to Chrome
Add to Edge
Add to Firefox
Add to Opera
Add to Brave
Add to Safari
Try it now - it's free
One sec!
Are you sure that you want to abandon your hard work?
Delete Work
Continue working
{}
undefined
url next
price drop