|
Поиск пути
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 14:22 | Сообщение # 1 |
почетный гость
Сейчас нет на сайте
| Всем привет! 
Делаю пошаговую стратегию, неожиданно возникла потребность в создании поиска пути по массиву с рандомными числами. Вот я думаю, и никак не пойму, как же мне сделать, чтобы путь проходил через более выгодные ячейки массива(с наименьшими значениями) к заданной цели.
Подскажите пожалуйста, как это можно осуществить? У кого какие соображения на этот счёт, может у кого какой-либо пример есть?
GMS MC
Сообщение отредактировал cosferaps - Понедельник, 13 Августа 2012, 14:23 |
|
|
| |
| Ретсамолф | Дата: Понедельник, 13 Августа 2012, 14:37 | Сообщение # 2 |
постоянный участник
Сейчас нет на сайте
| Серафим, ты?
Сообщение отредактировал Ретсамолф - Понедельник, 13 Августа 2012, 14:38 |
|
|
| |
| sk0rpi0n | Дата: Понедельник, 13 Августа 2012, 15:01 | Сообщение # 3 |
Tiberium
Сейчас нет на сайте
| Предложу свой кривой вариант: ищем в восьми клетках вокруг игрока наименьшие число и перемещаемся в ту клетку, опять повторяем, и опять, и опять...
Adventures of the Purple Ball - готов.
Wanderer - готов.
|
|
|
| |
| GameMix | Дата: Понедельник, 13 Августа 2012, 15:22 | Сообщение # 4 |
старожил
Сейчас нет на сайте
| sk0rpi0n, минус в твоем варианте в том, что из невыгодной первой точки, может выходить куча вторых точек, выгоднее, чем вторые точки первой выгодной точки 
В первую синюю клетку шагать невыгодно, зато в следующие синие выгоднее, чем в красные. Поэтому нужно все точки перебирать от начала пути до конца.
Steel Standoff - 2D аркада.
Мои статьи
|
|
|
| |
| RUNGOGET2THECHOPAH | Дата: Понедельник, 13 Августа 2012, 15:32 | Сообщение # 5 |
участник
Сейчас нет на сайте
| Есть куча алгоритмов поиска пути. Алгоритм Дейкстры, например.
|
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 16:20 | Сообщение # 6 |
|
почетный гость
Сейчас нет на сайте
| sk0rpi0n, представь себе такой вариант  тогда что?
Алгоритм дейкстры здесь неуместен вообще
GMS MC
Сообщение отредактировал cosferaps - Понедельник, 13 Августа 2012, 16:33 |
|
|
| |
| GameMix | Дата: Понедельник, 13 Августа 2012, 16:24 | Сообщение # 7 |
|
старожил
Сейчас нет на сайте
| Quote (cosferaps) Алгоритм дейкстры здесь неуместен вообще
Почему же? Он вычисляет стоимость каждого из возможных путей.
Steel Standoff - 2D аркада.
Мои статьи
|
|
|
| |
| RUNGOGET2THECHOPAH | Дата: Понедельник, 13 Августа 2012, 16:33 | Сообщение # 8 |
|
участник
Сейчас нет на сайте
| Ну да, составить граф из двумерного массива - неразрешимая задача.
|
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 16:35 | Сообщение # 9 |
|
почетный гость
Сейчас нет на сайте
| GameMix, хотя ещё поискал нашёл заметки, что он весьма эффективен, но примера с клетчатыми полями не нашёл, а графы нафиг не сдалисьQuote (RUNGOGET2THECHOPAH) Ну да, составить граф из двумерного массива - неразрешимая задача.
GMS MC
|
|
|
| |
| GameMix | Дата: Понедельник, 13 Августа 2012, 16:37 | Сообщение # 10 |
|
старожил
Сейчас нет на сайте
| cosferaps, зачем тебе массив со смещением?
Вот, тот самый алгоритм, изображенный на клеточном поле:
Steel Standoff - 2D аркада.
Мои статьи
Сообщение отредактировал GameMix - Понедельник, 13 Августа 2012, 16:38 |
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 16:43 | Сообщение # 11 |
|
почетный гость
Сейчас нет на сайте
| GameMix, спасибо ну изобразить и я могу, а вот с реализацией как быть. Я когда по волновому искал, там вообще всё просто, записывал координаты в другой массив и путь из них составлял потом. А тут, как сравнить всё это нагромождение, и нужное в конце выявить?
GMS MC
|
|
|
| |
| GameMix | Дата: Понедельник, 13 Августа 2012, 16:45 | Сообщение # 12 |
|
старожил
Сейчас нет на сайте
| cosferaps, попытаюсь реализовать, самому интересно
Steel Standoff - 2D аркада.
Мои статьи
|
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 16:45 | Сообщение # 13 |
|
почетный гость
Сейчас нет на сайте
| GameMix, смещение, потому что поле из гексов
GMS MC
|
|
|
| |
| RUNGOGET2THECHOPAH | Дата: Понедельник, 13 Августа 2012, 16:52 | Сообщение # 14 |
|
участник
Сейчас нет на сайте
| Самый простой способ составить граф на основе массива - это реализовать матрицу смежности. Вот тут http://habrahabr.ru/post/111361/ все подробно расписано (в том числе и как найти сам путь, а не только его длину).
|
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 17:31 | Сообщение # 15 |
|
почетный гость
Сейчас нет на сайте
| RUNGOGET2THECHOPAH, я не понимаю этого  Скорее вопрос: как массив в графы переделать. Я так-то совсем не математик, да ещё и с температурой нужно что-то попонятнее
GMS MC
|
|
|
| |
| RUNGOGET2THECHOPAH | Дата: Понедельник, 13 Августа 2012, 17:48 | Сообщение # 16 |
|
участник
Сейчас нет на сайте
| cosferaps, вкратце:
Есть двумерный массив размера n на m. Элементы массива - числа. Пронумеруем каким-нибудь образом все элементы. Тогда матрица смежности соответствующего этому массиву графа - двумерный массив размера n*m на n*m (т.е. количество строк/столбцов равно количеству элементов массива (или, что то же самое, количеству вершин графа) ). Элементы этой матрицы - цены перехода из одной смежной вершины к другой (смежные вершины - вершины, соединенные ребром в графе). Например, число 5, стоящее на позиции [6][7] в матрице означает, что цена перехода из вершины 6 в вершину 7 равна 5 (в твоей исходной матрице этому соответствует пятерка, стоящая на седьмой позиции). Если вершины не смежны (одна из вершин соответствует препятствию или вершины просто не являются соседними на твоей карте), то ставишь вместо цены какое-нибудь большое число (например, сумма всех цен, умноженная на два), которое в алгоритме называют бесконечностью. На позициях типа [1][1], [2][2], ... ставишь нули, поскольку переход из вершины в саму себя ничего не стоит. Вот вроде и все.
upd:
Ах да, забыл сказать. Алгоритм Дейкстры работает только если все числа в массиве неотрицательные.
Сообщение отредактировал RUNGOGET2THECHOPAH - Понедельник, 13 Августа 2012, 17:51 |
|
|
| |
| cosferaps | Дата: Понедельник, 13 Августа 2012, 20:16 | Сообщение # 17 |
|
почетный гость
Сейчас нет на сайте
| RUNGOGET2THECHOPAH, то есть у нас получается массив массивов что-ли ? или как? Или массив с рамками по бокам. Нет наглядного примера, что было и что получилось?
GMS MC
|
|
|
| |
| Gavolot | Дата: Понедельник, 13 Августа 2012, 20:21 | Сообщение # 18 |
Последователь Тени
Сейчас нет на сайте
| Да вроде же если поискать по мизистику можно найти реализованный A*
В общем что-то делаю, но пока не пойму ни как :)
Тень - выражение основной сущности человека.
|
|
|
| |
| cosferaps | Дата: Среда, 15 Августа 2012, 00:54 | Сообщение # 19 |
|
почетный гость
Сейчас нет на сайте
| Gavolot, я нашёл, но разобраться не получилось, слишком там много всего Добавлено (15.08.2012, 00:54)
---------------------------------------------
Есть ещё какие-нибудь идеи?
Или хотя бы пример реализации этого дейкстра на гамаке?
GMS MC
|
|
|
| |
| Maxaon | Дата: Четверг, 16 Августа 2012, 23:30 | Сообщение # 20 |
участник
Сейчас нет на сайте
| Ну так логично.
1.выделяешь массив и заполняешь случайными числами
2.задаешь цикл проверки ячеек
3.суммируешь значения какого-либо варианта
4.сравниваешь с остальными вариантами
5.выводишь самое минимальное
Добавлено (16.08.2012, 23:30)
---------------------------------------------
Это теория. На практике же дело стоит иначе(для меня по крайней мере )
Есть два решения:
1.Самый простой: считать по ходу следования т.е.
допустим есть стартовая ячейка(имеется ввиду двумерный массив) содержащая какоето значение.
делаем цикл проверяющий ячейки стоящие близ ее на значения
когда проверили, тогда начинаем сравнивать полученные значения
на поиск минимального из них
допустим нашли, дальше также делаем цикл проверки, только уже относительно новой ячейки
Здесь, если подумать, есть некоторые нюансы. Вот те из них о которых я догодался пока я это писал:
1)допустим возникнет случай когда ячейки содержат большее значение, чем та откуда ты "пришел"
здесь по логике произойдет переход назад и поэтому стоит делать доп. проверку(допустим можно запомнить, ту клетку от которой ты пришел и больше на нее не ходить )
2)необходимо заранее задать направление следования(чтобы знать куда идти, но это не проблема)
3)это не совсем правильный вариант поэтому см. ниже
2.Можно сделать как вариант 1 только работающий несколько по другому принципу(и он долгий и сложный и затратный)
Если посмотерть на т.Графов , то можно сделать что то подобное
Допустим, сделать полную проверку(просто Гигансткую проверку... да просто Армагедноскую проверщину).
Т.е. выходит, что это как бэ множество во множестве, содержащее множество, в свою очередь это множиство содержит другое множество и т.д. вариантов. По ходу проверки, надо выд. память куда записывать результаты сумм значений.
И в конце концов сделать последний цикл проверки на наличие минимального значения
да и тут тоже есть нюансы
Сообщение отредактировал Maxaon - Четверг, 16 Августа 2012, 23:32 |
|
|
| |
|
