0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
||||||
1 | ||||||
Отсортировать массив, который ищет самый короткий путь до точки30.11.2018, 04:37. Показов 2858. Ответов 23
Метки нет (Все метки)
Дорогие форумчане, прошу вашей помощи.
Пытаюсь написать алгоритм для монстра в игре. Алгоритм высчитывает самый короткий путь до игрока. Алгоритм нашел (называется волновой Алгоритм более подробно тут http://pestantium.blogspot.com... -post.html), подстроил под себя, написал, но столкнулся с проблемой. На выходе Алгоритм выдает мне двумерный массив интов, в котором кратчайший путь от одной точки до другой представлен последовательностью цифр от 0 до n, где n это максимальное кол-во ходов которое сделает точка (монстр в последствии), что бы добраться до конечной точки (игрока в последствии). Проблема такая, алгоритм высчитывает все возможные ходы, и "пачкает" этот двумерный массив ненужными ходами. Более наглядно, на скрине. Мне нужно вместо мусора поставить те же значения как и у стен (-2), но никак не могу сообразить как же мне это сделать. Может кол-во тем, которые я прошел не позволяют догадаться, может сам не могу догнать, хз) Прошу наведите на мысль. приложу так же код: Кликните здесь для просмотра всего текста
0
|
30.11.2018, 04:37 | |
Ответы с готовыми решениями:
23
Выбрать самый короткий путь в задаче о шахматах Найти самый длинный и самый короткий отрезок Найти самый короткий путь от точки до точки в матрице Самый короткий путь алгоритм Флойда |
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 05:00 | 2 |
а как вы узнаете, что элементы массива синего цвета являются кратчайшим путём?
судя по массиву - у вас просто отработанный алгоритм, который дал вам расчеты, а вот выбор кратчайшего (и возможность достижения игрока) это уже ваша задача. как вариант - отталкиваться от положения игрока, там вы имеете самое короткое значение, то есть 15, берём вокруг и ищем 14 и так до конца, везде, где встречаем еще одно (или несколько) совпадающее значение (например 14 будет снизу и справа) - все кроме одного из значений заменяем на -2. Еще можно расширить заполнение числом -2 так - ставить его везде где значение вокруг рассматриваемой позиции больше или равно, исключая путь маршрута, который вы ежу прошли. Но в таком случае есть ограничение - обязательно должны быть стены вокруг, то есть маршрут не должен делать петли соприкасаясь с ранее пройденным участком (в целом этого не должно происходить, так как точка соприкосновения даст априори более короткий маршрут). Если написал сумбурно и задавайте вопросы, я постараюсь написать что-то конкретное.
1
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 05:08 | 3 |
Если я правильно вас понял, то мой вариант выдаст такой результат.
1
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
30.11.2018, 05:25 [ТС] | 4 |
Последовательность, которая идет от 0 до n(15 в этом случае) и будет являться самым коротким путем.В этом и есть суть Алгоритма
Да, это именно так, он дал мне расчеты, про возможность достижения, это уже потом, сейчас мне нужно привести этот массив в вид, который у вас снизу на скрине, что бы в дальшейшем я уже отталкивался от массива в котором просто проложен самый короткий путь.
Тоже про это думал, но как именно выбрать именно ТО значение. В голову приходила мысль о том чтобы проверить, допустим 2 последующие клетки, так чтобы было в нижней/верхней/правой/левой 14, и если в следующей нвпл 13 то тогда уже удалять, но уверен есть решение проще, да и если стоит игрок у края, то там выход за границы пойдет при проверке, придется условий много писать... Добавлено через 5 минут UPD: В теории я хочу реализовать это так. У меня есть массив с самым коротким путем. Я подсовываю этот массив монстру, там он будет стоять в координатах со значением 0. Затем идет проверка, какая координата является значением 1, туда и идет монстр. Затем цикл повторяется, массив обновляется и все происходит заново. Но это в теории
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 05:29 | 5 |
это как раз понятно, я говорю о вашей программе, смотреть глазами человека и обводить синим - компьютер ещё нужно научить.
после такого просто теряется интерес к теме. я вам дал всю информацию для реализации, код напишите самостоятельно с аж кучей условий (вам бы на ассемблере попрограммировать немножко, чтобы понять как всё работает и почему у вас там почти постоянно будет CMP, JZ и т.п.)
0
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
30.11.2018, 05:42 [ТС] | 6 |
После такого, как я понял, это написанное мной "придется условий много писать..."
Вы подумали как это будет выглядеть в коде? Сколько это займет строк? 50? 100? Я сейчас имею ввиду кол-во всех проверок, ведь там 4 возможных направления, а за каждым еще как максимум 3, т.е в худшем случае 12. 12 проверок, не считая условий выхода за границы массива. Такое решение я написать смогу. Но тему я создал для того, что бы мой код не был похож на один большой костыль, посмотрев на который через неделю я едва пойму что там происходит(в коде). В общем .
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
||||||
30.11.2018, 05:57 | 7 | |||||
именно поэтому я первым задал этот вопрос. Если у вас голый массив и нет НИКАКОЙ информации об этом оптимальном маршруте, то вам всё равно придётся идти по массиву и проверять.
Сначала пишется код, проверяется его работа, а потом вы его оптимизируете, вплоть до полной переделки. Позавчера я написал вот такое:
Через пару часов буду посвободнее - напишу вашу реализацию, а вы потом напишете свою или кто-то еще напишет, может узнаю что-то новое.
0
|
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
|
|
30.11.2018, 06:11 | 8 |
В общем насколько понимаю волны надо пускать одновременно из стартового положения и из конечного и двигать их синхронно отслеживая факт встречи. Тот маршрут при котором n в точке встречи будет наименьшим и будет кратчайшим. т.е. трассируется обратно от наименьшего n.
Добавлено через 1 минуту кроме здраваго смысла. Добавлено через 6 минут lexatorgas, В принципе и по вашему массиву можно пройти по кратчайшему пути от конечного положения в начальное выбирая на каждом шаге клетку с минимальным неотрицательным значением. Но и таких путей в принципе может оказаться несколько .
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 06:12 | 9 |
зачем если кратчайший путь уже построен?
предложите ваш здравомыслящий вариант.
0
|
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
|
|
30.11.2018, 06:15 | 10 |
ТАк его еще найти надо какой из них кратчайший.
Добавлено через 1 минуту От конечного назад выбирая наименьшего соседа. Ну при этом как бы гнать исходную волну в двух направлениях оптимальней чем в одном.
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 06:17 | 11 |
тот, что оканчивается в точке игрока, массив - это и есть УЖЕ найденное решение. Топикстартер не просит нас искать кратчайший путь, он просит лаконично избавиться от ошибочных веток прохода алгоритма поиска.
Как я сразу и написал - путь от игрока к монстру однозначно проводит нас по кратчайшему маршруту (если маршрутов несколько, то выбираем любой).
0
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
30.11.2018, 06:19 [ТС] | 12 |
Но ведь в этом случаем волны будут так-же как и в моем алгоритме пускаться во все стороны, и "подтирать" за ними никто не будет (удалять ненужные маршруты, которые не оказались самыми короткими).
Моя задача на данный момент и есть "подтереть" массив, оставив в нем только самый короткий путь. А остальное уставить условными стенками. Нужно как то обьяснить компу, что вот этот путь и есть самый короткий, и все другие бессмысленны, поэтому поставь там везде стены.
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 06:19 | 13 |
Вы сейчас о чем? Вам не понравились мои if, причем тут какие-то волны?
Гнать волну от монстра не имеет смысла, так как от него расходятся ложные маршруты - вы будете выполнять лишний код.
0
|
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
|
|
30.11.2018, 06:25 | 14 |
Сообщение было отмечено lexatorgas как решение
Решение
Нинада ниче подтирать. мы проставили количество шагов которое нужно пройти от старта до финиша. теперь от финиша идем обратно к старту выбирая клетку из которой до финиша количество шагов минимальное (в ней записанное) и так приходим на старт кратчайшим путем. А при встречной трассировке выбирая точку встречи с минимальным n мы опять же получаем точку на кратчайшем пути откуда трассируем маршрут обратно в обе стороны.
Суть алгоритма - прямой ход (волна) определяет возможные пути и их длины. Обратный ход находит кратчайший из возможных.
1
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 06:34 | 15 |
кстати да, автор, а какая цель то у вас? наличие расставленных -2 ровным счётом ничего не даст.
0
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
30.11.2018, 06:34 [ТС] | 16 |
Попробую сейчас так:
Создать новый такой же массив из столько условных стенок. Вывести максимальное значение в первом массиве (оно и будет положением игрока) и присвоить этим же коодинатам нового массива максимальное значение. Затем в первом массиве проверять 4 стороны на значение (макс-1 и макс=макс-1) и т.д Так же поэтапно присваивать новому массиву все значения.
0
|
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
|
|
30.11.2018, 06:34 | 17 |
т.е. на обратном ходу пишем цепочку найденных координат в обычный одномерный массивчик, потом реверсим. Ну а можно сам алгоритм развернуть - т.е. пускать волну из конечной точки а не из начальной, чтобы массив лишний раз не разворачивать.
0
|
0 / 0 / 0
Регистрация: 25.06.2017
Сообщений: 60
|
|
30.11.2018, 06:35 [ТС] | 18 |
0
|
2063 / 1542 / 168
Регистрация: 14.12.2014
Сообщений: 13,402
|
|
30.11.2018, 06:39 | 19 |
Задача получить не 2D массив с пометками а цепочку координат (ну или смещений, хотя координат для автопилота пропорциональной навигации удобнее), последовательно пройдя по которым окажемся в заданной точке.
0
|
-338 / 245 / 26
Регистрация: 01.06.2018
Сообщений: 3,137
|
|
30.11.2018, 06:40 | 20 |
Fulcrum_013 дал отличный совет по поводу запуска волны от игрока, тогда монстр всегда ходит на клетку где шаг меньше на 1. Имхо это проще и быстрее чем считать в массив координаты маршрута, которые живут только одну итерацию.
0
|
30.11.2018, 06:40 | |
30.11.2018, 06:40 | |
Помогаю со студенческими работами здесь
20
Лабиринт, найти самый короткий путь Лабиринт. Найти самый короткий путь от входа в выходу Найти самый короткий путь от левого столбца массива к правому Определить самый короткий путь между точками на поле с препятствиями Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |