Произвольно генерировать направленный граф на сетке

Question

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

По сути, это то, что я хочу иметь возможность генерировать случайным образом: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory

Мне нужно иметь возможность ограничить размер графика в измерениях x и y. В примере в ссылке он будет ограничен сеткой 8x4.

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

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

Answer 1

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

Существует статья о быстрой генерации плоских графов.

Answer 2

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