Математическая генерация дна моря (глубины), Задача на мат.логику и/или программиование (не Стром-2.х) Опции

[ALexusB]

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

Уперся в генерацию (роботом) дна (мелей)

Дано:
Есть матрица, например, 64х64 или 100х100, не важно, хоть 100х60 клеток.
Значение клеток - это глубина в метрах.
Для простоты считаем до 7 метров, далее для корабля не важно - "нет дна".
То есть 1 2 3 4 5 6 7 видов значений.

переходы глубин плавные, то есть 1-2 2-3 и тп, 1-7 или 1-3 быть не может.

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

Требуется
Алгоритм генерации мелей амебообразной формы (из значений 1) с плавным переходом в 7

Решение

???

Какие есть идеи?

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

[os_]

Если я правильно понял, то координаты точек по периметру «амебы» известны (заданы), тогда предлагаемый расчет выполняется для каждой точки координаты слева направо сверху вниз по каждому ряду матрицы (как сканер). Рандом +1 или -1 к предыдущей точке ряда. Если =7, то только -1. Необходимо учитывать кол-во координатных точек в каждом ряду, т.е. если до конца ряда осталось 7 точек и глубина=7, то каждая следующая до конца точка – минус 1. (чтобы выйти обратно на =1). Наверное так.

[Belphegor]

Попробовал смоделировать в эксельке. Не до 7, до 5.
Получается примерно так.

Код

5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5
5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5
5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5
5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5    5    5    5    5    5
5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5    5    5    5    5    5
5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5
5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5
5    5    4    4    3    3    3    3    3    3    3    3    3    4    4    4    4    4    4    4    4    4    4    5    5
5    5    4    4    3    3    3    3    3    3    3    3    3    3    3    3    3    3    3    3    3    3    4    5    5
5    5    4    4    3    3    3    3    3    3    3    3    3    2    2    2    2    3    3    3    3    3    4    5    5
5    5    4    4    3    3    3    3    3    3    3    3    3    2    2    2    2    3    3    3    3    3    4    5    5
5    5    4    4    3    3    3    3    2    2    2    2    3    2    2    2    2    2    2    3    3    3    4    5    5
5    5    4    4    3    3    3    3    2    1    2    2    3    2    2    2    1    1    2    3    3    3    4    5    5
5    5    4    4    3    3    3    3    2    2    2    2    2    2    2    1    1    1    2    3    3    3    4    5    5
5    5    4    4    3    3    3    3    2    2    2    2    2    1    2    2    2    2    2    3    3    3    4    5    5
5    5    4    4    3    3    3    3    3    3    3    2    1    2    2    3    3    3    3    3    3    3    4    5    5
5    5    4    4    4    4    4    4    3    3    3    2    2    2    2    3    3    3    3    3    3    3    4    5    5
5    5    4    4    4    4    4    4    3    3    3    3    3    3    3    3    3    4    4    4    4    4    4    5    5
5    5    4    4    4    4    4    4    3    3    3    3    3    3    3    3    3    4    4    4    4    4    4    5    5
5    5    5    5    4    4    4    4    3    3    3    3    3    3    3    3    3    4    4    4    4    4    4    5    5
5    5    5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5
5    5    5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5    5    5    5
5    5    5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5    5    5    5
5    5    5    5    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    4    5    5    5    5    5
5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5    5

Суть такая: заполняем квадрат 25*25 пятерками.
Потом берем квадрат 16*16, сделанный из четверок и заменяем пятерки на четверки в случайном месте.
Но для плавного перехода нужно сделать проверку сперва: чтоб квадрат (16+2)*(16+2) (по полю с каждой стороны) с теми же центральными клетками, что и квадрат 16*16, не имел шестерок (у меня их вообще нет, но это для всех справедливо).
Потом берем квадрат 9*9, берем рандомный центр снова, проверяем, нет ли пятерок в квадрате 11*11 с тем же центром, что и у 9*9.
Таких квадратов можно поставить несколько.

И так далее.

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


Прочитал сам. что написал. Сумбурно... Но вдруг покажется интересным.

Короче метод "выкапывания ямы". Копать есть смысл только в уже выкопанном, а слишком глубоко в одном месте копать нельзя - осыпется.


____________
А, если не секрет, где это должно использоваться? Что за "кораблики"?

[ALexusB]

2Belphegor

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

2os_

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

[Destynar]

Можно попробовать сделать аналог топографической карты.

