Как сделать так, чтобы петли проходили рядом?

Question

Я работал над маленькой детской программой: на экране куча маленьких кружочков разных цветов и размеров. Когда большой круг сталкивается с меньшим кругом, он съедает меньший круг, а когда круг съел достаточно других кругов, он воспроизводит. Это вроде аккуратно!

Однако, как я это реализовал, процесс обнаружения соседних кругов и проверки их на пригодность к употреблению выполняется с помощью цикла for, который циклически проходит по всему живому населению кругов ... который длится все дольше по мере того, как население стремится к этому. всплеск 3000, прежде чем он начинает падать. Процесс не замедляет мой компьютер, я могу уйти и поиграть в Dawn of War или что-то в этом роде, и никакого замедления не происходит: это просто процесс проверки каждого круга на предмет его столкновения с каждым другим кругом ... .

Так что мне пришло в голову то, что я мог бы попытаться разделить окно приложения на четыре квадранта, и чтобы круги в квадрантах выполняли свои проверки одновременно, так как у них почти не было бы возможности мешать друг другу: или что-то еще на этот счет!

Тогда мой вопрос: как сделать петли, которые идут рядом? На Java скажем.

Answer 1

проблема, которая у вас есть, может быть решена без потоков.

Вам нужна пространственная структура данных. лучше всего использовать четырехугольное дерево, или если поле, в котором движутся сферы, является фиксированным (я предполагаю, что это так), вы можете использовать простую сетку. Вот идея.

Разделите область отображения на квадратную сетку, где каждая ячейка, по крайней мере, такая же большая, как ваш самый большой круг. для каждой ячейки ведите список (лучше всего связанный список) всех кругов, центр которых находится в этой ячейке. Затем на этапе обнаружения столкновения пройдите через каждую ячейку и проверьте каждый кружок в этой ячейке на предмет всех остальных окружностей в этой ячейке и окружающих ячейках.

технически вам не нужно проверять все ячейки вокруг каждой, поскольку некоторые из них, возможно, уже были проверены.

Вы можете комбинировать эту технику с методами многопоточности, чтобы получить еще лучшую производительность.

Answer 2

Компьютеры, как правило, имеют однозадачность, это означает, что они обычно могут выполнять одну инструкцию за один раз на процессор или ядро.

Однако, как вы заметили, ваша операционная система (и другие программы), по-видимому, одновременно выполняют много задач.

Это достигается путем разделения работы на процессы, и каждый процесс может дополнительно реализовать параллелизм, порождая потоки. Затем операционная система очень быстро переключается между каждым процессом и потоком, создавая иллюзию многозадачности.

В вашей ситуации ваша java-программа - это отдельный процесс, и вам нужно будет создать 4 потока, каждый из которых будет выполнять свой цикл. Это может быть сложно, поскольку потоки должны синхронизировать свой доступ к локальным переменным, чтобы предотвратить изменение потока одним потоком, в то время как другой поток пытается получить к нему доступ.

Поскольку многопоточность - сложная тема, она потребует гораздо большего объяснения, чем я могу сделать здесь.

Однако вы можете прочитать превосходное руководство Suns по параллелизму, которое охватывает все, что вам нужно знать:

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

Answer 3

То, что вы ищете, это не способ запустить их одновременно (как отметили люди, это зависит от того, сколько у вас ядер, и может предложить только 2-кратное или, возможно, 4-кратное ускорение), но вместо этого как-то сократить на количество столкновений, которые вы должны обнаружить.

Вы должны использовать quadtree . Короче говоря, вы рекурсивно разбиваете свою 2D область на четыре квадранта (при необходимости), и тогда вам нужно только обнаружить столкновения между объектами в соседних компонентах. В хороших случаях это может эффективно сократить время обнаружения столкновений с N ^ 2 до N * log N.

Answer 4

Вместо того, чтобы пытаться выполнять параллельную обработку, вам может потребоваться оптимизация обнаружения столкновений. Потому что во многих ситуациях выполнение меньшего количества вычислений в одном потоке лучше, чем распределение вычислений между несколькими потоками, плюс в этом многопоточном бизнесе легко оказаться на месте. Попробуйте поискать «алгоритм обнаружения столкновений» и посмотрите, куда он вас приведет;)

Answer 5

Это звучит очень похоже на мой эксперимент - зацените ...

http://tinyurl.com/3fn8w8

Меня также интересуют квадри (вот почему я здесь) ... надеюсь, вы все поняли.

Answer 6

Если вы действительно хотите заняться параллельным программированием, вам нужно научиться использовать потоки.

У Sun есть руководство по программированию потоков Java здесь: http://java.sun.com/docs/books/tutorial/essential/concurrency/

Answer 7

Если ваш компьютер имеет несколько процессоров или несколько ядер, вы можете легко запустить несколько потоков и запустить меньшие части циклов в каждом потоке. Многие ПК в наши дни имеют несколько ядер, поэтому сделайте так, чтобы каждый поток получал 1 / nth от числа циклов, а затем создавал n потоков.