|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
||||||
Отсортировать массив, который ищет самый короткий путь до точки30.11.2018, 04:37. Показов 3466. Ответов 23
Метки нет (Все метки)
Дорогие форумчане, прошу вашей помощи.
Пытаюсь написать алгоритм для монстра в игре. Алгоритм высчитывает самый короткий путь до игрока. Алгоритм нашел (называется волновой Алгоритм более подробно тут http://pestantium.blogspot.com... -post.html), подстроил под себя, написал, но столкнулся с проблемой. На выходе Алгоритм выдает мне двумерный массив интов, в котором кратчайший путь от одной точки до другой представлен последовательностью цифр от 0 до n, где n это максимальное кол-во ходов которое сделает точка (монстр в последствии), что бы добраться до конечной точки (игрока в последствии). Проблема такая, алгоритм высчитывает все возможные ходы, и "пачкает" этот двумерный массив ненужными ходами. Более наглядно, на скрине. Мне нужно вместо мусора поставить те же значения как и у стен (-2), но никак не могу сообразить как же мне это сделать. Может кол-во тем, которые я прошел не позволяют догадаться, может сам не могу догнать, хз) Прошу наведите на мысль. приложу так же код: Кликните здесь для просмотра всего текста
0
|
||||||
| 30.11.2018, 04:37 | |
|
Ответы с готовыми решениями:
23
Выбрать самый короткий путь в задаче о шахматах
Найти самый короткий путь от точки до точки в матрице |
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
|
| 30.11.2018, 05:00 | |
|
а как вы узнаете, что элементы массива синего цвета являются кратчайшим путём?
судя по массиву - у вас просто отработанный алгоритм, который дал вам расчеты, а вот выбор кратчайшего (и возможность достижения игрока) это уже ваша задача. как вариант - отталкиваться от положения игрока, там вы имеете самое короткое значение, то есть 15, берём вокруг и ищем 14 и так до конца, везде, где встречаем еще одно (или несколько) совпадающее значение (например 14 будет снизу и справа) - все кроме одного из значений заменяем на -2. Еще можно расширить заполнение числом -2 так - ставить его везде где значение вокруг рассматриваемой позиции больше или равно, исключая путь маршрута, который вы ежу прошли. Но в таком случае есть ограничение - обязательно должны быть стены вокруг, то есть маршрут не должен делать петли соприкасаясь с ранее пройденным участком (в целом этого не должно происходить, так как точка соприкосновения даст априори более короткий маршрут). Если написал сумбурно и задавайте вопросы, я постараюсь написать что-то конкретное.
1
|
|
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
|
| 30.11.2018, 05:08 | |
|
Если я правильно вас понял, то мой вариант выдаст такой результат.
1
|
|
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
||||
| 30.11.2018, 05:25 [ТС] | ||||
|
Добавлено через 5 минут UPD: В теории я хочу реализовать это так. У меня есть массив с самым коротким путем. Я подсовываю этот массив монстру, там он будет стоять в координатах со значением 0. Затем идет проверка, какая координата является значением 1, туда и идет монстр. Затем цикл повторяется, массив обновляется и все происходит заново. Но это в теории
0
|
||||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
|||
| 30.11.2018, 05:29 | |||
|
я вам дал всю информацию для реализации, код напишите самостоятельно с аж кучей условий (вам бы на ассемблере попрограммировать немножко, чтобы понять как всё работает и почему у вас там почти постоянно будет CMP, JZ и т.п.)
0
|
|||
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|||
| 30.11.2018, 05:42 [ТС] | |||
|
Вы подумали как это будет выглядеть в коде? Сколько это займет строк? 50? 100? Я сейчас имею ввиду кол-во всех проверок, ведь там 4 возможных направления, а за каждым еще как максимум 3, т.е в худшем случае 12. 12 проверок, не считая условий выхода за границы массива. Такое решение я написать смогу. Но тему я создал для того, что бы мой код не был похож на один большой костыль, посмотрев на который через неделю я едва пойму что там происходит(в коде). В общем
0
|
|||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
||||||||
| 30.11.2018, 05:57 | ||||||||
Через пару часов буду посвободнее - напишу вашу реализацию, а вы потом напишете свою или кто-то еще напишет, может узнаю что-то новое.
0
|
||||||||
|
2083 / 1574 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
|||
| 30.11.2018, 06:11 | |||
|
Добавлено через 1 минуту Добавлено через 6 минут lexatorgas, В принципе и по вашему массиву можно пройти по кратчайшему пути от конечного положения в начальное выбирая на каждом шаге клетку с минимальным неотрицательным значением. Но и таких путей в принципе может оказаться несколько .
0
|
|||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
|||
| 30.11.2018, 06:12 | |||
|
0
|
|||
|
2083 / 1574 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
|||
| 30.11.2018, 06:15 | |||
|
Добавлено через 1 минуту
0
|
|||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
||
| 30.11.2018, 06:17 | ||
|
Как я сразу и написал - путь от игрока к монстру однозначно проводит нас по кратчайшему маршруту (если маршрутов несколько, то выбираем любой).
0
|
||
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
||
| 30.11.2018, 06:19 [ТС] | ||
|
Моя задача на данный момент и есть "подтереть" массив, оставив в нем только самый короткий путь. А остальное уставить условными стенками. Нужно как то обьяснить компу, что вот этот путь и есть самый короткий, и все другие бессмысленны, поэтому поставь там везде стены.
0
|
||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
||
| 30.11.2018, 06:19 | ||
|
Гнать волну от монстра не имеет смысла, так как от него расходятся ложные маршруты - вы будете выполнять лишний код.
0
|
||
|
2083 / 1574 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
||
| 30.11.2018, 06:25 | ||
Сообщение было отмечено lexatorgas как решение
РешениеСуть алгоритма - прямой ход (волна) определяет возможные пути и их длины. Обратный ход находит кратчайший из возможных.
1
|
||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
||
| 30.11.2018, 06:34 | ||
|
0
|
||
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
||
| 30.11.2018, 06:34 [ТС] | ||
|
Создать новый такой же массив из столько условных стенок. Вывести максимальное значение в первом массиве (оно и будет положением игрока) и присвоить этим же коодинатам нового массива максимальное значение. Затем в первом массиве проверять 4 стороны на значение (макс-1 и макс=макс-1) и т.д Так же поэтапно присваивать новому массиву все значения.
0
|
||
|
2083 / 1574 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
|
| 30.11.2018, 06:34 | |
|
т.е. на обратном ходу пишем цепочку найденных координат в обычный одномерный массивчик, потом реверсим. Ну а можно сам алгоритм развернуть - т.е. пускать волну из конечной точки а не из начальной, чтобы массив лишний раз не разворачивать.
0
|
|
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
| 30.11.2018, 06:35 [ТС] | |
|
0
|
|
|
2083 / 1574 / 169
Регистрация: 14.12.2014
Сообщений: 13,614
|
||
| 30.11.2018, 06:39 | ||
|
0
|
||
|
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
|
||
| 30.11.2018, 06:40 | ||
|
0
|
||
| 30.11.2018, 06:40 | |
|
Помогаю со студенческими работами здесь
20
Лабиринт, найти самый короткий путь Лабиринт. Найти самый короткий путь от входа в выходу Найти самый короткий путь от левого столбца массива к правому
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение.
И на уровне агентов добавится между грибами или бактериями взаимодействий.
До того я пробовал подход через многомерные массивы,. . .
|
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Сочетание глобально распределённой вычислительной мощности и инновационных. . .
|
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Налог на собак: https:/ / **********/ gallery/ V06K53e
Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf
Пост отсюда. . .
|
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop?
Ниже её машинный перевод.
После долгих разбирательств я наконец-то вернула себе. . .
|
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод
Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод.
Thinkpad X220 Tablet —. . .
|
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|