IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Обход двумерной матрицы
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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

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

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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата(Сергей Меркурьев @ 5.06.2010 8:51) *
на пути могут быть преграды
Вот это - ключевой момент. Тут поподробнее, пожалуйста..
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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

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

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

Цитата
0 0 0 0 0 0 0 0 0
0 0 0 0 Б 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 * * * 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 А 0 0 0 0
0 0 0 0 0 0 0 0 0

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

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

Сообщение отредактировано: Сергей Меркурьев -


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


самое простое - идти буквой "Г" по одной клеточке по-моему. Идешь вверх (вниз) потом в сторону. Если преграда - то надо свернуть на 1 клетку. Суть вроде и так понятна, но если праграда сложная, а не как в примере, то будет посложнее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


при движении возможно только четыре варианта - вперед, назад, налево и направо smile.gif перед "развилкой" можно запомнить положение. Если прямо нельзя, то направо или налево, а если и туда нельзя - то назад. Если выбранный путь не удался (тупик, угол) то с сохраненной позиции надо идти в другую сторону.
Лучше делать это на бумаге сначала, нарисовать праграду и обойти ее. Так появится представление, как сделать программно. smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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

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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


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

Сообщение отредактировано: Client -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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

Сообщение отредактировано: Сергей Меркурьев -


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 7.06.2010 17:11) *
С графами я к сожалению, не знаком...
А вот с матрицей еще могу что-то сделать.
Не пугайся слов. Граф может выступать как представление матрицы, или наоборот. Посмотри тут: википедия, волновой алгоритм


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 8.06.2010 8:48) *
А по времени, что будет быстрее?
К примеру обычныйпоиск пути в двумерной матрице или же Ваш волновой алгоритм (или другое)? И примерно во сколько раз они будут отличаться?
Гм. Забавно ты ставишь вопрос )).

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

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

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

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

Добавлено через 6 мин.
Цитата(Сергей Меркурьев @ 8.06.2010 8:48) *
или же Ваш волновой алгоритм
чего это он мой-то? blink.gif я на него не претендую.. smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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

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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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

Добавлено через 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 килобайт ) Кол-во скачиваний: 304


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

Цитата(TarasBer @ 8.06.2010 12:22) *
ГРАФА, а не матрицы! Нету такого термина, как "обход матрицы".
Тарас, ну че пристал? это не термины, это простое словосочетание. Нет никакой разницы, как это называть (в данном случае).

Цитата
Вот пример программы (для турбопаса)
Кэштмэрррт.. shok.gif
Здравствуй, гость из прошлого! поди, посиди на лавочке...

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 5:15
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name