Is it possible to use Dijkstra search in Navigation2D?

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Robotex

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?

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

Ertain | 2021-06-26 08:55

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

Robotex | 2021-06-29 09:34

2
:bust_in_silhouette: Reply From: Kolandrious

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.