Я создаю 2D игру для веб-сайта, где вселенная может стать очень большой (в основном бесконечно большой). Первоначально, Вселенная состоит из 6 звезд, которые находятся на одинаковом расстоянии от начала координат (0, 0). Моя задача - создать больше звезд, у которых будут «контуры» (ребра), которые соединяются друг с другом. Как я могу разработать алгоритм, который отвечает этим ограничениям:
- Звезды генерируются случайным образом наружу. (например, (x, y) координаты для новых звезд будут медленно выходить из (0, 0) во всех направлениях, предпочтительно в спиральном формате)
- Края НЕ будут пересекаться.
- Хотя должна быть некоторая разница, новые звезды не должны быть слишком далеко или слишком близко к другим звездам. (Например, должен быть минимальный радиус)
- Ни одна звезда / точка не должна иметь кратность больше 3.
- Учитывая, что все это будет храниться в базе данных, алгоритм не может быть слишком дорогостоящим. Другими словами, я хотел бы достичь чего-то сложности O (n) (я не знаю, возможно ли это).
По сути, я собираюсь представить спиральную галактику, где звезды - это точки на графике, а путешествие между звездами изображено гранями между этими звездами.
Конкретные шаги, которые мне нужно решить:
- Произведите случайное генерирование точки в соседней окрестности других звезд, которые еще не имеют кратности 3.
- Найдите первую звезду, у которой еще нет кратности 3, которая не приведет к конфликту краев.
- Если звезда находится на расстоянии не менее x единиц, создайте грань между двумя точками.
Я пытался найти решения, но мои математические навыки (и знания по теории графов) требуют много работы. Кроме того, любые ресурсы / ссылки по этому вопросу будет принята с благодарностью.
Вот некоторый псевдокод, о котором я думал, но я не уверен, что это сработает, и я уверен, что он не будет работать ужасно хорошо после нескольких 10 000 звезд и т.д.
newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
for (star in the known universe):
if(distance between newStar and star > x units):
if(star has < 3 multiplicity):
if(path from newStar to star does not intersect another path):
connect the star to the other star
break;
newStar = new random (x, y) coordinateКроме того, если у кого-нибудь есть какие-либо советы о том, как мне хранить это в базе данных MySQL, я был бы также признателен за это.
Наконец, в случае, если ничего не имеет смысла выше, я включил изображение того, чего я хотел бы достичь ниже:
источник
Ответы:
Предложение: Держите внутреннюю сеть юниверсов идеально упорядоченной, алгоритмической и относительно простой. Вам нужно только, чтобы юниверс выглядел случайным, когда он отображается на экране пользователя . Применяйте только случайные смещения к положениям звезд для отображения пользователем.
Проблема: наиболее очевидный подход вычисления случайного смещения для каждой звезды не очень хорошо спрятал бы скрытую истинную структуру. Вы можете только рандомизировать звезды на небольшое количество, прежде чем они рискуют столкнуться друг с другом или пересечь пути.
Решение: Вы можете применить большие случайные искажения и получить гораздо более случайную и интересную вселенную, если будете применять скоординированную нелокальную случайность. Представьте себе размещение звезд на резиновом листе, и представьте, как случайно растягиваются и сжимаются разные части листа. Это может сдвинуть целые группы звезд на большое расстояние. Они никогда не будут сталкиваться или пересекаться, потому что соседние звезды растягиваются и сжимаются относительно друг друга.
Как это сделать: Посмотрите генераторы фрактальной местности. Для этого есть много свободного и открытого кода. Вам нужен только базовый код, который генерирует значение высоты для каждой точки на карте. Мы собираемся использовать это по-другому. Используйте этот код для создания ДВУХ независимых карт местности-высоты. Начните с истинного положения X, Y звезды, посмотрите на это местоположение на каждой карте, используйте одно значение карты, чтобы сместить положение отображения звезды X, и используйте другое значение карты, чтобы сместить положение отображения звезды Y. Вам придется поиграть с некоторыми из коэффициентов масштабирования, но это может дать вам случайный эффект деформации резинового листа. Большие изменения в положении звезды должны полностью скрывать основные упорядоченные позиции. Фрактальная природа случайности даст очень естественный эффект,
источник