Версия для печати темы

Автор: Сергей Меркурьев 5.06.2010 12:51

В общем хочу написать код, который давал бы путь перехода из точки А в точку В.
На процедуру посылаются значения точек (x1,y1,x2,y2:byte).
Матрица сама по себе небольшая (не больше 15 клеток, а то и меньше). Я пытался сделать, но получились лишь куски кода, в которых я ищу где находится вторая точка относительно первой (сверху, снизу, снизу слева). А также 4 процедурки движения (если вверху точка, идем вверх).

НО! Есть небольшое "но" .
Движение нельзя совершать по диагонали. И на пути могут быть преграды. Помогите пожалуйста. Если нужно напишу то, что у меня есть.

P.S. Извиняюсь, если подобная проблема решалась раньше.

Автор: Гость 5.06.2010 13:01

Вот это - ключевой момент. Тут поподробнее, пожалуйста..

Автор: Сергей Меркурьев 5.06.2010 13:06

В общем двумерная матрица будет размером 9*9.

Приведу небольшой пример, так будет наверно легче.

В данном случае мы просто пойдем вверх по матрице. Проблем никаких не возникает.


В данном случае уже нужно обходить преграду. В том случае если выхода нет, желательно сообщить об этом.

0 - пустая клетка.
* - некая преграда.
А, Б - пункты назначения.

Автор: Сергей Меркурьев 5.06.2010 21:56

Посоветуйте что-нибудь пожалуйста

Автор: Client 6.06.2010 0:26

самое простое - идти буквой "Г" по одной клеточке по-моему. Идешь вверх (вниз) потом в сторону. Если преграда - то надо свернуть на 1 клетку. Суть вроде и так понятна, но если праграда сложная, а не как в примере, то будет посложнее.

Автор: Сергей Меркурьев 6.06.2010 0:31

Вот, что по поводу посложнее у меня и не получается придумать

Автор: Client 6.06.2010 0:38

при движении возможно только четыре варианта - вперед, назад, налево и направо перед "развилкой" можно запомнить положение. Если прямо нельзя, то направо или налево, а если и туда нельзя - то назад. Если выбранный путь не удался (тупик, угол) то с сохраненной позиции надо идти в другую сторону.
Лучше делать это на бумаге сначала, нарисовать праграду и обойти ее. Так появится представление, как сделать программно.

Автор: Сергей Меркурьев 6.06.2010 0:41

В принципе все наработки моей программы только лишь на бумаге сделаны.

Я думал по поводу сохранения позиции, но я раньше ничего подобного ни делал. Как я понимаю таких ситуаций сохранения, начиная с первого, может еще несколько штук. Как это организовать?
И еще вопрос, как лучше делать выбор хода? Желательно идти (рассматривать ходы) по часовой (против часовой) стрелки или тут это не имеет значения?

Автор: Client 6.06.2010 0:43

думаю, что сворачивать стоит в ту сторону, ближе к которой находится "пункт назначения"
а запомнить надо х и у, т.е. координаты

Автор: Сергей Меркурьев 6.06.2010 0:58

Хорошо, надо будет попробовать. Если что-то будет не получаться, спрошу.

Автор: TarasBer 7.06.2010 15:55

> самое простое - идти буквой "Г" по одной клеточке по-моему

Самое простое - применить какой-нибудь стандартный алгоритм обхода графа.

Автор: Сергей Меркурьев 7.06.2010 20:04

А причем тут графы?

Автор: TarasBer 7.06.2010 20:09

А причём тут матрицы?
В условии задан лабиринт. А лабиринт - это частный случай графа. Вершины - свободные клетки, а рёбра есть между вершинами, соответствующими соседним клеткам.

Автор: Сергей Меркурьев 7.06.2010 20:11

С графами я к сожалению, не знаком...
А вот с матрицей еще могу что-то сделать.

Автор: Lapp 8.06.2010 3:52

Не пугайся слов. Граф может выступать как представление матрицы, или наоборот. Посмотри тут: http://ru.wikipedia.org/wiki/%D0%92%D0%BE%D0%BB%D0%BD%D0%BE%D0%B2%D0%BE%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

Автор: Сергей Меркурьев 8.06.2010 11:48

А по времени, что будет быстрее?
К примеру обычныйпоиск пути в двумерной матрице или же Ваш волновой алгоритм (или другое)? И примерно во сколько раз они будут отличаться?

Автор: Lapp 8.06.2010 12:54

Гм. Забавно ты ставишь вопрос )).

