1. Presentation
2. Objectives
3. Euler Integrator
4. Development and Features
5. Test and Validation
6. Conclusions

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.

Download our project here

• Programming
• jose-tello

• Project Lead & Coordinator
• adriaserrano97

• Programming
• davidcarrasquet

• Report Lead
• juanha2

• Physics Programmer Lead
• oscarpm5

• Programming
• AaronGCProg

• Programming Lead
• ferba93

• Physics Programmer
• xatrilu

• Physics Programmer
• AlexMelenchon

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.

Our main objective is to develop and implement a numerical integrator based on Euler Integration.

In order to achieve this goal, we will program an integrator that will:

• Propagate our objects 1D each frame, receiving adjustable inputs
• Provide as outputs: acceleration & velocity & position at current frame
• Work with particle-physics
• Be fast enough to work in-game

Besides those main objectives, we have set our own group of extra objectives in order to improve our project; both making it better and more interesting. These extra goals include:

• Implement SDL library and graphically display our results
• Jump from 1D physics to 2D
• Work with solid rigids (at least, one shape)
• Implement aerodynamic drag force
• Make gravity direction change on key-press
• Work with time units, not frames (so computing power does not change execution speed)
• Add a mouse joint to move the objects with a mouse

The Euler method is the most basic and simple process used to find approximate numerical solutions, to a first order first degree differential equation, as long as its initial condition is known.

An ordinary differential equation is the equation that relates an unknown function of a single independent variable with its derivatives. If the major derivative that appears in the equation is of degree one, then we're refering to a first degree ordinary differential equation.

The main idea of Euler's method is to find a numerical solution to the differential equation in the interval between Xi and Xf.

At first, we divide this interval in xn points.

x0, x1, x2, x3…, xn

If we know the initial condition then we know the derivative at the beginning:

y’ (xo) = f (xo, yo).

This derivative represents the slope of the tangent line to the curve of the function y(x) precisely at the point:

Ao = (xo, yo)

Then an approximate prediction of the value of the function y(x) is made in the following point: y (x1) ≈ y1

y1 = yo +(x1– xo) f (xo, yo) = yo + h f (xo, yo)

We obtain this way the next approximate point of the solution that would correspond to:

A1 = (x1, y1)

Then, we repeat this process to obtain the successives points:

A2, A3…, xn

• In the figure shown up above, the blue curve represents the exact solution of the differential equation, and the red one represents all the successive points obtained by Euler's procedure.

In this page we will describe how our Euler Integrator works. We will divide it in 2 parts. The first part will be a description of the different code elements that we use, while the second part explains how these elements interact to make our integrator work.

In these two items we create all the classes of the different modules we will use later on using a p2List<Module*>. Each module shares a series of functions such as Init(), Update(), CleanUp(), etc...

In the main loop we create an enum main_states which we will use to call all the App functions in order with a switch. In case of error the state will automatically turn to MAIN_EXIT.

This item contains the general information and functions such as the minimum value, all the window settings, etc...

This module creates the window using SDL functions

The main function of this module is to print every frame and manage the camera position. It has several print functions too, such as DrawLine() or DrawCircle().

This module gets the user's input (via keyboard and mouse) in order to execute different functionalities.

This module creates the main world, its objects and calculates the position, speed and acceleration of the respective objects via Euler Integration.

In this struct we define the properties of the object (mass, name, position, etc...) initialized with constructors, and we establish the CheckCollisions method.

To make Object management as easy and efficient as possible, we added multiple ways to create them. Since these are the main entities in our Integrator, we want them to be as easy to work with as possible.

A method of the objects that detects if two objects interact.

In this struct we set our gravity, the name of the world and the list (array) of all the objects that are contained in it.

Here we have it, the integrator itself. This function is called each frame, traversing the array of objects in the world and moving them all. It takes the object's properties and returns the position, velocity and acceleration of the object in the next iteration.

In this module we check the collisions between all the objects in Update(). We have implemented the ForwardPropagation mehtod which consists of checking in every frame if there is a collision and then set the new speed and position of the two objects colliding (we add "artificial" forces to the objects involved in order to achieve so).

Inside Module Scene, we included a special feature that allows you to drag an object by simply clicking on it. When you are dragging the object, it becomes a rigid object and collides with the enviroment! In order to drag, just Left Click to one object and move the mouse without letting go of the button; when you stop clicking, the object stops being dragged.

We hope a quick glance on the diagram above should be enough to understand how our code operates. Just to be safe, we'll provide a written step-by-step explanation.

Our integrator works as many games do: it consists of an infinite main() loop that only breaks on user command (ESC keyboard press) or if the code returns a false state in any of the steps. This loop checks the state of several modules, each of those with their own methods. Those modules do different things in our code, all working together to create our integrator. So... what happens once we execute our integrator?

App module is created in main, immediately followed by the call to construction of all modules, keeping a pointer to each of them. This step is mandatory, since the only way modules have of passing information to each other is through App.

Once that is down, Init() of all modules is called. in Init(), we assign base values to all needed variables, as well as calling some basic SDL functions. Following that, we proceed to Start() the modules. From a conceptual standpoint, Start() corresponds to the first frame in which our code is actually simulating the game. Therefore, we define all starting conditions of our world in Start(). Refer to the diagram to look up what module does exactly what.

Should any Init() or Start() fail to execute, we immediately print the error in a LOG and close the App. Just a routinely defense mechanism against memory overloading or even worst: memory corruption.

Once everything is set up, we enter the main loop. From here, we call the Update() method of each module, checking if anything needs to change depending on external inputs (user interaction via keyboard or mouse) or internal inputs (integration of objects each frame, or collision resolving). From here on out, the loop should repeat itself indefinitely until the player quits (or a fatal error occurs, which it should not). This leads to the finish state.