Например генерится случайно на матрице n точек глубины m+/-х. От этих точек концентрически расходится повышение/понижение грунта до соприкосновения с соседней областью.

В результате получится случайная карта глубин.
Генерить соответственно можно и фигуры из 2-n точек (в форме круга, эллипса, буквы "г" и т.п.)

[ALexusB]

2Destynar
Это и нужно - другое дело алгоритм всего этого.

Кстати, как переложить элипс на матрицу? Какая формула для клеток?

Можно выбирать шаблон: элипс, квадрат, и делать 2-3 мели - тогда и буква Г и Х будут сами собой

Если делать вложенные квадраты, то даже при рандоме будет прослеживаться квадратность, Потому лучше элипсом лепить - это естестеннвая форма хотя бы.

А, если не секрет, где это должно использоваться? Что за "кораблики"?

все для того же
http://legend.seaward.ru/forum/index.php?showtopic=11912

[Destynar]

Ну например:
Есть клетка матрицы (100x100), с координатами х,у. Тогда:
1. х=0, у=0
2. х=х+а, где а - случайное число от 0 до 99
3. у=у+b, где b - случайное число от 0 до 99

Получаем случайную точку на матрице.
Потом задаем этой точке глубину:

g(глубина)=m (+/-) n, где m - средняя глубина на участке (допустим 3), а n - разброс глубин (пусть будет 2).

Соответственно потом строим цикл, и повторяем его q раз (q - сложность рельефа дна) (пусть 4)

Тогда у нас 4 точки с произвольными координатами на матрице, глубиной от 1 до 5.

Далее.
Записав координаты этих точек, получаем для каждой 8 точек, которые вокруг. И устанавливаем их глубину g (+/-) 1 (на повышение грунта или на понижение)
т.е. это получается для всех точек "х (+/-) 1 or y (+/-) 1"

Соответственно для следующего круга будет
g (+/-) 2
"х (+/-) 2 or y (+/-) 2"

И так до точки, у которой g!=0 (не равно).
Тут надо подумать, правда, что делать когда разница на границе 2 и более, но это уже технический вопрос.

Ну вот как-то так.

[Belphegor]

Соответственно для следующего круга будет
g (+/-) 2
"х (+/-) 2 or y (+/-) 2"

А как? там же во втором круге уже 16 точек, потом 24 и так далее...

А еще вдруг

т.е. это получается для всех точек "х (+/-) 1 or y (+/-) 1"

в точке будет g + 1
а потом g - 2

разница... большая...

Или я туплю.


http://ru.wikipedia.org/wiki/%D0%AD%D0%BB%...%B8%D0%BF%D1%81
про эллипс

[Destynar]

g (глубина) - тут выбирается на повышение идет грунт или на понижение. т.е. + ИЛИ - (для всех изменений g)

насчет второго круга прав, так он будет выбирать те же 8 точек... Надо усложнить уравнение...

[ALexusB]

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

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

[Belphegor]

А нельзя сетку использовать не квадратную, а шестиугольную? Соты?
Они круглее и там диагоналей нет.

[ALexusB]

Теоретически можно, но не в моем случае

Упраылять сотами - это не матрица (готовая структура в коде).
Это сложности перехода между клетками, это сложности преобразования координат.
И тормоза при вычислении - а мне критична скорость обработки

[Serginio]

Искомый (генерируемый) объект имеет критическую кривую со значением 7 (периметр) и критические точки со значением 1 (пики или вершины мели). Количество пиков (пусть будет не более 4), а также значение высоты пика (например от 1 до 4) можно задать случайным генератором чисел. Также рандомно задаются координаты пиков. Дальше построение (генерация) объекта закладывается по принципу от пика к глубине в 8 направлениях- каждое следующее соседнее значение (Условие 1) точки должно быть равным или на единицу большим (случайная генерация) и так до достижения значения 7. Для однопиковой мели будет работать идеально, не нужно даже задавать критический периметр... Можно также задать коэффициент корреляции, чем он выше, тем круче будут откосы мели и наоборот. Не знаю как по скорости, но в математике такое будет работать. По окончании генерации мель будет иметь форму шатра с 8-ю лапами разной длины и скольугодно (рандомно) плоской вершиной.
Для многопиковых сложнее, но можно задать функцию: если два откоса мели стыкуются со значениями 4 и 6, то 6 изменить на 5 (следующую 6 при необходимости тоже на 5, до выполнения условия 1). Но здесь уже сложно для мох куриных мозгов...
Я не программист, поэтому не смейтесь, если чего не так

