|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
11.10.2005, 23:35
|
#1
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Короче вот такая задача передомной стоит еще с лета :
Есть двумерная матрица состоящая из "ноликов" и "единичек", нолик - пустое пространство, единичка - проепятствие (на рисунке голубой и черный квадратики соответственно). В матрице находится игрок, который смотрит в одну из четырех сторон (вверх, вправо, вниз, влево), неважно в какую. Игрок должен иметь обзор с углом 90 (А) или 120 (В) градусов, это тоже нестоль важно. Основная задача состоит в том, чтобы определить виден-ли тот или иной сегмент матрицы примерно как показано на рис. С.
Я не прошу написать этот алгоритм (хотя если напишите я буду благодарен вдвойне), а просто направить мои мысли по этому поводу в нужнуб сторону
Заранее спасибо всем кто откликнится!
|
(Offline)
|
|
11.10.2005, 23:53
|
#2
|
Администратор
Регистрация: 03.09.2005
Сообщений: 2,408
Написано 301 полезных сообщений (для 996 пользователей)
|
хмммм, интересная задача...
я бы сделал так:
очертил бы окружность (или сегмент окружности... видимыйсегмент = началосегмента=уголигрока-полезрения/2 конецсегмента=уголигрока+полезрения/2) вокруг игрока с радиусом поля зрения, и с шагом примерно в половину клетки (можно в четверть)...
от игрока проводил бы по очереди к каждой точке окружности линию* и если, при рисовании линии, в очередной точке встретился объект, то заносил бы его в массив видимых объектов (ессно сначала проверять нужно есть ли он там уже)... потом у тя получается то, что игрок видит
* - линию рисуем следующим образом:
берем разницу координат (х начала - х конца) и делим на два радиуса поля зрения (для точности можно больше) результат получим дельтаХ... точно так-же и про Y
далее берем и пускаем цикл от одного до 2радиуса (или сколько взяли при делении разницы координат) и к Х игрока прибавляем дельтаХ (Y тоже), смотрим есть ли в этой точке объект... и так до конца цикла
__________________
Как минимум я помог многим (с)
|
(Offline)
|
|
11.10.2005, 23:59
|
#3
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Угу. Вот только подавление ошибок, вызванных дискретностью модели мира, путём калиброки коэффициентов заведомо меньших - настораживает. В общем надо закодировать: если не заработает - определить почему и усовершенствоать алгоритм.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
11.10.2005, 23:59
|
#4
|
Администратор
Регистрация: 03.09.2005
Сообщений: 2,408
Написано 301 полезных сообщений (для 996 пользователей)
|
и конечно игра коэффициентов надо их будет правильно подобрать, чтоб через клетку не перескакивали и чтоб лишних проверок небыло, и шаг в черчении окружность надо брать максимально большим пока через клетку прыгать не начнем...
__________________
Как минимум я помог многим (с)
|
(Offline)
|
|
12.10.2005, 00:09
|
#5
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Вообще я хотел бы решить эту проблему оперируя только с матрицей... Основная проблема в том, что если использовать такую методику как ты приводишь, то на определение видимости уйдет значительное количество процессорного времени.
Да и к тому же мне особо не нужна такая точность определения видимости... главное чтобы алгоритм работал приблизительно так как мне хочется.
Но все равно спасибо за совет.
|
(Offline)
|
|
12.10.2005, 01:14
|
#6
|
Администратор
Регистрация: 03.09.2005
Сообщений: 2,408
Написано 301 полезных сообщений (для 996 пользователей)
|
ну, другого метода я не знаю... погоди, спать буду ложиться перед сном подумаю... мож еще чего в голову прийдет..
__________________
Как минимум я помог многим (с)
|
(Offline)
|
|
12.10.2005, 08:48
|
#7
|
|
я неучюсь в инсте а только еще в лицее
предлагаю так
вообщем клепаеш примитивный алгоритм рисования линии чтобы точки получить
и рисуеш круг по линейно c радиусом x
обект первый натолкнувшися на линию (или линия на него) и будет видет
все остальные - невидны
|
|
|
12.10.2005, 09:53
|
#8
|
|
Можно привести такой пример работы с матрицей:
Матрица - это ведь массив.
Определяешь, в какую сторону смотрит игрок; циклом перебираешь только те клетки, которые попадают в зону видимости (причем перебирать нужно от того места, где стоит игрок, а не все время сверху вниз или снизу вверх).
Если в цикле натыкаешься на клетку с препятствием, объекты за этим препятствием делаешь невидимыми за несложным алгоритмом:
сторон поворота четыре, поэтому достаточно проверять счетчики массива (если счетчик подошел к краю поля зрения, то невидимые клетки будут смещены относительно препятствия, как это хорошо видно на рисунке).
|
|
|
12.10.2005, 22:00
|
#9
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Впринципе у меня есть задумка алгоритма, который будет работать как смесь предложенных вами технологий определений видимости.
Вобщем попробую сделать так:
- буду проводить виртуальные линии с шагом в одну клетку (точнее с шагом в один элемент матрицы) по той оси в которую смотрит игрок;
- линий будет столько, сколько клеток ограничивают область обзора (на границе области).
Займусь его реализацией наверно на этих выходных, когда времени будет побольше.
Спасибо всем за помощь
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 07:59.
|