Rocket Science for Fun and Fun

 

Есть такая замечательная кроссплатформенная игрушка - Kerbal Space Program - симулятор космической программы, где нужно конструировать космические корабли и бороздить ими просторы вселенной, летая к другим планетам, строя космические станции и т.д. Для строительства кораблей доступно множество готовых частей (двигатели, топливные баки, кабины для космонавтов, вспомогательные маневровые двигатели, парашюты для посадки, крылья и закрылки, лестницы, солнечные батареи и всякое прочее), которые можно комбинировать множеством способов. Ваша задача - написать программу, которая получит на вход два ключевых параметра (масса полезного груза и delta-V бюджет) и придумает ракету наименьшей массы, способную поднять этот груз в космос и доставить его до цели, обеспечив требуемый бюджет скорости.

Delta-V бюджет

Для космического корабля с выключенными двигателями, находящегося в гравитационном поле планеты или звезды, его дальнейшая судьба определяется только его скоростью и не зависит от массы и формы корабля. Если скорость не слишком велика, то в каждый момент времени он движется по орбите вокруг захватившего его небесного тела. Чтобы переместиться от одной планеты к другой, необходимо как минимум дважды поменять текущую орбиту: сперва перейти на эллиптическую орбиту, проходящую мимо обеих планет, затем перейти на орбиту вокруг новой планеты. Каждая такая смена орбиты есть изменение текущей скорости: к старому вектору скорости прибавляется некоторый корректирующий вектор ∆v и получается новый вектор скорости, соответствующий новой орбите. В промежутках между сменами орбит корабль летит по инерции и топливо не тратит. Стоит заметить, что эта ∆v не зависит от характеристик корабля и зависит только от маршрута: в каком месте с какой орбиты на какую переходим. При планировании межпланетной миссии составляется план маневров, и ∆v всех маневров суммируется в общий ∆v бюджет, который определяет, сколько нужно топлива: если его будет меньше, то пролететь по маршруту не получится, а если слишком много, то корабль выйдет излишне тяжелым и дорогим.

Расчет ∆v

Для расчета изменения скорости при использовании ракетного двигателя используется уравнение Циолковского:

∆v = log (m_start / m_end) * Isp * 9.816

где:

  • m_start - общая масса корабля в начале маневра (в момент включения двигателя)
  • m_end - общая масса корабля в конце маневра (в момент выключения двигателя)
  • Isp - удельный импульс - характеристика эффективности двигателя
  • 9.816 - используемая в игре константа для g.
  • логарифм натуральный
Разница между m_start и m_end - это масса потраченного во время маневра топлива. В m_start и m_end входит и масса полезного груза, и масса двигателей, соответственно, чем легче корабль, тем больше будет ∆v при тех же затратах топлива и том же двигателе, или, другими словами, тем меньше нужно топлива для достижения заданного ∆v. Когда ракета состоит из нескольких ступеней, отстреливая отработавшую ступень, мы резко уменьшаем общую массу корабля и тем повышаем эффективность двигателей очередной ступени. Разные двигатели имеют разную массу и разный удельный импульс. Еще один важный параметр двигателей - сила тяги, выражаемая в Ньютонах. Некоторые двигатели имеют небольшую массу и большой удельный импульс, что делает их чрезвычайно эффективными по топливу, но при этом они могут иметь совсем небольшую тягу. И если далеко в космосе это может быть приемлемо, то при взлете с планеты этой тяги может быть недостаточно, чтобы оторваться от поверхности. Кроме того, удельный импульс двигателя может быть различным в вакууме и в атмосфере. Для простоты будем считать, что самая первая ступень ракеты (которая включается при старте) работает в атмосфере, а остальные ступени будем расчитывать с удельным импульсом в вакууме.

Структура ракеты

