Motivation
in WOF, We usually seek perfection. In the case of AI assisted Footballer control switching, we wanted to do better than other comparable games. This means, when a human player is controlling a footballer, and the ball is shot or passed, control has to switch to the best candidate. This does not mean, the first footballer in the ball's direction! Even the smallest thought effort gives us a long list of cases where this does not work: lobs, balls unreachable because of ball speed and footballer reaction time, target footballer being busy doing other important actions... (even ball deflections from the goal bar are handled 'correctly' by WOF!)
the AI also had to correctly handle multiple human players in the same team and not allow ping- pong switching between them.
Results
a shy video showing the results (partially) can be seen here:
Non Linearity and Searching
Since we are in 3 dimensions, the speed of the ball being non linear, and the position even much less so, the fact that the footballers speeds can be approximated as linear is not of great help.
Therefore, the correct algorithm had to rely on a search. in it's basic unoptimized form, it should calculate the ball's complete trajectory (colliding with static obstacles only), and for each potential footballer, find the portions of the trajectory (and yes they are portions because of ball height changing) when the ball can be intercepted. Then choose among those based on mix of criteria: first to intercept, wait time after arriving to position, effort needed to arrive to position...
As with every search algorithm, it makes lots of sense trying to optimize it, we do not want this single 'basic' task to wreak havoc on the whole game's performance.
Full Ball Trajectory Calculation
The full ball trajectory is very useful, and we use it for many different purposes, that is why, we already had it implemented. It is calculated using exactly the same physics engine used in game, it is therefore very exact. The collisions are only performed with static objects, it does not make sense to include dynamic ones since they are ... dynamic.
Because of our performant physics, collision detection and spatial subdivision, we can afford to calculate the full ball trajectory every time the ball is shot.
The calculation is optimized in 2 ways. The 1st optimization is splitting the calculation among a configurable amount of frames, since we never need the whole trajectory instantaneously, in practice we obtain it fast enough for all of our purposes. The second optimization is the intelligent choice of sampling technique. Instead of some naive sampling, we use an error metric that allows us to have the least number of samples possible, while keeping the quality of the samples so, that one can linearly interpolate the position of the ball based on a sample's start velocity, until the next sample, keeping the error less than the ball's radius.
Search Optimizations
As with all searches, we can do much better than brute force. And since this search will be continuously executed since the footballers move, it better be performant!
One optimization was made by adding functionality to the trajectory calculation phase, allowing it, on the fly, to split the trajectory into multiple sections, depending on the height of the ball (and therefore it's reachability by footballers), allowing 'too high' sections to be completely skipped during the search.
As for the search itself, we used temporal caching, and a number of WOF specific optimizations.
For temporal caching, we hold on to the last found intercept point, and only check for it's validity using it's type (footballer will wait for ball at intercept, ball will wait for footballer at intercept, no intercept, ...) and the amount of time elapsed since the intercept's first analysis time. This means in one case per example, if we found a valid intercept point where the footballer has to wait 0.5 seconds for the ball after arriving to his position, we can, until 0.5 secs pass, 'simply' recheck for the intercept's validity (while keeping an eye on where the footballer is going) and this is much cheaper than starting a new search.
Of course, samples are invalidated as times passes by, thus making the number of samples to search smaller the further the time advances, but this is obvious.
The implementation itself produces (crudely estimated) 2500 lines of source code (excluding headers), split among multiple files in a nicely organized design, that allows reusing it in a clean way for a number of other purposes (like the scripted AI using it to make it's decisions).
Conclusion
when considering searches, make sure they are unavoidable, if you are sure they are, understand why, implement them, optimize, profile and enjoy the hopefully nice results.
No comments:
Post a Comment