Что быстрее: использовать правило одной руки в лабиринте - или сразу пройти к выходу?
Что быстрее: ходить в школу и делать домашние задания в течение десяти лет - или сразу стать умным и сдать ЕГЭ?
Что быстрее было Александру Сергеевичу: трястись в бричке перу дней - или сесть на вертолет и сразу махнуть к себе в Михайловское из Питера?
Что быстрее: лететь на Аполло-13 на Луну - или прорыть туда подземный ход?

Если ты знаешь КАК сделать то, что стоит в каждом предложении после тире - я умолкаю и снимаю шляпу.

Волновой алгоритм - это ПРИНЦИПИАЛЬНАЯ возможность найти (короткий) путь. Никакого "обычного поиска пути в двумерной маотрице" я НЕ ЗНАЮ. Соответственно, я не могу ответить на вопрос, что быстрее..

Я подозреваю, что тебя сбивает с толку то, что ты знаешь какие-то дополнительные условия, которые не назвал нам - малая плотность препятствий, ограничение размера и формы препятствий.. Такое знание МОЖЕТ помочь, но может и подвести. Либо (что скорее) ты просто не вник достаточно глубоко в суть своего же вопроса )).

Добавлено через 6 мин.
чего это он мой-то? я на него не претендую..

Автор: Сергей Меркурьев 8.06.2010 15:08

По сути дела препятсвия могут быть в любой клетке, могут вообще полностью заполонена таблица ими.
Ограничения есть, но это только лишь размер двумерной матрицы - 9х9 клеток.
Также то, что ходить нельзя по диагонали и все.

P.S. Вообще я задумал написать игру на Delphi. Игра Lines (может быть слышали). У меня практически все есть, кроме алгоритма обхода матрицы.

Автор: TarasBer 8.06.2010 15:22

> кроме алгоритма обхода матрицы.

ГРАФА, а не матрицы! Нету такого термина, как "обход матрицы".

Добавлено через 13 мин.
Вот пример программы (для турбопаса), которая сама с собой играет в Пакмана. Писал для себя, но основные мозги участников в этом месте:

      Push(x1);
      Push(y1);
      while B <> E do begin
        Pop(x);
        Pop(y);
        for i := 0 to 3 do with F.Items[y+dy[d[i]], x+dx[d[i]]] do if Value = 3 then begin
          Value := 0;
          Push(x+dx[d[i]]);
          Push(y+dy[d[i]]);
        end;
      end;

Гопник (жёлтый) движется к жёлтой фигне, выбирая путь, свободный от ментов (голубые), при этом забавно мечется (потому и вызвал ассоциации с гопником). Менты движутся к гопнику, выбирая путь,свободный от других ментов (ну чтобы окружать гопника).
Мышкой можно переставить цель гопника и перевести его обратно на автоуправление (стрелочками можно самому управлять гопником, но лучше не надо). Константа MCount задаёт кол-во ментов, MSpeed - их скорость относительно скорости гопника.


Прикрепленные файлы
 LAB.PAS ( 11.71 килобайт ) Кол-во скачиваний: 309

Автор: Lapp 9.06.2010 7:13

Слышали )).
Алгоритм обхода в этой игре составляет одну из основных частей. Помню, я писал когда-то Xonix (про нее вряд ли кто слышал, ее забыли, а зря..), и это был мой первый опыт с персоналками вообще (Электроника НЦ-80, кажется - копия DEC Pro 350, 8 бит, 512К, HD 5 MB, ОS RSX-11). Писалось на Basic'е. Когда отрезался кусок площади и шла проверка на связность - можно было смело идти пить чай )). Крайне неудачно сделал (некоей псевдо-рекурсией), можно было сильно ускорить.. но работало! ))

Сергей, не мучайся: просто гони волну (типо каламбур)). Это в твоем случае самое лучшее. Волновой алгоритм очень прост в реализации и работать будет как из пушки. Если что-то непонятно - пиши, поможем.

Тарас, ну че пристал? это не термины, это простое словосочетание. Нет никакой разницы, как это называть (в данном случае).

Кэштмэрррт..
Здравствуй, гость из прошлого! поди, посиди на лавочке...

Где мне ее запущать прикажешь??

Автор: TarasBer 9.06.2010 13:30

> Кэштмэрррт..
Здравствуй, гость из прошлого! поди, посиди на лавочке...
Где мне ее запущать прикажешь??

Не понял, Виста опять на что-то ругается? Ну тогда ДосБокс...