Assignment 2: The Aimbot - AaronGCProg/Euler.Integrator-Aimbot GitHub Wiki

Welcome to the Aimbot Report!

Index

  1. Presentation
  2. Objectives
  3. Monte Carlo method
  4. Development and features
  5. Test and validation
  6. Conclusions

Presentation

We are a group of students in 2nd year of Videogame Development degree, creating a basic Euler integrator for CITM's 2nd year Physics II subject, to improve our knowledge on the subject. For making this project we have used the integration scheme from the first assignment The Euler Integrator

Download our project here

Team members

David Carrasquet Iniesta:

Aaron Guerrero Cruz:

Oscar Pérez Martín:

Jose Luis Redondo Tello:

Juan Hernández Almagro:

Adrià Serrano López:

Àlex Melenchón Maza:

Ferran-Roger Basar i Bosch:

Mostly everything was done in cooperation. The statements above reflect who was the one to take responsability for the section, as well as supervision and final implementation.

Objectives

The main objective of this assignment is to develop and implement an automatic targeting algorithm (aimbot). This aimbot must:

  • take as inputs: position of the shooter, position of the target
  • provide as output: initial velocity of the bullet that results in a hit (or damage) to the target
  • work with particle-physics (no rigid body required)
  • be game-oriented: speed first, accuracy second

As extra objectives and features we have set the following ones:

  • Make objects move with a mouse joint.
  • Make a humanoid object that receives a variable amount of damage depending on where the bullet hits.
  • Debug mode where all montecarlo paths are blit to the screen.
  • Optimize the Monte Carlo mehotd as far as possible, priorizing its speed rather than its accuracy.

It is important to note that before proceeding to make all these objectives we plan on cleaning and polishing the Euler Integrator project first in order to work more efficiently

Monte Carlo method

The Monte Carlo method is a subset of computational algorithms that use the process of repeated random sampling to make numerical estimations of unknown parameters. During a Monte Carlo simulation, values are sampled at random from the input probability distributions. Each set of samples is called an iteration, and the resulting outcome from that sample is recorded. Monte Carlo methods vary, but tend to follow a particular pattern that consists of the following 4 steps.

  1. Define a domain of possible inputs
  2. Generate inputs randomly from a probability distribution over the domain
  3. Perform a deterministic computation on the inputs
  4. Aggregate the results

This method is widely used and useful in many sector such as physics, engineering, computanional biology, etc..

Development and Features

We have worked from our previous mission The Euler Integrator, so we recommend to have a look at how we structured the development to fully understand all the changes and new features explained below.

Collision

The collision system has been changed from the previous one. We have implemented collisions with the screen limits to reduce the number of iterations of the Monte Carlo method in order to hit an objective. We have also restructured the OnCollision and resolveCollision system, now we avoid checking collisions already checked and we check first if there could be a pontetial collision to later on proceed to the more complex check collision function (with sqrt).

Aimbot

We have created a new module Aimbot, which will be the central part of this project. Our aimbot has four principal states that we will manage with a switch function:

  1. Idle: do nothing.
  2. Calculate MonteCarlo: if there's a target, we will calculate the trajectory using the Monte Carlo method.
  3. Finished calculating MonteCarlo: Once we know the trajectory we are ready to shoot.
  4. Shoot: We shoot the bullet and reset the state to idle.

We get the input of the user right before all the logic and calculations. If we press the left mouse button, we trigger the "Calculate MonteCarlo state" which will calculate the trajectory and will take us to the "Calculated MonteCarlo state". Once in here, the user can press SPACE and trigger the last state "shoot", that will shoot a bullet to its objective through the trajectory calculated before.

Calculate trajectory (Monte Carlo)

Let's have a look at this function since here it is where the basis of the Monte Carlo method resides.

Each time we want to calculate a new trajectory, we add a new body called propagation object. We generate random numbers for the speed and angle of the trajectory. We have decided to set the angle's values between 0 and 180 degrees; and we have also set a minimun velocity due to the aimbot's efficiency (with minimum velocities, the Monte Carlo method hardly ever found a solution) and a maximum velocity (to avoid ghosting collisions).

In each iteration, the propagation object will get these values and we will be checking if there is any collision with the target. In case of a collision, we will set our trajectory the angle and speed values of the propagation object that has collided. We now have the result trajectory and we are ready to shoot a body through it. To make the body describe the trajectory movement, we have added to our Object struct a function called AddSpeed(), which sets the speed of the result trajectory.

It is important to note that our function always does the maximun iterations defined and everytime there's a possible collision we check the number of the active iterations solved from that moment. If it's less from the previous ones, we update the "result" trajectory. This way we are optimizing the Monte Carlo method to be ready to shoot as fast as possible.

Inputs and useful commands

  • Left mouse button: Generates target at mouse position.
  • Space key: Shoots the bullet once a Monte Carlo path is generated.
  • 1: Creates a static body at mouse position.
  • 2: Creates a dynamic body at mouse position (affected by gravity).
  • F8: Debug mode where all iterations of Monte Carlo are displayed one by one.

Workflow (Aimbot Update UML)

Explanation

