vaio on 22 July 2008
It's All In The Wrist
I consider the aiming algorithm used by the BrainWorks bots to be the biggest success of the project. More than one experienced Quake player has told me how amazed they were to spectate the bots and watch their aiming, since it appears so realistic. I went through close to a dozen different iterations of the basic aiming engine until I got results I was pleased with, and this is the research that took most of the six year development period. I estimate roughly 60% of the work was spent on aiming! (If you're curious, item pickup was about 30% of the time and everything else took 10% total.) To me, the objective was to create a bot whose aiming realistically matched a human player's aiming. There's a secret to how I did this:
It's all in the wrist.
Most games don't let you spectate their AI units because it would be immediately obvious how the AI is cheating. But if you could, you almost always see on of two things. The AI might look almost directly at the player and but moves their camera away from the ideal position by a random amount, so that they miss sometimes at random. Or the AI could turn at a fixed, slowish speed, but always (eventually) aims more or less perfectly, so that they only miss right after the target suddenly changes.
The problem is that these algorithms don't model how a human wrist would interact with a mouse. So the result is that the AI won't miss at sometimes the human would miss, and will hit when the human won't hit. For example, rapidly moving side to side will confuse the AI whose aiming moves at a fixed, slowish rate, making them constantly miss. With these traditional algorithms, no matter what parameters the bot has for speed and error frequency, its aiming will never look like a human. That means its accuracy with weapons will never match human accuracies either.
The solution to modeling the aiming problem is to stop thinking about the monitor (whether the crosshairs are lined up) and start thinking about the mouse (how human motion changes the crosshairs). Human motion of the mouse doesn't move at a fixed speed, and it doesn't "randomly" move to the wrong area. The motion involves acceleration and deceleration. The faster a human moves a muscle, the larger the potential error. Humans can increase the precision of their movements by moving slower, so typical human motion involves a rapid acceleration to a desired speed, some time moving at that speed, and then deceleration to a rest state.
Mathematically this means that if a human attempts to accelerate at rate X m/s^2, the actual acceleration is somewhere in the interval [X*(1-e), X*(1+e)] where e is the maximum allowed error (eg. 10%). So a small error in acceleration is magnified over time each time the acceleration is applied to the velocity, and the velocity error in turn magnifies position error each time the velocity changes the view position. This, combined with an extremely simple, elegant error correction algorithm, provides an excellent simulation of the view motion created by a human hand on a mouse.
That's basically the algorithm BrainWorks implements. The bot splits its view state into two distinct axies: Up and down on the simulated mousepad make the bot pitch its view up or down, and moving left or right on the mousepad make the bot rotate left and right. This reduces the view problem into two identical one-dimensional problems. For each axis, the bot decides how much to accelerate and decelerate the movement of its simulated mouse to get from its current view position to its selected view position as quickly as possible. The small acceleration error factor is all that's needed to generate the smooth overshooting mistakes that humans make when they try to turn quickly with a mouse.
The calculus to compute exactly how much time to spend accelerating and decelerating is a bit complicated: there's a 150 line comment explaining the derivation in ViewAxisModify() function in ai_view.c. But the resulting equations are fast and easy to compute. It's 30 lines of actual code, only one square root, four floating point divides, and a whole bunch of adds and multiplies.
As I said, it's all in the wrist.
It's all in the wrist.
Most games don't let you spectate their AI units because it would be immediately obvious how the AI is cheating. But if you could, you almost always see on of two things. The AI might look almost directly at the player and but moves their camera away from the ideal position by a random amount, so that they miss sometimes at random. Or the AI could turn at a fixed, slowish speed, but always (eventually) aims more or less perfectly, so that they only miss right after the target suddenly changes.
The problem is that these algorithms don't model how a human wrist would interact with a mouse. So the result is that the AI won't miss at sometimes the human would miss, and will hit when the human won't hit. For example, rapidly moving side to side will confuse the AI whose aiming moves at a fixed, slowish rate, making them constantly miss. With these traditional algorithms, no matter what parameters the bot has for speed and error frequency, its aiming will never look like a human. That means its accuracy with weapons will never match human accuracies either.
The solution to modeling the aiming problem is to stop thinking about the monitor (whether the crosshairs are lined up) and start thinking about the mouse (how human motion changes the crosshairs). Human motion of the mouse doesn't move at a fixed speed, and it doesn't "randomly" move to the wrong area. The motion involves acceleration and deceleration. The faster a human moves a muscle, the larger the potential error. Humans can increase the precision of their movements by moving slower, so typical human motion involves a rapid acceleration to a desired speed, some time moving at that speed, and then deceleration to a rest state.
Mathematically this means that if a human attempts to accelerate at rate X m/s^2, the actual acceleration is somewhere in the interval [X*(1-e), X*(1+e)] where e is the maximum allowed error (eg. 10%). So a small error in acceleration is magnified over time each time the acceleration is applied to the velocity, and the velocity error in turn magnifies position error each time the velocity changes the view position. This, combined with an extremely simple, elegant error correction algorithm, provides an excellent simulation of the view motion created by a human hand on a mouse.
That's basically the algorithm BrainWorks implements. The bot splits its view state into two distinct axies: Up and down on the simulated mousepad make the bot pitch its view up or down, and moving left or right on the mousepad make the bot rotate left and right. This reduces the view problem into two identical one-dimensional problems. For each axis, the bot decides how much to accelerate and decelerate the movement of its simulated mouse to get from its current view position to its selected view position as quickly as possible. The small acceleration error factor is all that's needed to generate the smooth overshooting mistakes that humans make when they try to turn quickly with a mouse.
The calculus to compute exactly how much time to spend accelerating and decelerating is a bit complicated: there's a 150 line comment explaining the derivation in ViewAxisModify() function in ai_view.c. But the resulting equations are fast and easy to compute. It's 30 lines of actual code, only one square root, four floating point divides, and a whole bunch of adds and multiplies.
As I said, it's all in the wrist.
Vaio - "Bury me at Milanello" R.I.P AC Milan
In the 60's, people took acid to make the world weird.
Now the world is weird and people take Prozac to make it normal.
If laughing is the best medicine and marijuana makes you laugh
Is marijuana the best medicine?
"Be who you are and say what you feel, because those who mind don't matter and those who matter don't mind."
“If any creator has not played Mario, then they’re probably not a good creator. That’s something I can say with 100 percent confidence. Mario is, for game creators, the development bible.