[Belphegor]

Ну погоди, по 8 направлениям... А промежуточные клетки на кругах, больших второго?

3 _ 2 _ 3
_ 2 1 2 _
2 2 1 1 2
_ 2 2 2 _
2 _ 3 _ 2


вот так будет после второго заполнения, если я правильно понял.
А как заполнить остаток?

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

[Serginio]

Ну погоди, по 8 направлениям... А промежуточные клетки на кругах, больших второго?

...А как заполнить остаток?

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

Снизу - сложнее. Во-первых нужно задать критический периметр из множества точек. Во-вторых количество этих рандомных точек должно быть достаточно большим с определёнными взаимовлияющими значениями. Это трудоёмко для случайной генерации.
А остаток заполняется по тому же условию 1 От оси вправо, например. И это будут не клетки на кругах, а клетки в рядах (математика, по крайней мере, так их будет трактовать).
Кроме того, ты рассматриваешь мель, как неправильный эллипс внутри поля (пусть 64*64) с замкнутой кривой периметра. Тогда мы будем иметь только песчаные банки. А если использовать случайный выбор координат пика, то вероятна возможность его размещения слишком близко к краю такого поля, тогда мы будем иметь мель с одним склоном пологим, а другим обрывающимся, условно назовём таку мель риф. Такие образования в геологии отнюдь не редки и называются "сброс" или "взброс" в зависимости от морфологии образования (поверь горному инженеру). А если не нравится риф, то задаём условие генерации координат пика - не ближе 7-10 пунктов от края поля...

[Belphegor]

А остаток заполняется по тому же условию 1 От оси вправо, например. И это будут не клетки на кругах, а клетки в рядах (математика, по крайней мере, так их будет трактовать).

Нифига не понимаю. Главное, чтоб Алексус понял.

3 _ 2 _ 3
_ 2 1 2 _
2 2 1 1 2
_ 2 2 2 _
2 _ 3 _ 2


Ну вот берем

и заполняем верхний ряд по правилу: пустая клетка равна или меньше на единицу клетки слева от нее

3 3 2 1 3 2
_ 2 1 2 _
2 2 1 1 2
_ 2 2 2 _
2 _ 3 _ 2


Получается так. К примеру. А это две ошибки.
Или я все-таки неправильно тебя понял? Не бейте сильно, если что...

Кроме того, ты рассматриваешь мель, как неправильный эллипс внутри поля (пусть 64*64) с замкнутой кривой периметра.

Ну так, вроде так и спрашивалось...

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

Ну квадратную систему я предложил. Периметр получается рандомный.
Вот только квадратность.

[Serginio]

Нифига не понимаю. Главное, чтоб Алексус понял.

и заполняем верхний ряд по правилу: пустая клетка равна или меньше на единицу клетки слева от нее

3 3 2 1 3 2
_ 2 1 2 _
2 2 1 1 2
_ 2 2 2 _
2 _ 3 _ 2
Получается так. К примеру. А это две ошибки.
Или я все-таки неправильно тебя понял? Не бейте сильно, если что...

Уважаемые Belphegor и ALexusB. Простите, я оговорился, условие 1 должно звучать так: каждое следующее соседнее значение точки должно быть равным или на единицу большим.
Не случайно в твоём втором примере справа от центральной верхней двойки появилась 1. Значение должно быть или 2 или 3 другого быть не может... Тогда всё работает. Просто понижение уровня грунта в мели я подменил формулировкой "понижение значения цмфры", это логический казус, приведший к неправильному написанию (прочтению) условия.
Ещё раз извините...
Короче, вокруг точки со значением 1 могут находиться точки со значениями 1 или 2. Вокруг точки со значением 2 могут находиться точки со значениями 1,2 или 3. вокруг точки со значением 3 могут находиться точки со значениями 2,3 или 4 и т.д. Частично такая схема используется в игре "Сапёр"...
Если использовать такое условие в чистом виде, то мель будет формироваться вокруг пика и иметь хаотично-бугристый вид. Вид бессистемно разбросанных по болоту кочек, и на всей площади поля может не быть ни одного значения 7... Кстати, при соблюдении условия 1, такое тоже возможно Но это не сложно поправить...

[Belphegor]

Это я ступил. Сперва понял правильно (прибавлял), а потом стал вычитать.
Но все равно, вот гляди

Короче, вокруг точки со значением 1 могут находиться точки со значениями 1 или 2. Вокруг точки со значением 2 могут находиться точки со значениями 1,2 или 3. вокруг точки со значением 3 могут находиться точки со значениями 2,3 или 4 и т.д.

