How do I make cycles run side by side?

Question

I am working on a small children's program: on the screen there are a bunch of small circles of different colors and sizes. When a larger circle collides with a smaller circle, it eats a smaller circle, and when the circle eats enough other circles, it reproduces. It's kind of neat!

However, as I implemented it, the process of detecting neighboring circles and checking them for edibility is carried out using the for loop, which cycles through the entire living population of circles ... which takes more time and more as the population tends to surge in 3000 before it starts to fall. The process does not slow down my computer, I can leave and play Dawn of War or something else, and there is no slowdown: it is just a process of checking each circle to see if it collided with any other circle ..

So, what occurred to me is that I can try to separate the application window into four quadrants, and the circles in the quadrants carry out their checks at the same time, since they will have almost no chance to interfere with each other: for this purpose!

So my question is: how to make loops that work side by side? In Java, let's say.

Answer 1

Computers typically run with a single task, which means that they can usually execute one command at a time on a processor or core.

However, as you noticed, your operating system (and other programs) seems to run many tasks at the same time.

This is achieved by dividing the work into processes, and each process can additionally implement concurrency by spawning threads. The operating system then quickly switches between each process and thread to create the illusion of multitasking.

In your situation, your java program is one process, and you will need to create 4 threads, each of which will start its own loop. This can be tricky because threads must synchronize their access to local variables to prevent one variable from being edited while another thread is trying to access it.

Since threads are a complex subject, this will require much more explanation than I can do here.

However, you can read Suns' excellent Concurrency tutorial, which covers everything you need to know:

http://java.sun.com/docs/books/tutorial/essential/concurrency/

Answer 2

the problem you are here can actually be solved without threads.

You need a spatial data structure. a square tree would be best, or if the field in which the balls move is fixed (I suppose it is), you can use a simple grid. This is an idea.

Divide the display area into a square grid where each cell will be at least as large as your largest circle. for each cell, save the list (a linked list is better) of all circles whose center is in this cell. Then, during the collision detection step, go through each cell and check each circle in this cell against all other circles in this cell and surrounding cells.

technically, you don’t need to check all the cells around each, as some of them may have already been checked.

You can combine this method with multithreading methods to get even better performance.

Answer 3

What you are looking for is not a way to launch them at the same time (as people noted, it depends on how many kernels you have, and can only offer 2x or maybe 4 times acceleration), but instead down in the number of collisions which you must discover.

You should learn quadtree . In short, you recursively split your 2D region into four quadrants (as needed), and then you should detect collisions between objects in adjacent components. In good cases, it can effectively reduce the collision detection time from N ^ 2 to N * log N.

Answer 4

Instead of trying to do parallel processing, you can look for collision detection optimization. Since in many situations, punching fewer calculations in a single thread is better than distributing the calculations between multiple threads, it’s also easy to take your foot off in this multi-threaded business. Try googling "collision detection algorithm" and see where it will get you;)

Answer 5

IF your computer has multiple processors or multiple cores, then you can easily start multiple threads and run smaller parts of the loops in each thread. Many PCs today have several cores - even if each thread receives the 1st / nth of the number of cycles, and then creates n threads.

Answer 6

If you really want to switch to parallel programming, you need to learn how to use threads.

Sun has a tutorial on programming Java threads: http://java.sun.com/docs/books/tutorial/essential/concurrency/

Answer 7

It sounds a lot like my experiment - check it out ...

http://tinyurl.com/3fn8w8

I am also interested in quadrants (which is why I am here) ... I hope you all understand this.