Re:A* tricks for videogame path finding
by deadbabe on Monday January 01, 2024 @05:41PM
(#38835983)
Can someone share tips for A* pathfinding where NPCs have limited knowledge about the map, where they must got from point A to point B without knowing entirely about what’s in between?
[ Parent
| on HN ]
Micromouse competition is exactly about this. There are plenty of algorithms published. Some version of flood fill is the most popular I think.
Re:A* tricks for videogame path finding
by Sohcahtoa82 on Tuesday January 02, 2024 @02:05PM
(#38845575)
I would simply make the path finder assume all unknown areas are traversable. As the areas are discovered, you re-run the path finder. Eventually it will unveil enough of the map to find the path.
Of course, there's a possibility that the uncovered area of the map has a known possible path, but there's an undiscovered shorter path. You could tweak the cost of traveling through unknown areas to nudge the path finder towards or away from trying to travel through unknown areas of the map in case there's a shorter way.