Re:Show HN: BFS, Dijkstra and A* interactive demo made in React
by psyc on Monday January 18, 2021 @11:27AM
(#25823333)
That was also my introduction to A*. Say, does anyone have insights into optimizing path finding for speed, as the map gets larger and number of entities increases?
[ Parent
| on HN ]
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React
by Vvector on Monday January 18, 2021 @11:59AM
(#25823748)
One method is to preprocess the map, which then can greatly increase the accuracy of the A* heuristic.
Re:Show HN: BFS, Dijkstra and A* interactive demo made in React
by mysterydip on Monday January 18, 2021 @12:04PM
(#25823810)
I would think you could do a scaling of sorts, like if your map was 100x100 you could reduce it to 10x10 with "clear", "fully blocked", and "partially blocked" based on the contents, and work a general path at that meta level first, then focus on each grid map at the full scale to navigate around local obstacles. You could do multiple scales depending on your needs and where the terrain makes sense to categorize most into clear or blocked.