Имеем две находящиеся рядом точки - 2 и 3 и две пустые точки внизу. Допустим, что вверху где-то находится пик, поэтому заполнение идет вниз.
Если заполнение радиально.
2 3
_ _
Вокруг точки со значением 2 могут находиться точки со значениями 1,2 или 3.
допустим 2.
2 3
2 _
вокруг точки со значением 3 могут находиться точки со значениями 2,3 или 4 и т.д.
а вот если поставить 4, то первое условие нарушается и вводится ошибка
2 3
2 4

А если заполнение построчно - если расчет вести не от верхней точки, а от, к примеру, левой, то может получиться так
2 3
2 _
Вокруг точки со значением 2 могут находиться точки со значениями 1,2 или 3.
2 3
2 1

Получается хаотично-бугристый, но тут бугры чересчур крупные.
Хотя логически правильно. То есть нужно дополнительно проверять? Вот мне и кажется, что слишком много условий.

[ALexusB]

Нифига не понимаю. Главное, чтоб Алексус понял.

Я тоже не догнал

Точнее, подход от высоты (1) в глубину (7) я уже пробовал +- тапки также на понижение - это слишком сложный многопроходовый алгоритм. При этом у нас не должно быть мелей 1х1 - они не имееют смысла. Нужно минимум 7х7 + выравнивание до некой не квадратной фигуры.

То есть, нужно генерить размер мели еще, а потом от нее на понижение идти - и тут вторая трабла - 2-3 мели одновременно
Их нужно тогда генерить сперва (1), а потом выравнивать по более сложному правилу, тк будет 1-2-3-2-1
И оны перехода тоже должн быть разные, то есть
1-1-2-2-2-2-3-3-3-3-2-2-1 - то есть нет симертии.

Пока у мя в голове сложилась рабочая картина предложеноого квадратами от 7 до 1, но нужно ее загруглить.


Еще нет совершенно никакой проблемы, если мель попадет в угол карты. Просто клетки за гранью не отработают.

[Serginio]

2 3
2 _
вокруг точки со значением 3 могут находиться точки со значениями 2,3 или 4 и т.д.
а вот если поставить 4, то первое условие нарушается и вводится ошибка
2 3
2 4

Ты сам себя запутываешь. Поставить 4, безусловно можно, но следуя какому алгоритму? Т.е. откуда там взялась 4? Если основная ось проходит вертикально вниз через цифру 3 в твоём примере, то цифра 4 будет находиться на основной оси и мы от неё по часовой стрелке образуем ряд, в котором у тебя почему-то уже стоит двойка (эта двой должна быть вторичной), т.е. образовываться после четвёрки, тогда сгенериться не 2, а 4 или 5 (условие 1). Если же первична твоя нижняя двойка, то работает (условие 2) вокруг двойки могут быть цифры 1, 2 или 3; но вокруг тройки (верхней) могут быть цифры 2,3 или 4, т.е. сгенериться или 2 или 3 от наложения условий.

А если заполнение построчно - если расчет вести не от верхней точки, а от, к примеру, левой, то может получиться так
2 3
2 _
Вокруг точки со значением 2 могут находиться точки со значениями 1,2 или 3.
2 3
2 1

Здесь проще. Условие 1 гласит, что цифра должна быть равна или больше. Единицы здесь ни в каком случае не будет (если генерация идёт сверху вниз). Если же генерация идёт снизу, то не будет тройки.

Получается хаотично-бугристый, но тут бугры чересчур крупные.
Хотя логически правильно. То есть нужно дополнительно проверять? Вот мне и кажется, что слишком много условий.

В твоих примерах не крупные бугры. Здесь противоречие. Как математическое, так и логическое. Между глубиной 1 метр и глубиной 3 метра обязательно существует точка с глубиной 2 метра. Даже в случае вертикального размещения плоскости. Посмотри любую геологическую карту. На ней изогипсы (линии высот или глубин) никогда не пересекаются и не соединяются. В принципе что-то подобное нужно сгенерировать и здесь.
Я прекрасно вижу свою ошибку, вернее ту ситуацию, когда условия пересекутся, но, надеюсь, что поле не будет таким огромным, да и уважаемый ALexusB наверняка знает парочку волшебных слов, чтоб это отрегулировать
Хотя не исключаю, что моя модель с точки зрения программирования - есть полная туфта и бред дилетанта.