Я пытаюсь случайным образом сгенерировать ориентированный граф, чтобы сделать игру-головоломку, похожую на ледяные скользящие головоломки от покемонов.
По сути, это то, что я хочу иметь возможность генерировать случайным образом: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory
Мне нужно иметь возможность ограничить размер графика в измерениях x и y. В примере в ссылке он будет ограничен сеткой 8x4.
Проблема, с которой я сталкиваюсь, заключается не в случайной генерации графа, а в случайной генерации графа, который я могу правильно отобразить в 2-мерном пространстве, поскольку мне нужно что-то (например, камень) на противоположной стороне узла, чтобы это имело смысл, когда вы перестаете скользить. Проблема в том, что порой камень оказывается на пути между двумя другими узлами или, возможно, на другом узле, что приводит к разрыву всего графа.
После обсуждения проблемы с несколькими знакомыми людьми мы пришли к нескольким выводам, которые могут привести к решению. Включая препятствия в сетке как часть графика при его построении. Начните с полностью заполненной сетки и просто нарисуйте случайный путь и удалите блоки, которые заставят этот путь работать, хотя тогда возникает проблема выяснения, какие из них удалить, чтобы случайно не ввести дополнительный более короткий путь. Мы также думали, что алгоритм динамического программирования может быть полезным, хотя никто из нас не слишком опытен в создании алгоритмов динамического программирования из ничего. Любые идеи или ссылки о том, как эта проблема официально называется (если это проблема с официальным графом), были бы наиболее полезными.