Speed Up the Program

[godisreal]

Shall I use Cython to speed up the program?
In current test there are only 8 agents and if there are more, the computation slows down.
The computation complexity increases with the number of agents (in form of N^2).
There are some python program that writes agent model in C/C++. Currently I do not want to rewrite the model in C/C++, but maybe Cython is an alternative way to speed up the program.
I haven't used Cython before. Any suggestions?

[godisreal]

How about rewriting the program in C/C++? Not sure about it.
Python is very easy to use and to test different algorithms. But as the number of agents increase, the computation efficiency drops down remarkably.
Yet if I use C/C++, shall I keep using SDL? Comments are much welcome! @chraibi

[chraibi]

Maybe first you could try to fix the N^2 problem. Alone, from this you will be able to improve the performance of the code.

Cython is a good option also.

But, I think it depends on what you want to do. If your code is dedicated to explain and demonstrate ideas, then maybe Python is just fine. If you care about big and complex simulations , where run-time speed is important, then probably it would be even better to join another open-source software instead of reinventing the wheel.

[godisreal]

Thank you for your valuable suggestion. Any better solution to N^2 problem? I suppose not.

I checked some other programs of pedestrian simulation. I think there must be two loops to compute interaction of N agents. One can save some computation time if two agents are far away so that their interaction is almost ignored, but the algorithm of two loops serves as a baseline.

If there are also M walls and L doors and exits, inner loop will count them and the entire complexity is N*(N+M+L). This is acceptable in computer science. Any better solution? I suppose not.

[chraibi]

Thank you for your valuable suggestion. Any better solution to N^2 problem? I suppose not.

Why do you suppose not?

There are some techniques usually used to solve the problem. You may want to check them out.

• https://en.wikipedia.org/wiki/Cell_lists
• https://en.wikipedia.org/wiki/Verlet_list

The idea is "simply" to keep a list of your neighbors. If you do this in a smart way, then you just have a small loop over your neighbors instead of looping over everyone.

[godisreal]

OK. Thanks for the weblinks. The information is useful.
In my problem there are some long-range forces and the range of the forces are individual-related. Different individuals have different range of interaction force. Not sure whether this is feasible for Verlet List.
In fact I have created a list for each individual agents. If other agents are far away sufficiently, they will not be listed, and they are not calculated for interaction force. The problem exists in how often I should update the list. Let me think about it.

By learning about Verlet List I do find a problem of my existing algorithm. The problem is that I update the list every time step, which is not necessary. In a tuturiol document about Verlet List, I find the following description:

Updating neighbor lists – Typical update frequency ~ 10-20 timesteps

• Too high: method inefficient
• Too low: forces calculated incorrectly

So now I choose DT=0.3 and DT_OtherList = 3.0 in my model, and it means that I update the list every 3 second, and it does speed up the simulation remarkably. So your suggestions are helpful. Thank you.

In brief, collective behavior of pedestrain crowd is different from molecular dynamics. I do not think the criterion of cutting radius is a good one for pedestrian simulation. However, it is feasible to combine Verlet List with a new criterion to speed up the crowd simulation.

[godisreal]

Below is the criterion I am using in this repo (ai means agent i and aj means agent j)

if dij < ai.B_CF*BFactor[idai, idaj] + rij*DFactor[idai, idaj] and no_wall_ij and see_i2j:
    comm[idai, idaj] = 1
    ai.others.append(aj)
else: 
    comm[idai, idaj] = 0

In brief, the surrounding individuals (aj) are in the list (ai.others) if three conditions hold:

1. The long-range force (group force) is in the effective range
2. There is no wall between ai and aj
3. ai can see aj (aj is in the front of ai, not in the back of ai)

Maybe I should call it "attention list" because the list includes surrounding agents who draw ai's attention. Comments are appreciated.