What would not be a bad approach, and the best available out of the box. Even better solution would be to implement a KDTree that would hold all Pawns, and recreating it with some frequency (depending of how dynamic your pawns are), and query the tree. Adding this is actually on my list of things to do, but I can’t give you any date on this one (hope to get it in withing 3 months).
I’d go forward with physics-based solution for now.
Cheers,
–mieszko
Hi. I need to get some advices on AI programming. I’ve looked for some example AI projects and saw they are using pawn iterators to learn about closest enemy. It might not be a problem for a game which has tens of pawns but in a game with hundreds of pawns it might be a problem about performance. Hundreds of pawns do hundreds of iterations…
So I think about sphere triggers to detect the other pawns in radius. AI controller class can contain a list of pawns which are entered the trigger. Then decision can be made on these pawns only. By using this way the physics engine can eleminate the iterating loop for pawns.
Is this a good aproach or is there any other good aproaches to boost performance?
Edit: Ninja’d, I see. Mieszkoz, any thoughts on using the Navmesh polys in the way I suggest below?
This approach could work, but I don’t know about the performance of so many triggers operating all the time - the efficiency of fewer iterations could be lost amongst the overhead of all the collision logic, though given physics has its own thread, perhaps not.
Remember that unless you need the exact distance between the pawns, you can FVector::SizeSquared to avoid the expensive square root as an optimization to the ‘iterate all pawns’ approach.
You could certainly investigate alternatives, though. For example, as an off-the-cuff idea - divide your map into buckets or cells or grid squares. Iterate through your pawn list once, at some interval. Place the pawn into a bucket based on their position, and store a pawn count for each bucket. When the pawn wants to know what the nearest pawn is, check its bucket for pawns. If there are no pawns present, check adjacent buckets for pawns, and keep expanding the search until you have a list of pawns with the shortest distance in ‘buckets’ to the current pawn, and you can iterate over the reduced set of pawns instead of the full list.
You could potentially even use navigation mesh polys as the buckets, though I’m not familiar enough with the navigation mesh implementation to elaborate further. If navmesh already tracks which pawns are in which polys this would be even easier.
Will your AI have other factors to consider other than distance when choosing a target? If so, I’d recommend perhaps applying any other constraints you have to target selection, onto the list, before iterating it, to reduce the number of items in that list and therefore iteration time. Alternatively, you could use a heuristic approach that decides if another Pawn in the list is ‘sufficiently good’ as a target so that you can exit out of the iteration early when a target is found that’s ‘close enough’.
(If you’re really concerned about performance, I’d suggest profiling your current approach as a base line, then comparing it to other solutions - I’ve done no testing on anything I’ve suggested here, so can’t guarantee it as a meaningful optimization for you).
I don’t realy know about background of triggers. How UE4 does physx computation using Physx, does it using buckets foreach level for physical computation…etc but I know Physx is fast so Sphere trigger concept looks like fine to me.