The UML up above shows us briefly all the operations that our code follows in one frame. The first thing our aimbot does in the update is getting the user's input. In case of no input (or different from left mouse button or space bar), the aimbot will do nothing and return to getting the input in the next frame.

In case the left mouse button is pressed, the aimbot will reset the possible remaining or previous propagations objects. Then, it will proceed to the calculation of the Monte Carlo method. If there is no objective, it will stop there and we will wait for the next frame. In case of an available target, the aimbot will calculate the trajectory generating random values for the speed and angle. If the object doesn't collide, we will do more iterations until it collides. Finally, when the object collides, we will have the desired trajectory calculated.

On the other hand, if the space bar is pressed, the aimbot will seek for trajectories calculated. If there is no trajectory available, it will return to the beginning in the next frame. However, if there is an available trajectory it will proceed to shoot the object!

Test and Validation

In this section we are going to test, validate and prove how our code works. In order to do this, we have recorded a little video that shows the main features of our project.

Video

alt text

Explanation

At the beggining of the video we can see the origin point, drawn as a circle, where the bullets will be shot from. By clicking the left mouse button we can see how bodies spawn at the cursor position. Automatically, a path is generated in color red (the Monte Carlo result trajectory). When the space key is pressed, the bullet from the origin is shot following the path until it reaches the objective.

We can see how the ball impacts optimally with the walls and the objective. By clicking "1", more bodies are generated on the screen. Even generating many spheres as shown in the video and trying to resolve Monte Carlo, our programm achieves the desired path avoiding possible collisions with the spheres that aren't our target.

In the second part of the video we have pressed "F8", this is a debug mode where we can see all iterations one by one of the Monte Carlo method.

We have also implemented dynamic bodies by pressing "2". As we can see in the video, we can drag these bodies through our mouse joint. The bullet can also be moved with this joint.

Finally, it is worth mentioning the header of the window, where the current, the average, the target and the last FPS are displayed. This has been really helpful to be aware that our code is efficient and to make sure that calling the Monte Carlo method doesn't drop the FPS of the programm.

Conclusions

In order to evaluate our project, thus extracting our conclusions, we'll adress each objective individually. Our objectives were:

Main objectives

take as inputs: position of the shooter, position of the target

This hasn't been very difficult to achieve as the position of the shooter always remains at the same location and the position of the target is obtained by the mouse position once the left mouse button is clicked. Furthermore, these features were already well implemented in the last report (The Euler Integrator), making it very easy to implement in here again.

provide as output: initial velocity of the bullet that results in a hit (or damage) to the target.

In order to achieve this objective we have had to implement the Monte Carlo method. To get the initial velocity we just had to generate random values to the speed and angle and check (after integrating with those values) if there was any collision. Once there was a collision, we just had to get the values and calculate the initial velocity.

However, our programm just works with collisions, there is no damage mechanism to the bodies generated. Moreover, the management of the angle and speed values turned out to be a little tricky since some functions used radians and others degrees. We decided to pass to radians all values (in exception of the function declaration).

be game-oriented: speed first, accuracy second

Thanks to the FPS display in the window title, we were well aware in every moment of the development if any change caused a drop or problem to the velocity of the programm. Sometime through the development, we accidentally set the number of iterations to a large number. This made the velocity go crazy and made the programm not work efficiently as well. Even so, we could manage to find the problem and solve it.

Bonus objectives

Make objects move with a mouse joint.

Unlike the last report that we worked with squares, now we are working with circles. The only problem that this has brought us is that we have had to recalculate the formulas in order to drag the dynamic circles correctly.

Make a humanoid object that receives a variable amount of damage depending on where the bullet hits.

Due to some complications of the main objectives and wanting to focuse on polishing the Monte Carlo algorithm, we haven't managed the time correctly to make this objective.

Debug mode where all montecarlo paths are blit to the screen.

We have implemented the F8 key which shows us all iterations of Monte Carlo. Although not all paths are blit at the same time, we have managed to graphically display each iteration correctly.

We had a problem when drawing the resulting red trajectory because we were converting ints to floats making that some information was missed. A quick revision of the code was enough to realize this problem and solve it.

Optimize the Monte Carlo mehotd as far as possible, priorizing its speed rather than its accuracy.

In the first iterations of the project we could see that executing Monte Carlo dropped the framerate. We could manage to solve this by modifying the function and updating the path everytime a collision was detected. This way we optimized the Monte Carlo method making it so much faster to execute.

Re-structure of Collisions

We began this project carrying some problems of our last collision system. Basically some collisions between objects caused problems. In this project we have made major changes to our collision system to try to improve it.

To reduce the collisions between objects we've made that the walls are no longer square objects. We have implemented two different systems of collisions: bewteen object/object and between object/wall. Now the walls behave different from objects.

Another problem that caused us some problems was the fact that we were working with square shapes (lost info from converting floats). We have decided to now work with circle shapes as it is easier to work with. However, we have had to implement a new way to detect collision with spheres, which is way more inefficient (uses sqrt) than with squares. To prevent the code from being too slow, we have re-used the one we had (squares) to make a first check if there can be a possible collision and then proceed to use the new way to detect circles.

In the last report objects sank into each other, we have made a work-around of this problem by adjusting the position of the objects in function of a stablished delta value.