Profiling: move to food

[richelbilderbeek]

Is your feature request related to a problem? Please describe.

In recent Travis CI build logs we can observe that 35% of all run-time is spent in agent:move_to_food.

Now we can rationally speed up the program, let's reduce the big-O complexity of it.

What we can see, is that when move_to_food is called for an agent, it measures the distance to all other agents. If there are x as many agents, there will be x^2 as much comparison, therefore we write O(n) = n^2. Let's make this O(n) = n!

To do so, we need to:

1. Make an agent scan one other each frame
2. Somehow remember where to go

Easy:

1. just pick a random agent
2. give the agent a motivation to go someplace

Describe the solution you'd like

• [x] Write down the current run-time speed for the profiling setup here:

Measured	Runtime speed
Before	2:40

• [x] Within an agent:move_to_food only pick one random other agent at a time.

At 50 fps, this should work out good enough.

• [x] To an agent, add:

/// Motivation for a certain horizontal velocity
/// Added due to profiling results, see Issue  #543 
double m_dx_motivation;

/// Motivation for a certain horizontal velocity
/// Added due to profiling results, see Issue  #543
double m_dy_motivation;

View this motivation as a mathematical vector (which is not a std::vector). Vectors add up. If there is incentive to into a direction, add this to the vector.

The closer the target, the longer the vector, as the motivation to go there is bigger. Use this equation:

const double vector_length = std::exp(-distance);

I've made a picture in which I hope to show the idea of such a vector:

There is a lot of influence of the first measurement, but whatever happens, the agent will go to the closer lower-left green agent.

• [ ] Keep track of this motivation vector. Consider letting someone else display this vector graphically

• [x] Let the agent move in the direction of the vector. Constrain the agent to a maximum speed

• [x] Measure the speed increase

Measured	Runtime speed
Before	2:40
After	2:22

• If speed is reduced, undo all changes!
• If speed is increased, keep the changes.

Describe alternatives you've considered

None.

Additional context

None,

[richelbilderbeek]

@robkruger: I assign you this Issue. Feel free to delegate it to others, as long as you take the responsibility to ensure the code is actually sped up!

[robkruger]

@richelbilderbeek This is my code so far, but I think I'm doing it wrong. But with this, it walks to food, but not to the closest one. Can you help?

unsigned int rand = static_cast<unsigned int>(std::rand() % (count_n_agents(g)));
  agent a = g.get_agents()[rand];
  if(std::find(m_prey.begin(), m_prey.end(), a.get_type()) == m_prey.end()){
    return;
  }
  else{
    double distance = pythagoras(fabs(m_x - a.get_x()), fabs(m_y - a.get_y()));
    const double vector_length = std::exp(-distance/400);
    double angle = atan2(m_y - a.get_y(), m_x - a.get_x());
    m_dx_motivation = sin(angle) * vector_length;
    m_dy_motivation = -cos(angle) * vector_length;
    m_dx_motivation = std::max(-0.5, std::min(m_dx_motivation, 0.5));
    m_dy_motivation = std::max(-0.5, std::min(m_dy_motivation, 0.5));
    std::cout << m_dx_motivation << std::endl;
    m_x += m_dx_motivation;
    m_y += m_dy_motivation;
  }

[richelbilderbeek]

Looks cool at first glance. Could you produce a test that fails?

You do not keep the old motivation, I quote:

    m_dx_motivation = sin(angle) * vector_length;
    m_dy_motivation = -cos(angle) * vector_length;

Notice the = signs. Preserve the old information by changing (not: overwriting) it:

    m_dx_motivation += /* something */;
    m_dy_motivation += /* something */;

That may help :+1:

Adding a test would help even more :1st_place_medal:

[richelbilderbeek]

Well done :+1: