Is it possible to use Dijkstra search in Navigation2D?

0 votes

I need to find the closest pickable item on map. Closest not by straight line (it's a labyrinth) but by shortest path. How to do this in Godot without implementation of custom navgraph?

in Engine by (273 points)

Have you tried using AStar? It works quite well, from what I've read.

by (3,072 points)

And do this search for each item on map? There are hundreds of them. It's too expensive. I need Dijkstra

by (273 points)

1 Answer

0 votes

I think, you will have to code BFS algorithm for this kind of task find the closest out of hundreds in a maze. Also, the algorithm might take more time if the closest item appears to be far away. Consider splitting the map into cells and flag cells as "has items" and "has no items", this may help you decrease the number of items to check against and build your graph.

Hope that helps.

by (26 points)
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read Frequently asked questions and How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to [email protected] with your username.