December 23, 2015

pSeven learns to play "Angry Circles"

Almost every software developer comes to a moment when he has a desire to create a video game. This wish usually fades away fairly quickly, but may reappear at any moment. So when was given a task to develop an illustrative use case for the pSeven optimization capabilities, I knew precisely what to do.

Idea is simple - physical models are easy to visualize and to understand. Everyone has some intuitive understanding of physical laws - apples fall, glass breaks and the ice is quite slippery. However, demonstrating a real-world problem is not ideal. Engineering problems tend to be complex and full of unnecessary details.

With all this in mind, I teamed up with our intern Kirill (thanks for your help!) and implemented a very simple game-like solver for a 2D physics scene. Let’s assume that we have a heavy body that is thrown with some initial momentum (both linear and angular) at some angle and let’s call it a Circle. Scene contains a number of breakable targets with different durability, each of them giving a set amount of points for its destruction. The evil Squares worth the highest number of points. The goal is simple - with a single launch of the Circle, we want to get the maximum score. Solver takes into account basic forces (gravity and friction) and models some degree of elasticity for each body. It can be visualized like this:

Setting an optimization problem around this solver is obvious. We have three variables - linear velocity, angular velocity and angle. Resulting score is the objective function. What is interesting, that physical model in this simple example already creates non-trivial mathematical task. “Score” objective function behaves erratically and has numerous local minima and vast degraded regions (with the zero value, when our cannonball hits no targets and just fly away). Let’s see if pSeven Core GTOpt optimization capabilities are up to this challenge!

This is an optimization workflow:

Due to the multimodality of the objective function we need to use global optimization here, so let’s turn it on in the Optimizer options:

We treat our 2D solver seriously, so we run it like a real one. We prepare input files with a scene description, run the simulation (without any graphics to make it faster) and parse the result from the output file. When optimization is finished, the optimal point is passed through the same solver again, this time with the visualization turned on. Final result is saved as an interactive plot which can be shown right inside pSeven using our recently added Page Viewer:

Despite all the complexities, GTOpt managed to find the solution very close to the global optimum - no targets survived. Here is the final solution:

 By Alexey Nazarenko, Senior Software Engineer, DATADVANCE