Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualCornstalks

Posted 08 January 2013 - 01:23 PM

One way to speed up A* (and can be used in combination with Heiarchial A*) is Jump Point Search A* (not for the feint of heart!).

 

I did something similar to what I think IADaveMark is suggesting. In school my team and I made a game where you were a marine battling hundreds and hundreds of zerglings. A* was way too slow for the zerglings' AI, so instead we did a Dijkstra flood-fill search (starting from the player's location), linking tiles together back to the player (the benefit is that it only requires one search, regardless of how many units you have). That way, each zergling could query the tile they were on top of to know which tile they should move to next in order to progress to the player. We supplemented this with a flocking algorithm so that the zerglings wouldn't line up single file, but instead would properly bunch up around the player. It worked decently enough even with hundreds of zerglings. With more time it could've been perfected, but I'd suggest this method if you've only got one player and many units trying to get to that one player.


#1Cornstalks

Posted 08 January 2013 - 01:13 PM

One way to speed up A* (and can be used in combination with Heiarchial A*) is Jump Point Search A* (not for the feint of heart!).

 

I did something similar to what I think IADaveMark is suggesting. In school my team and I made a game where you were a marine battling hundreds and hundreds of zerglings. A* was way too slow for the zerglings' AI, so instead we did a Dijkstra flood-fill search (starting from the player's location), linking tiles together back to the player. That way, each zergling could query the tile they were on top of to know which tile they should move to next in order to progress to the player. We supplemented this with a flocking algorithm so that the zerglings wouldn't line up single file, but instead would properly bunch up around the player. It worked decently enough even with hundreds of zerglings. With more time it could've been perfected, but I'd suggest this method if you've only got one player and many units trying to get to that one player.


PARTNERS