Игра Резинка и колышки

Question

Я должен сделать флеш-игру примерно так: Есть доска с отверстиями (более 1000). Изначально на доске размещены 3 колышка и вокруг них резиновая полоса. У нас есть 3 возможных операции: 1. Добавить колышек - добавляет колышек на доску 2. Удалить колышек - удаляет колышек (если имеется более 3 колышков) - резиновая полоса должна принимать форму оставшихся колышков. 3. Переместить колышек - резиновая лента должна быть обновлена ​​с текущими позициями колышков.

Как бы вы решили задачу оптимального определения формы резиновой ленты?

У меня есть 2 идеи, но мне нужно немного поработать над ними. Основная идея заключается в том, что нам нужно менять форму резиновой ленты только при операции «Перемещение», и мы используем такое же количество колышков, только одна меняет позицию:

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

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

У вас есть другие идеи или предложения?

Answer 1

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

Вы просите «оптимальное» решение, но на вашем месте я бы стремился к «правильному и достаточно быстрому» решению. У вас есть контракт на выполнение, вы можете оставить асимптотику академикам.

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

Теперь предположим, что игрок перемещает колышек A с a на a '.

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

Так что же там за события?

• Peg A "поднимает" группу. (Это происходит, если колышка A еще не было на полосе, а линия a – a ' пересекает одну из линий между колышками на полосе.)
• Пег А "опускает" группу. (Это происходит, если на полосе был колышек A с соседями B и C, а линия a – a ' пересекает линию B – C.)
• Пег А получает соседа по группе. (Это происходит, когда колышек A находится на полосе, B - сосед A, а треугольник a – a ' –B содержит еще один колышек C.)
• Peg A теряет соседа по группе. (Это происходит, когда колышек A находится на полосе, соседние колышки на полосе переходят в A-B-C, а колышек B находится в треугольнике a – a ' -C.)

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

(Что делать, если два события происходят одновременно? Я оставлю это на ваше усмотрение.)

Отредактировано, чтобы добавить: сложность заключается в том, что колышек может появиться на более чем одном сегменте резиновой ленты (например, полоса может идти A-B-A-C-A). Но я думаю, что приведенный выше набросок алгоритма все еще работает.

Еще одна проблема заключается в том, что даже с небольшим количеством колышков вы можете произвольно изменять конфигурацию полосы. Например, предположим, что полоса растянута между колышками B и C. Теперь возьмите колышек A и переместите его в виде цифры 8 вокруг колышков B и C (по часовой стрелке вокруг B, против часовой стрелки вокруг C, скажем). Каждый раз, когда вокруг петли, колышек А подбирает еще пару кусочков группы. Вы не можете позволить, чтобы сложность конфигурации росла без ограничений, поэтому нужен какой-то способ не допустить выхода вещей из-под контроля. Я предлагаю наложить максимальный предел на длину полосы, чтобы любая попытка растянуть ее слишком сильно приводила к ее трещотке (конечно, до этого у вас будут предупреждающие знаки, например, полоса становится тоньше, меняется цвет, зловещие скрипучие звуки ).