We prepare our code to close itself. Clean Up method of each module is called, deleting all instances of every object, directing every pointer to null... We also quit all subsystems (mainly, SDL).

Once we're left with nothing but main() and App(), we destroy them. We're out!

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.

The first thing shown in the first video is that every time the right mouse button is clicked, a red square appears at the position of the cursor. This is due to the SDL library, which let us display graphical results on the screen.

As soon as we make a square appear, we can see that it automatically moves downwards due to the default gravity that we have established.

When two red squares collide, both of them react because of the collision system. This reaction changes the position of each square and sets a new direction, velocity and acceleration for each of them.

If two squares are created at the same spot at the same time, we can see clearly how they repel due to the forward propagation system in our code.

Finally, there is some information displayed at the top of the window that indicates the time between frames in milliseconds, the project's FPS (30 in this case), the average FPS, and the actual FPS running.

In the second video, we can see how the squares collide, after a floor has been added. Now, this squares fall slower because we have set their sizes to 1 meter.

We can also see that the direction of the gravity changes with the W, A and D keys, and that its magnitude can be increased by pressing S. The value of the gravity can be reset with the spacebar key.

In the third video, we can see how the mouse joint works, after hitting left click when the mouse is within an object boundaries, the object becomes draggable and collides with the enviroment. As you can see, the vector that unifies the object with the mouse is blit in the window, giving the user a visual reference to move the object.

To stop dragging the object, just release the button.

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

This proved to be easily achieved. Our team managed to code a first draft in under two hours. We set the inputs in-code as hardcoded values, and the output was shown as console messages (Log function). As a first draft, it worked wonders. We used this "integrator" as a base model to improve in further iterations.

This was added at the same time as point 1. We needed to calculate those values, so we just needed to LOG them. Again, no problems were found here.

First iterations of our integrator worked with particles. Of course, this didn't generate any problems. It should be said that those first iterations worked only in 1D.

The integrator started as a handful of code lines scrapped together, so of course it would be fast enough back then. With each iteration, code complexity (and volume) raised quickly. However, it never proved to be enough to noticeably diminish the CPU's performance. Therefore, no code optimization sessions were needed. The fact that we were displaying FPS and time windows at every point proved to be extremely usefull here, as it showed us beforehand wether or not something was too slow to be implemented.

Here we faced some inconviniences, although nothing too drastic. Only problem was that the conversion from floating point numbers to pixels can be fatal if left unsupervised. Some easy and quick correction formulas and that was all the trouble this objective caused us.

We knew this one would be troublesome. It was written in the walls: the complexity gap between 1D and 2D is nothing to cough at (at some point in brainstorming we though of doing something in 3D. We know now that trying that would prove way too time-consuming for the scope of this project). At the start, we thought the main problem would be the integrator function itself. However, much to our dismay, collision detection and correction proved to be a nightmare. Some of the problems we faced here were:

• Objects unable to properly detect each other (we are working with squares, quite a more challenging shape than circles. While knowing when and where two spheres are colliding is trivial, doing the same with squares is not).
• Objects acquiring unreal amounts of speed. We decided that static objects should have mass 0. Surprise: having objects with no mass provides a hilarous experience once you are trying to conserve momentum in a collision. Once again, we had to implement extra checks, corrections and functions. (Most important one: objects with mass 0 in collision are assigned a "ghost mass" of 1.000.000. Once the collision is resolved, mass goes back to 0).
• Objects sinking into one another. Probably the most unexpected problem that we faced. We spent way too much time checking our code just to realize in the end it had nothing to do with us. Basically, it's all because "Floating point error IEEE754]." What does that mean? It means that if you have a floating point value with theorically infinite precision (in our case; speed, impulse, acceleration, etc.) your computer is going to store a "simplified", shorter version of it. From a theory standpoint, we knew it would happen from the start, that's why we store values in value types such as long doubles and floats. While we thought that would be enough, we were proven wrong. Each frame, this floating point error kept rising, ending up in messed up calculations of impulse and distorted positions (which caused the aforementioned sinking). Once again, checks and functions needed to be implemented (mainly, if a change is produced in an object with a delta inferior to a pre-defined threshhold value, our integrator takes it as zero).

While the objective itself was not that hard to accomplish, we didn't account for the added difficulty in chosing the type of shape. All examples on-line we found were using circles, so we decided to try squares, and after that, rectangles. As explained before, this proved to be an extra layer of complication. Some math was required to figure out detections and positions of rectangles as a result.

This proved to be way easier than expected. From both a physics and a coding standpoint, it amounted to a couple extra simple calculations. Due to time constrains, we were not able to implement lift. However, the realism of the simulation gets heavily improved by this extra step. In the end, it was 100% worth the little extra time.

While not beign automatic, it didn't prove to be a bottleneck for the project. In the end, it all amounts to a re-definition of the gravity vector we use to integrate objects each frame. Should we have more time or expertise, maybe we could have defined the gravity vector as a console-input, thus enabling an infinite scope of possible gravity vectors (not just the 4 cardinal directions we have defined). We think this idea is not being explored with enough depth nowadays, so some experiments would prove benefitial to developing a creative idea.

In the end, we knew this integrator didn't work in a vacuum: it was supposed to work in a game. Most (properly made) games do not work in frame units, but time units. This responds to the fact that, were it not the case, the strenght of your processor would raise the speed at which your game ran. That's not something you want in your game for obvious reasons, and thus, not something we wanted in our integrator. Transforming our code to work with time units proved slow and sluggish, altough not of high difficulty. In the end, it was worth it: both because of aforementioned reasons and because from a physics standpoint, its way easier to understand what the code does, as it uses time as...time, not frames.