Игра позволяет строить весьма разнообразные и причудливые корабли, но для упрощения расчетов и сужения пространства поиска мы введем ряд ограничений на их структуру. Ракета состоит из нескольких ступеней: при старте начинают работать двигатели первой, самой нижней, ступени, используя топливо из баков первой ступени. Когда топливо в них заканчивается, первая ступень (пустые баки и двигатели) отстреливаются специальным разделителем, после чего тут же начинают работу двигатели второй ступени. И так далее, пока не будет отброшена последняя ступень ракеты-носителя и не останется один лишь полезный груз (это может быть посадочный модуль со своими двигателями, но в рамках данной задачи это для нас неважно, важна лишь его масса). Каждая ступень состоит из опциональной центральной части (топливные баки и, обычно, двигатель), являющейся частью "ствола" ракеты, и 0, 2, 3, 4 или 6 боковых частей, также состоящих из топливных баков и опционального двигателя под ними. Т.е. всего возможны три формы ступени:
  1. только центральная часть (ствол)
  2. центральная часть + боковые части вокруг него
  3. только боковые части
Третий вариант возможен только при условии, что следующая (по времени работы) ступень - первого типа (только ствол). Фактически, первая и третья форма - это вторая, разбитая на две фазы, где сначала отрабатывают боковые двигатели, отстреливаются, и лишь затем работает центральный.

Каждая часть ступени (центральная или боковые) состоит из 1-3 топливных баков, поставленных вертикально друг на друга, и, опционально, двигателя под ними. В ступенях первой и третьей формы двигатели обязаны быть во всех частях. В ступени второй формы, состоящей из центральной части и N боковых, двигателей может быть либо 1 (только в центре), либо N+1 (везде). В пределах одной ступени все топливные баки и все двигатели одинаковые. Число баков во всех частях ступени тоже одинаковое.

Параметры всех двигателей и топливных баков перечислены здесь:
http://wiki.kerbalspaceprogram.com/wiki/Parts
В данной задаче используем только Liquid Fuel Engines размера Small и Large, а также топливные баки размера Small и Large. Другие двигатели и баки не используем, всякие твердотопливные бустеры тоже игнорируем. Для удобства, вот полный список интересующих нас двигателей и баков в синтаксисе хаскелеподобных языков: 

data Diam = Small | Large
data Fuel = F String Float Float Diam -- name m_full m_empty size

allFuels = [
  F "FL-T100 Fuel Tank" 0.5625 0.0625 Small,
  F "FL-T200 Fuel Tank" 1.125 0.125 Small,
  F "FL-T400 Fuel Tank" 2.25 0.25 Small,
  F "FL-T800 Fuel Tank" 4.5 0.5 Small,
  F "Rockomax X200-8 Fuel Tank" 4.5 0.5 Large,
  F "Rockomax X200-16 Fuel Tank" 9 1 Large,
  F "Rockomax X200-32 Fuel Tank" 18 2 Large,
  F "Rockomax Jumbo-64 Fuel Tank" 36 4 Large]

--              name   size mass  thrust  Isp_atm Isp_vac
data Engine = E String Diam Float Float   Float   Float 
allEngines = [
 E "LV-T30 Liquid Fuel Engine" Small 1.25 215 320 370,
 E "LV-T45 Liquid Fuel Engine" Small 1.5  200 320 370,
 E "LV-909 Liquid Fuel Engine" Small 0.5  50  300 390,
 E "Toroidal Aerospike Rocket" Small 1.5  175 388 390,
 E "Rockomax \"Poodle\" Liquid Engine"   Large 2.5 220  270 390,
 E "Rockomax \"Mainsail\" Liquid Engine" Large 6   1500 280 330,
 E "Rockomax \"Skipper\" Liquid Engine"  Large 4   650  300 350,
 E "LV-N Atomic Rocket Engine" Small 2.25 60  220 800 ]
(масса в тоннах, тяга в килоньютонах)

Между собой ступени соединяются разделителями. Вертикально они соединяются в стволе. Если двигатель верхней ступени и бак нижней ступени оба размера Large, то используется "Rockomax Brand Decoupler" массой 0.4 тонны. В противном случае используется "TR-18A Stack Decoupler" массой 0.05 тонны. Для горизонтального отделения боковых частей (разделения ступеней первой и третьей форм) используется "TT-38K Radial Decoupler" массой 0.025 тонны. Масса разделителя прибавляется к общей массе нижней (отделяемой) ступени.

