Pathfinding to a moving target in evolving terrain
64 points by friendshaver 20 hours ago | 6 comments
  • porphyra 16 hours ago |
    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 4 hours ago |
      I wonder if there are any constraints on the buildings etc that make this easier.
  • a13n 10 hours ago |
    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 2 hours ago |
      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 5 hours ago |
    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 2 hours ago |
      >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.