Соединительные кусочки проводов - алгоритм - PullRequest
0 голосов
/ 05 октября 2011

Я использую C #, но в будущем мне может понадобиться использовать его на других языках.

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

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

Где-то в будущем я тоже попробую то же самое, но на этот раз с проводами, которые разделяют сигнал на 2 или 3 сигнала.

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

Итак, вы можете мне помочь? Я смогу понять алгоритм как «что должна делать программа», но мне нужна помощь в понимании алгоритма как «как писать код».

Спасибо!

Ответы [ 2 ]

1 голос
/ 17 ноября 2012

Взгляните на некоторые алгоритмы генерации лабиринтов - они делают то же самое, что и вы, и как таковые - то, что вам нужно для создания сетки.Выберите простой «клеточный резчик» из тех, с которыми я связан;случайным образом вращайте все фрагменты, et voilà!

В комментарии к вашему вопросу отмечается, что превращение алгоритма в код предполагает его разбивку на куски - так мы и сделаем:

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

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

Но как насчет создания лабиринта?Ресурс, на который я ссылаюсь, содержит несколько алгоритмов, которые идеально подходят для вашего использования - простой рандомизированной DFS должно хватить для ваших нужд.

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

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

0 голосов
/ 26 ноября 2012

Алгоритмы Union-Find (которые отвечают на мою проблему) описаны в этом файле PDF: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

Я не думаю, что когда-либо думал об этом алгоритме, не говоря уже о том, чтобы сделать его быстрым.

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