# What are the best 2D pathfinding algorithms?

3

Options Considered

Last Updated

Activity

Here’s the Deal

Slant is written by a community helping you be informed. Tell us what you’re passionate about to get an awesome personalized feed.

Recommend your favorite options here

Breadth-first search

Recommended a month ago by TalentedPapsukkal

TalentedPapsukkal hasn’t added their experience, pros or cons to their recommendation.

A* Algorithm

Recommended 5 months ago by WiseCermait

WiseCermait hasn’t added their experience, pros or cons to their recommendation.

Dijkstra's Algorithm

Recommended 2 years ago by Vlad

Pro

Good when you have multiple target nodesPro

Uninformed algorithmA* Algorithm

Recommended 2 years ago by Brian

Brian hasn’t added their experience, pros or cons to their recommendation.

A* Algorithm

Recommended 2 years ago by Jules

Jules hasn’t added their experience, pros or cons to their recommendation.

Dijkstra's Algorithm

Recommended 2 years ago by ideasman42

ideasman42 hasn’t added their experience, pros or cons to their recommendation.

Dijkstra's Algorithm

Recommended 2 years ago by Pedro

Pro

Good when you have multiple target nodesPro

Uninformed algorithmA* Algorithm

Recommended 2 years ago by Pedro

Pro

HeuristicPro

CompletePro

Can be morphed into other algorithmsThe Slant community took these options into consideration for this question.

If you feel one should be highly recommended please vote for it.

If you feel one should be highly recommended please vote for it.

Pro

HeuristicA* 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.

Con

Not useful if you have many target nodesIf 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.

Pro

Uninformed algorithmDijkstra 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.

Con

Fails for negative edge weightsIf 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 n...

Pro

CompleteBFS is complete, which means that it will always find a solution if it exists.

Con

Requires a large amount of memoryWhen 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...

Welcome to the Slant Community

Stop spending hours researching

Slant is written by a community helping you be informed. Let us know what you’re passionate about to get an awesome personalized feed.