Замечание: двигатель "Toroidal Aerospike Rocket" не соединяется с разделителями, поэтому его нельзя использовать в центральной части, под которой будут другие ступени. Можно в боковых частях и можно в центральной части самой нижней ступени (хотя там он вряд ли пригодится).

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

Формат решения

Программа должна получать на вход два вещественных числа: массу полезного груза в тоннах и Delta-V бюджет в м/с. На выход она должна выдать конфигурацию ступеней в порядке сверху-вниз (первой выводится ступень, отрабатывающая позже всех, последней выводится ступень, отрабатывающая раньше всех) в формате JSON-списка. Параметры одной ступени:
  • "fuel" - название топливного бака, используемого в этой ступени, строка
  • "engine" - название двигателя, строка
  • "central" - есть ли в этой ступени центральная часть (true/false)
  • "numSideParts" - кол-во боковых частей в этой ступени: 0, 2, 3, 4 или 6.
  • "numEngines" - число двигателей в ступени (число: 1, numSideParts или numSideParts + 1)
  • "height" - число топливных баков в одной части (1, 2 или 3).
Пример конфигурации:
[
 {"fuel": "FL-T400 Fuel Tank",
  "engine": "LV-N Atomic Rocket Engine",
  "central": true,
  "numSideParts": 3,
  "numEngines": 1,
  "height": 1},
 {"fuel": "Rockomax X200-16 Fuel Tank",
  "engine": "LV-T30 Liquid Fuel Engine",
  "central": true,
  "numSideParts": 2,
  "numEngines": 3,
  "height": 1},
 {"fuel": "Rockomax X200-8 Fuel Tank",
  "engine": "Rockomax \"Skipper\" Liquid Engine",
  "central": true,
  "numSideParts": 4,
  "numEngines": 5,
  "height": 1} 
]
Число ступеней должно быть не больше 7. И сумма высот (числа баков по вертикали) всех ступеней со стволом не должна быть больше 7. Т.е. всего в ракете-носителе может быть максимум 7 ступеней единичной высоты. Или две стволовых ступени по 3 бака, одна ступень с одним, и сколько-то чисто боковых. А может быть всего лишь две ступени по два бака, например, т.е. общая высота может быть и меньше 7.

Общий запас delta-V для ракеты определяется как сумма delta-V всех ступеней. При расчете ∆v одной ступени следует учитывать, что m_start есть сумма массы полезного груза, массы всех следующих (по времени) ступеней и массы текущей ступени при полных баках. m_end - то же, но уже с пустыми баками текущей ступени. Суммарное значение ∆v должно получиться больше или равным заданному на входе требуемому бюджету. При этом следует минимизировать суммарную массу всей ракеты. При расчете ∆v следует брать Isp двигателя в вакууме для всех ступеней кроме стартовой (последняя в выводимом списке), для которой следует использовать значение Isp в атмосфере. Считаем, что первые 5000 м/с бюджета тратятся на подъем с Земли Kerbin'a и выход на его орбиту. Поэтому ступени, работающие на этом участке, обязаны давать тягу такую, которая в невесомости бы дала ускорение 15 м/с2. Тяга для ступени считается как произведение числа двигателей на тягу (thrust) одного двигателя. Поскольку тяга - это сила, F = m*a, F/m = a, отношение тяги к массе m_start должно быть не меньше 15 для тех ступеней, что дают первые 5000 м/с ∆v. Для последующих ступеней минимально допустимое ускорение равно 5 м/с2, т.е. отношение тяги к m_start таких ступеней должно быть не меньше 5.

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

Проверить решение и сравнить расчеты по ракете можно здесь:
Калькулятор ракет.

Решение ваша программа должна находить за 2 минуты. Присылайте конфигурации, найденные вашей программой для таких параметров:

  1. m = 10.4, ∆V = 7000 (codename: Mun)
  2. m = 1.5, ∆V = 12000 (codename: Kerbol)
  3. m = 11.0, ∆V = 10500 (codename: Moho)
  4. m = 12.0, ∆V = 14800 (codename: Laythe)
а также исходники и время, за которое программа нашла решение, а вы нашли программу. :)