Пошук шляху в лабіринті
Реалізація алгоритму пошуку ортогонального шляху між двома точками у вигляді окремого модуля. Дозволяє як знаходити шлях та і окремо використовувати створену для цього мапу дистації/напрямку.
Під катом посилання на модуль та приклади використання
Простий приклад
var
nm: TfwNodesMap;
i: Integer;
// створюємо об’єкт
nm := TfwNodesMap.Create;
try
// завантажуємо мапу лабіринту із прикладу
nm.ImportFromBitmap('labirint.bmp');
// встановлюємо початкову позицію в ЛВК
nm.SetBasePoint(GetCoord(0, 0));
// встановлюємо цільову позицію в НПК
nm.SetTargetPoint(GetCoord(29, 29));
// будуємо мапу дистанцій/напрямів та шлях від початкової до цільової позиції
if not nm.FindWayToTarget then
if nm.WayNodeCount > 0 then
for i := 0 to nm.WayNodeCount - 1 then
// відображаємо точки шляху
ListBox1.Items.Add(Format('WayPoint %d [%d %d]', [i, nm.WayNode[i].x, nm.WayNode[i].y]));
finally
// звільняємо пам’ять
FreeAndNil(nm);
end;
Пошук кількох шляхів
Пошук здійснюємо по вже побудованій мапі дистанцій/напрямів.
// встановлюємо початкову позицію в ЛВК
nm.SetBasePoint(GetCoord(0, 0));
// будуємо мапу дистанцій/напрямів
nm.BuildMap;
// будуємо шляхи по вже обчисленій мапі
if nm.IsFullMapBuild then
begin
// шлях 1
if nm.BuildWayTo(12, 2) then
... // відображаємо шлях 1
// шлях 2
if nm.BuildWayTo(6, 8 ) then
... // відображаємо шлях 2
end;
Пошук за умовами користувача
Клас пошукового механізму підтримує події OnProcessNode (спрацьовує перед початком обробки вузла) та OnAddQueue (при додаванні вузла до черги обробки), за допомогою яких можна змінювати стандартний алгоритм пошуку и «блокувати» напрями, що не підходять.
OnProcessNode
const Pos: TfwCoord – позиція вузла;
const Distance: Integer – дистанція вузла;
const FromDir: TfwDirection – напрям на попередній вузол;
OnAddQueue
const ParentPos: TfwCoord – позиція вузла, з якого здійснюється обробка інших вузлів;
const Pos: TfwCoord – позиція вузла, що додається;
const Distance: Integer – дистанція вузла;
const FromDir: TfwDirection – напрям на попередній вузол;
var Add: Boolean – чи додавати вузол;
Якщо вузол не буде доданий, то він відмічається як виключений із пошуку.
Приклад пошуку за умовами користувача
Для прикладу, спробуємо знайти шлях від початкової до цільової позиції шириною не менше двох клітин. Для цього нам потрібно перевіряти ширину прямих та діагональних «проходів», як показано на малюнку нижче.
Процедури обробки подій:
procedure TForm1.OnProcessNode(const Pos: TfwCoord; const Distance: Integer;
const FromDir: TfwDirection);
var
DiagA, DiagB: Boolean;
begin
DiagA := False;
DiagB := False;
if (Pos.x > 0) and (Pos.y > 0) and (Pos.x < nm.Size.Width - 1) and (Pos.y < nm.Size.Height - 1) then
begin
// діагональна перевірка непрохідності A
// [A]
// [X]
// [A]
DiagA := ((nm.Node[Pos.X - 1, Pos.Y - 1].Barier) or (nm.Node[Pos.X - 1, Pos.Y - 1].Excluded)) and
((nm.Node[Pos.X + 1, Pos.Y + 1].Barier) or (nm.Node[Pos.X + 1, Pos.Y + 1].Excluded));
// діагональна перевірка непрохідності B
// [B]
// [X]
// [B]
DiagB := ((nm.Node[Pos.X - 1, Pos.Y + 1].Barier) or (nm.Node[Pos.X - 1, Pos.Y + 1].Excluded)) and
((nm.Node[Pos.X + 1, Pos.Y - 1].Barier) or (nm.Node[Pos.X + 1, Pos.Y - 1].Excluded));
// виключаємо взли в залежності від напрямку пошуку
case FromDir of
dLeft:
begin
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
end;
dRight:
begin
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
end;
end;
dUp:
begin
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
end;
dBottom:
begin
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
end;
end;
end;
end;
end;
procedure TForm1.OnAddQueue(const ParentPos, Pos: TfwCoord; const Distance: Integer;
const FromDir: TfwDirection; var Add: Boolean);
var
SideP_c, Side_c: TPoint;
SideA, SideB: Boolean;
begin
// перевірка ширини шляху
case FromDir of
dLeft,
dRight:
begin
SideA := False;
SideB := False;
SideP_c := Point(ParentPos.x, ParentPos.y - 1);
Side_c := Point(Pos.x, Pos.y - 1);
if nm.CheckNodeCoord(SideP_c) and nm.CheckNodeCoord(Side_c) then
SideA := (not nm.Node[SideP_c.X, SideP_c.Y].Barier) and (not nm.Node[Side_c.X, Side_c.Y].Barier);
SideP_c := Point(ParentPos.x, ParentPos.y + 1);
Side_c := Point(Pos.x, Pos.y + 1);
if nm.CheckNodeCoord(SideP_c) and nm.CheckNodeCoord(Side_c) then
SideB := (not nm.Node[SideP_c.X, SideP_c.Y].Barier) and (not nm.Node[Side_c.X, Side_c.Y].Barier);
Add := SideA or SideB;
end;
dUp,
dBottom:
begin
SideA := False;
SideB := False;
SideP_c := Point(ParentPos.x - 1, ParentPos.y);
Side_c := Point(Pos.x - 1, Pos.y);
if nm.CheckNodeCoord(SideP_c) and nm.CheckNodeCoord(Side_c) then
SideA := (not nm.Node[SideP_c.X, SideP_c.Y].Barier) and (not nm.Node[Side_c.X, Side_c.Y].Barier);
SideP_c := Point(ParentPos.x + 1, ParentPos.y);
Side_c := Point(Pos.x + 1, Pos.y);
if nm.CheckNodeCoord(SideP_c) and nm.CheckNodeCoord(Side_c) then
SideB := (not nm.Node[SideP_c.X, SideP_c.Y].Barier) and (not nm.Node[Side_c.X, Side_c.Y].Barier);
Add := SideA or SideB;
end;
end;
end;
...
nm := TfwNodesMap.Create;
nm.OnProcessNode := OnProcessNode;
nm.OnAddQueue := OnAddQueue;
Результати роботи алгоритмів на одному і тому самому шаблоні:
Стандартний
Шлях у дві клітини
Удосконалення алгоритму
Вищенаведений алгоритм має певні недоліки, наприклад, якщо ми спробуємо знайти шлях в точку, позначену зеленим:
то зіткнемося з ситуацією, що цільову позицію вже було виключено з пошуку на попередньому етапі, і шлях до неї не буде знайдено:
Тож, перед початком аналізу, які саме вузли потрібно відключити від пошуку, бажано щоб всі ці вузли обов’язково були підключені, як показано нижче.
З урахуванням цього, код процедури обробки події OnProcessNode повинен бути наступним:
procedure TForm1.OnProcessNode(const Pos: TfwCoord; const Distance: Integer;
const FromDir: TfwDirection);
var
DiagA, DiagB: Boolean;
begin
DiagA := False;
DiagB := False;
if (Pos.x > 0) and (Pos.y > 0) and (Pos.x < nm.Size.Width - 1) and (Pos.y < nm.Size.Height - 1) then
begin
// діагональна перевірка непрохідності A
// [A]
// [X]
// [A]
DiagA := ((nm.Node[Pos.X - 1, Pos.Y - 1].Barier) {or (nm.Node[Pos.X - 1, Pos.Y - 1].Excluded)}) and
((nm.Node[Pos.X + 1, Pos.Y + 1].Barier) {or (nm.Node[Pos.X + 1, Pos.Y + 1].Excluded)});
// діагональна перевірка непрохідності B
// [B]
// [X]
// [B]
DiagB := ((nm.Node[Pos.X - 1, Pos.Y + 1].Barier) {or (nm.Node[Pos.X - 1, Pos.Y + 1].Excluded)}) and
((nm.Node[Pos.X + 1, Pos.Y - 1].Barier) {or (nm.Node[Pos.X + 1, Pos.Y - 1].Excluded)});
// виключаємо взли в залежності від напрямку пошуку
case FromDir of
dLeft:
begin
// включення вузлів
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, False);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, False);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, False);
// виключення вузлів
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
end;
dRight:
begin
// включення вузлів
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, False);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, False);
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, False);
// виключення вузлів
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
end;
end;
dUp:
begin
// включення вузлів
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, False);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, False);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, False);
// виключення вузлів
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y + 1, True);
end;
end;
dBottom:
begin
// включення вузлів
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, False);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, False);
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, False);
// виключення вузлів
if DiagA then
begin
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
nm.ExcludedNodeByCoord(Pos.x + 1, Pos.y, True);
end;
if DiagB then
begin
nm.ExcludedNodeByCoord(Pos.x - 1, Pos.y, True);
nm.ExcludedNodeByCoord(Pos.x, Pos.y - 1, True);
end;
end;
end;
end;
end;
Останні коментарі