Ответ 1

Если вы проверите Conway Game of Life, вы обнаружите, что есть много общего с проблемой расы.

Вот аналогия:

• Начальное состояние (семя системы):
  • Игра жизни: начальный шаблон на сетке. Каждая ячейка имеет следующие параметры:
    • координата x и y
    • ли живая или мертвая ячейка
  • Задача расы: n машин, каждый из которых имеет заданные параметры и длину дорожки l. Каждый автомобиль имеет следующие параметры:
    • максимальная скорость
    • ускорение
    • коэффициент обработки
    • позиция на треке
    • текущая скорость
• Правила применяются в дискретных моментах, которые называются тиками.
  • Игра жизни: правила применяются одновременно к каждой ячейке предыдущего поколения, производящему следующее поколение. Каждое поколение является чистой функцией предыдущего.
  • Задача расы: правила применяются одновременно к каждому автомобилю из предыдущего состояния, производя следующее состояние. Это происходит каждые 2 секунды. То же, что и в Game of Life, каждый шаг является чистой функцией предыдущего, что означает, что он зависит только от параметров автомобилей от предыдущего состояния.

В отличие от того, что Игра Жизни никогда не заканчивается, тогда как Задача Раса должна заканчиваться, когда текущая позиция каждого автомобиля больше или равна длине дорожки l (Хотя последнее утверждение является спорным: из-за фактора обработки это возможно что в некоторых условиях некоторые машины никогда не достигнут финишной черты).

Ключевым моментом является то, что вычисления выполняются в дискретные моменты, которые отвечают на ваш вопрос:

Но как я могу выяснить, в каком экземпляре я должен выполнить вычисления?

Вы можете воспользоваться этой идеей из раздела Algorithms, чтобы решить эту проблему. Вы должны иметь 2 массива автомобилей: один из которых представляет текущее состояние, а другой - следующий шаг. На каждой итерации вы пересчитываете текущее положение и скорость каждого автомобиля, следуя правилам задания, и проверяете, должен ли цикл прекращаться. Перед следующей итерацией вы меняете роли массива так, чтобы массив преемников в последней итерации становился текущим массивом в следующей итерации.

Псевдокод высокого уровня может выглядеть следующим образом:

n = ..; // initial number of cars
l = ..; // track length
Car[] currentState = initializeState(n, l);
Car[] nextState = clone(currentState);
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
    calculateNextState(currentState, nextState, iteration);
    swap(currentState, nextState);
    if (shouldTerminate(currentState, l) {
        break;
    }
}

printResultOrClaimNotTerminated(currentState);

Правила применяются в функции calculateNextState (..). В самой наивной реализации вы проверяете каждую пару автомобилей, которые дают вам

O (C(n, 2)) = O (n * (n - 1) / 2) = O (n ^ 2)

сложность для каждой итерации. Однако вы можете подумать о возможных оптимизациях здесь. Например, вы можете сначала отсортировать автомобили по текущему положению (O (n * log(n))), а затем пройти сортированный массив, проверяющий только соседние автомобили (O (2 * n)). Вы можете это сделать, поскольку, если 10-метровое состояние не удовлетворяет для соседних автомобилей, оно не будет удовлетворять для несмежных автомобилей. Это даст вам сложность:

O (n * log(n))

что намного лучше. Сортированный массив автомобилей, естественно, даст вам автомобиль с последней позицией, к которой вам нужно применить правило нитроучета. Возможно, возможны и другие оптимизации. Это отвечает на ваш вопрос:

Для каждого экземпляра я должен проверять все комбинации C (n, 2) каждой пары драйверов и вычислять результат?

Ответ 2

Автомобильные объекты и игровой объект

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

Идеи ускорить каждый шаг обновления, чтобы не выполнять все проверки C (n, 2)

Вы можете ускорить шаг позиции обновления и параметров, не проверяя все комбинации C (n, 2). Одна простая эвристика, которую вы можете использовать, заключается в том, что нам не нужно проверять взаимодействия между автомобилями, которые находятся далеко. Например, автомобиль в первой четверти гоночной трассы не будет взаимодействовать с автомобилем в третьей четверти гоночной трассы. Я думаю, основываясь на параметрах вашего вопроса, вы хотите разделить гоночный трек на 10-метровые секции. Ведите список для каждого раздела и отслеживайте все автомобили в каждом разделе. После обновления позиций проверьте только взаимодействие между машинами только в последовательных разделах.

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

Выбор TimeStep

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

Если вы выберете timeStep как большее число (например), автомобиль может пройти через другой автомобиль и избежать обнаружения столкновения. Если, с другой стороны, вы выбираете значение timeStep слишком маленьким, и если время для операций больше, чем timeStep, игра будет работать медленнее, чем в реальном времени.