0
\$\begingroup\$

I'm looking to implement a pathfinding algorithm that will allow me to throw hundreds of spiders at the players in my grid-based game. I can implement this with A*, but I'm worried that that algorithm has too high of a "per spider" performance cost.

The "potential fields" approach looks really good to me, but my map is quite large and rebuilding the entire potential field sounds expensive (even on a background thread).

Unfortunately, there's no logical divisions on my map where I could separate the grid into smaller grids. And the map is quite dynamic (walls/bridges can be destroyed, which could have huge impacts on pathing).

Are there any options other than reducing the size of the map?

\$\endgroup\$
2
\$\begingroup\$

If you can't subdivide the grid then combine the spiders. Make each navigable spider represent a group of N spiders, then calculate one path and during your movement flow the N spiders out during placement and rendering.

I assume that you're not keeping individual stats on these hundreds, like Spider named "Leggy Bob" has 3 HP remaining while his neighbor "Mandible Sheila" has 4 HP. That would be silly.

\$\endgroup\$
2
\$\begingroup\$

You can amortize the cost of building the grid and computing the flow.

In a 60 FPS game, there is no need to compute it every frame. Once every 20 frames is more than fast enough.

So maybe just process 5% of the cells, each frame.

That said, with fields like this, you typically need to redo all the work for every group of NPCs that have a different goal.

You can also do SIMD processing of your grid. I personally did this with AVX Intrinsics in my steam game Imhotep, Pyramid Builder. I used 10 grids, one per goal, of size 128x128 cells. It pays if you can process 8 cells in a single instruction.

But the nice thing of these fields is, that once computed, you can have as many NPCs using it, as you want. As long as they share their goal. This allows for 1000s of agents doing pathfinding. Pathfinding this way is independent of the crowd size (cost is near-constant in crowd size, linear in number of different goals.)

\$\endgroup\$
  • \$\begingroup\$ "Once every 20 frames is more than fast enough" - even less than that. It only needs to be recomputed when the map changes. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Dec 21 '18 at 9:42
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft I implemented "Continuum Crowds" approach, where crowds themselves are soft obstacles in the map too. And as crowds move, the optimum path changes, hence you need to update the flow quite often. Example scenario: A 100 agents exit a building via a single door, once the last one leaves, it becomes much easier for another agent to enter via that door again. Pushing upstream is hard, so you need to know exactly when the stream stops. \$\endgroup\$ – Bram Dec 21 '18 at 16:32
0
\$\begingroup\$

This is way too much information to explain in a single answer, but some good keywords for multi-unit pathfinding are "swarm pathfinding", "boids", "flocking behaviors", and "collision avoidance pathfinding".

Also for highly dynamic maps, if approximate paths are ok, check out HPA* (Hierarchical Pathfinding A*) - you don't need "logical divisions" to be able to separate your grid into smaller grids.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.