Собсно хочу написать универсальный мининг - разметка пещеры не рулит.
Есть начит массив координат тайлов пещеры, как бы разбить её на квадраты самым оптимальным образом?
Мининг, точнее аспект бегов -)
Moderators: Murderator+, Murderator
-
Destruction
- Junior Expert
- Posts: 3221
- Joined: 2004-06-24 22:08:56
Re: Мининг, точнее аспект бегов -)
Destruction wrote:Собсно хочу написать универсальный мининг - разметка пещеры не рулит.
Есть начит массив координат тайлов пещеры, как бы разбить её на квадраты самым оптимальным образом?
Не понял.
А на кой тебе делить то ?
Ты как планируешь копать, с хождением или так по кругу (то бишь по квадрату) ?
Сделал дело - флуди смело !!!
-
Destruction
- Junior Expert
- Posts: 3221
- Joined: 2004-06-24 22:08:56
Re: Мининг, точнее аспект бегов -)
Askaneli wrote:Destruction wrote:Собсно хочу написать универсальный мининг - разметка пещеры не рулит.
Есть начит массив координат тайлов пещеры, как бы разбить её на квадраты самым оптимальным образом?
Не понял.
А на кой тебе делить то ?
Ты как планируешь копать, с хождением или так по кругу (то бишь по квадрату) ?
Обкапываем квадрат - дуем к следущему.
Вот, расписал, даже нарисовал
)
http://forum.woweb.ru/topic17332.html?st=0#entry140183
Все очень просто.
Расписываю алгоритм по пунктам:
1) Делаем функция подсчета количества красных точек на расстояни от выбранной точки.
2) Устанавливаем где-попало в зеленом секторе красную точку.
3) Запускаем от нее рекурсивную функцию:
for все точки на радиусе N
if у текущей точки на расстоянии (N-1) красных точек нет
ставим сюда красную точку
запускаем эту функцию относительно уже этой новой красной точки
endif
endfor
Теперь как будет работать этот скрипт:
1) Точка одна которая взята случайным образом.
2) найдена точка на расстоянии N, вокруг нее только 1 точка (начальная на расстоянии N (а проверка на расстояние N-1) тоесть сюда ставим красную тоже.
Повторяем 2 для новой точки, и так далее пока вдруг не зайдем в тупик. Зайдя в тупик, функция просто переберет все точки, и возвратиться на 1 "уровень" выше, тоесть на предыдущую красную точку. Она дойдет начатый цикл до конца, и возвратиться еще выше. В итоге по полю будут раскиданы красные точки с максимальным расстоянием 3. Решение НЕ САМОЕ ОПТИМАЛЬНОЕ. Но из всех возможных алгоритмов самое простое.
Расписываю алгоритм по пунктам:
1) Делаем функция подсчета количества красных точек на расстояни от выбранной точки.
2) Устанавливаем где-попало в зеленом секторе красную точку.
3) Запускаем от нее рекурсивную функцию:
for все точки на радиусе N
if у текущей точки на расстоянии (N-1) красных точек нет
ставим сюда красную точку
запускаем эту функцию относительно уже этой новой красной точки
endif
endfor
Теперь как будет работать этот скрипт:
1) Точка одна которая взята случайным образом.
2) найдена точка на расстоянии N, вокруг нее только 1 точка (начальная на расстоянии N (а проверка на расстояние N-1) тоесть сюда ставим красную тоже.
Повторяем 2 для новой точки, и так далее пока вдруг не зайдем в тупик. Зайдя в тупик, функция просто переберет все точки, и возвратиться на 1 "уровень" выше, тоесть на предыдущую красную точку. Она дойдет начатый цикл до конца, и возвратиться еще выше. В итоге по полю будут раскиданы красные точки с максимальным расстоянием 3. Решение НЕ САМОЕ ОПТИМАЛЬНОЕ. Но из всех возможных алгоритмов самое простое.