[HN Gopher] Pathfinding to a moving target in evolving terrain
       ___________________________________________________________________
        
       Pathfinding to a moving target in evolving terrain
        
       Author : friendshaver
       Score  : 67 points
       Date   : 2025-01-10 23:50 UTC (23 hours ago)
        
 (HTM) web link (www.holm.dog)
 (TXT) w3m dump (www.holm.dog)
        
       | porphyra wrote:
       | Pathfinding is a profoundly interesting problem. I think it is
       | very impressive that Starcraft II still has amazing lag-free
       | pathfinding that beats or matches basically every game out there,
       | including very recent RTS games like Stormgate and Zerospace that
       | have a specific emphasis on smooth mechanics for competitive
       | play. Like you can build all kinds of buildings and a zillion
       | zerglings will instantly go around them.
        
         | HPsquared wrote:
         | I wonder if there are any constraints on the buildings etc that
         | make this easier.
        
       | a13n wrote:
       | Couldn't you just do a breadth first flood fill from the player
       | every time the environment changes? Would be O(n) where n is
       | total number of cells, which would be fast on any hardware or in
       | the browser.
       | 
       | You'd still want to use the directional chart idea.
        
         | poincaredisk wrote:
         | Or when player moves. But this is also something that came to
         | my mind. They acknowledge this in a footnote:
         | 
         | [3] The approach I ended up using is very similar to a Dijkstra
         | map, a pathfinding tool from roguelike games, which I
         | discovered as I was writing this. As far as I could tell, my
         | approach extends a Dijkstra map to handle minimal updates as
         | the target moves and obstacles update
        
       | deadbabe wrote:
       | Can't you just use web workers to offload A* path finding to a
       | separate thread and expose results to the main thread through
       | shared array buffers?
        
         | poincaredisk wrote:
         | > _just_ use web workers to offload A* ... shared buffers
         | 
         | That's a huge overkill. A single dijkstra per game tick (or
         | even only when map changes or player moves) is enough.
        
       ___________________________________________________________________
       (page generated 2025-01-11 23:02 UTC)