Поиск кратчайшего пути в лабиринте 2 (стр. 2 из 2)
wr.Right:=cx+w;
wr.Top:=cy-h;
wr.Bottom:=cy+h;
mC.Brush.Color:=RGB(0,255,255);
mC.Pen.Width:=3;
mC.Pen.Color:=RGB(0,0,0);
mC.Arc(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);
k:=md.zEnd;
x:=k+1;
ir:=(x-1) div md.mr +1;
jr:=(x-1) mod md.mr +1;
wr:=R[ir,jr];
cx:=(wr.Left+wr.Right) div 2;
cy:=(wr.Top+wr.Bottom) div 2;
w:=(wr.Right-wr.Left) div 12;
h:=(wr.Bottom-wr.Top) div 7;
wr.Left:=cx-w;
wr.Right:=cx+w;
wr.Top:=cy-h;
wr.Bottom:=cy+h;
mC.MoveTo(cx,cy);
mC.Brush.Color:=RGB(0,255,0);
mC.Pen.Width:=3;
mC.Pen.Color:=RGB(255,255,255);
mC.Arc(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);
while k<>md.x0 do begin
k:=md.Prev[k];
x:=k+1;
ir:=(x-1) div md.mr +1;
jr:=(x-1) mod md.mr +1;
wr:=R[ir,jr];
cx:=(wr.Left+wr.Right) div 2;
cy:=(wr.Top+wr.Bottom) div 2;
w:=(wr.Right-wr.Left) div 12;
h:=(wr.Bottom-wr.Top) div 7;
wr.Left:=cx-w;
wr.Right:=cx+w;
wr.Top:=cy-h;
wr.Bottom:=cy+h;
mC.Pen.Width:=7;
mC.Pen.Color:=RGB(255,0,0);
mC.LineTo(cx,cy);
mC.Brush.Color:=RGB(0,255,0);
mC.Pen.Width:=3;
mC.Pen.Color:=RGB(255,255,255);
mC.Chord(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);
end;
end;
// процедура рисует перегородки лабиринта
procedure TOcno.DrawRect(i,j:Integer; md:Tway);
var d:Integer;
wr,wrG:TRect;
CR:TColor;
wd:Integer;
begin
wd:=14; //Перегородки
wr:=R[i,j];
wrG:=wr;
d:=3;
Inc(wr.Left,d);
Inc(wr.Top,d);
Dec(wr.Right,d);
Dec(wr.Bottom,d);
mC.Brush.Color:=C1;
mC.Pen.Width:=0;
mC.Pen.Color:=RGB(0,255,255);
mC.FillRect(wr);
CR:=RGB(255,128,255);
if md.Wr[i,j].L<>1 then
begin
mC.pen.Color:=CR; mC.Pen.Width:=wd;
mc.MoveTo(wr.Left,wr.Top+3);
mc.LineTo(wr.Left,wr.Bottom-3);
end;
if md.Wr[i,j].R<>1 then
begin
mC.pen.Color:=CR; mC.Pen.Width:=wd;
mc.MoveTo(wr.Right,wr.Top+3);
mc.LineTo(wr.Right,wr.Bottom-3);
end;
if md.Wr[i,j].U<>1 then
begin
mC.pen.Color:=CR; mC.Pen.Width:=wd;
mc.MoveTo(wr.Left+2,wr.Top);
mc.LineTo(wr.Right-2,wr.Top);
end;
if md.Wr[i,j].D<>1 then
begin
mC.pen.Color:=CR; mC.Pen.Width:=wd;
mc.MoveTo(wr.Left+2,wr.Bottom);
mc.LineTo(wr.Right-2,wr.Bottom);
end;
end;
6. Руководство пользователя
При разработке программы применялся принятый в среде Delphi объектно-ориентированный подход для разработки интерфейса. При реализации алгоритмов обработки данных использовался структурный подход. В рабочем окне программы лабиринт занимает все пространство. Управление программой выполняется посредством меню приложения, расположенное в главном окне.
Назначение пунктов меню.
· «Компоненты» — пункт меню содержит в себе две вкладки
- «О программе» — выбор пункта меню сопровождается вызовом диалога сообщения о разработчике приложения.
- «Выход» — пункт меню выхода из приложения.
· «Файл лабиринта» — пункт меню позволяет выбрать различные лабиринты.
· «Вычислить» — пункт меню находит кратчайший путь и рисует лабиринт и показывает найденный путь.
Если путь найден, он выдает сообщение и рисует лабиринт и найденный путь. Если путь не найден на экран выводится сообщения «Путь не найден», рисует лабиринт и путь который не достигает нужной точки.
Структура данных клеточной области лабиринта определяется в текстовом файле. Такие файлы — это исходные данными приложения. Выбор файла данных лабиринта осуществляется в диалоге, вызов которого выполняется пунктом меню «Файл лабиринта».
Описание структуры данных файла лабиринта.
При подготовке данных условно ввели обозначения цифрой 8 для комнат лабиринта.
Дана цифра никак не используется. Однако она применяется для установки конфигурации перегородок между комнатами.
Например, комната 8 имеет перегородки сверху и снизу, а справа и слева они отсутствует.
Данные реального примера лабиринта
1 1 — координаты начала пути
6 4 – координаты конца пути
7 6 – размерность матрицы
0 0 0 0 0 0 - верхние перегородки
0 8 1 8 1 8 0 8 0 8 0 8 0 – комнаты и боковые перегородки
1 1 1 1 0 1 – внутренние перегородки комнат
0 8 0 8 0 8 1 8 0 8 1 8 0
0 0 0 1 0 1
0 8 1 8 1 8 1 8 1 8 1 8 0
1 0 0 0 0 1
0 8 0 8 1 8 1 8 1 8 1 8 0
1 1 0 1 0 1
0 8 0 8 0 8 1 8 0 8 0 8 0
0 0 1 0 1 1
0 8 1 8 1 8 0 8 0 8 0 8 0
1 0 0 1 1 1
0 8 1 8 1 8 1 8 0 8 1 8 0
0 0 0 0 0 0
По этим данным выполнены тестовые расчеты, результаты которых приведены ниже в тестовом примере (рис.1).
7. Тестовый пример
Тестовый пример является расчетом кратчайшего пути в лабиринте.
Рис.1. Рабочее окно приложения – нахождения кратчайшего пути
Заключение
Результатом работы над курсовой работой создано приложение среде Delphi, которое находит в нем кратчайший путь и визуализирует его на форме приложения. Приложение является полупрофессиональным, допускает различные варианты лабиринтов, настройкой соответствующих параметров. Выполненные многочисленные тестовые примеры позволяют утверждать, что надежность программного обеспечения проекта довольно высока.
Список литературы
1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ, 2000. – 288с.
2. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.