Staonův svět - Vyhledávání nejkratší cesty

Protože jsem dneska neobyčejně aktivní, vyrobil jsem ještě jeden příkládek. Jedná se o určitou kostru vyhledávání nejkratší cesty po šachovnici (případně s překážkami).

V téhle verzi, protože jsem byl líný, se pohybuje král po prázdné šachovnici. Pro případ pohybu koně, nebo jiné figury, je potřeba přepsat proceduru makeStep tak, aby vytvářela tahy této figury. Zde je potřeba spočítat všechny pozice, kam se ze zadané pozice lze posunout. Pro koně je to jednoduché, ten může skákat přes překážky, pro jiné figury je potřeba se na překážkách zarazit.

Další, co si případný uživatel musí zajistit, je načtení dat: „bludiště“ na šachovnici a počáteční a koncovou pozici.

Dál už stačí jen vyvolat funkci mainLoop. Ta vrací true, pokud cestu nalezne, jinak false. Procedura printWay vytiskne nalezenou cestu. Cesta se hledá pozpátku od cíle ke startu, aby interpretace zpětných značek byl rovnou nalezenou cestou.

  1. const
  2.   MAX_N = 100;
  3.  
  4. type
  5.   { -- pozice na sachovnici }
  6.   OPozice = record
  7.     x, y: integer;
  8.   end;
  9.   { -- mozne typy pole na sachovnici }
  10.   OTyp = (PREKAZKA, START, STOP, VOLNO);
  11.   { -- pole sachovnice }
  12.   OPole = record
  13.     typ: OTyp;
  14.     vlna: integer;      { -- "umisteni" pole v alg. vlny }
  15.     predchozi: OPozice;  { -- znacka, odkud se na pole prislo }
  16.   end;
  17.   { -- sachovnice }
  18.   OSachovnice = array[0..MAX_N - 1, 0..MAX_N - 1] of OPole;
  19.  
  20.   { -- fronta pozic }
  21.   OQueue = record
  22.     zacatek, konec: integer;
  23.     fronta: array[0..MAX_N * MAX_N - 1] of OPozice;
  24.   end;
  25.  
  26. procedure initBoard(var sachovnice: OSachovnice; n: integer);
  27. var
  28.   x, y: integer;
  29. begin
  30.   for y := 0 to n - 1 do
  31.     for x := 0 to n - 1 do
  32.     begin
  33.       sachovnice[x, y].typ := VOLNO;
  34.       sachovnice[x, y].vlna := 0;
  35.       sachovnice[x, y].predchozi.x := -1;
  36.       sachovnice[x, y].predchozi.y := -1;
  37.     end;
  38. end;
  39.  
  40. procedure queueInit(var fronta: OQueue);
  41. begin
  42.   fronta.zacatek := 0;
  43.   fronta.konec := 0;
  44. end;
  45.  
  46. function queueIsEmpty(var fronta: OQueue): boolean;
  47. begin
  48.   queueIsEmpty := fronta.zacatek = fronta.konec;
  49. end;
  50.  
  51. function queueChange(index: integer): integer;
  52. begin
  53.   queueChange := (index + 1) mod (MAX_N * MAX_N);
  54. end;
  55.  
  56. procedure queuePut(var fronta: OQueue; x, y: integer);
  57. begin
  58.   fronta.fronta[fronta.zacatek].x := x;
  59.   fronta.fronta[fronta.zacatek].y := y;
  60.   fronta.zacatek := queueChange(fronta.zacatek);
  61. end;
  62.  
  63. procedure queueGet(var fronta: OQueue; var x, y: integer);
  64. begin
  65.   x := fronta.fronta[fronta.konec].x;
  66.   y := fronta.fronta[fronta.konec].y;
  67.   fronta.konec := queueChange(fronta.konec);
  68. end;
  69.  
  70. procedure putPosition(
  71.       var sachovnice: OSachovnice;
  72.       var fronta: OQueue;
  73.       x, y: integer;
  74.       currx, curry: integer;
  75.       n: integer);
  76. begin
  77.   if (x >= 0) and (x < n) and (y >= 0) and (y < n) and
  78.      ((sachovnice[x, y].typ = VOLNO) or (sachovnice[x, y].typ = STOP))
  79.      and (sachovnice[x, y].vlna = 0) then
  80.   begin
  81.     { -- pole je volne a jeste jsem zde nebyl }
  82.  
  83.     { -- nastavim znacku zpet }
  84.     sachovnice[x, y].predchozi.x := currx; sachovnice[x, y].predchozi.y := curry;
  85.     { -- nastavim aktualni cislo vlny }
  86.     sachovnice[x, y].vlna := sachovnice[currx, curry].vlna + 1;
  87.     { -- zaradim do fronty }
  88.     queuePut(fronta, x, y);
  89.   end;
  90. end;
  91.  
  92. procedure makeStep(
  93.       var sachovnice: OSachovnice;
  94.       var fronta: OQueue;
  95.       x, y: integer;
  96.       n: integer);
  97. var
  98.   i: integer;
  99. begin
  100.   for i := -1 to 1 do
  101.   begin
  102.     putPosition(sachovnice, fronta, x + i, y - 1, x, y, n);
  103.     putPosition(sachovnice, fronta, x + i, y + 1, x, y, n);
  104.   end;
  105.   putPosition(sachovnice, fronta, x - 1, y, x, y, n);
  106.   putPosition(sachovnice, fronta, x + 1, y, x, y, n);
  107. end;
  108.  
  109. function mainLoop(
  110.       var sachovnice: OSachovnice;
  111.       var fronta: OQueue;
  112.       cil: OPozice;
  113.       n: integer): boolean;
  114. var
  115.   x, y: integer;
  116. begin
  117.   mainLoop := FALSE;
  118.  
  119.   while(not queueIsEmpty(fronta)) do
  120.   begin
  121.     queueGet(fronta, x, y);
  122.     if(x = cil.x) and (y = cil.y) then
  123.     begin
  124.       { -- dorazil jsem do cile, hurra }
  125.       mainLoop := TRUE;
  126.       break;
  127.     end;
  128.     { -- neni cil, zkusim se z pole posunout dal }
  129.     makeStep(sachovnice, fronta, x, y, n);
  130.   end;
  131. end;
  132.  
  133. procedure printWay(var sachovnice: OSachovnice; x, y: integer);
  134. var
  135.   h: integer;
  136. begin
  137.   while(x <> -1) do
  138.   begin
  139.     write('<', x, ', ' , y, '> ');
  140.     h := x;
  141.     x := sachovnice[h, y].predchozi.x;
  142.     y := sachovnice[h, y].predchozi.y;
  143.   end;
  144.   writeln;
  145. end;
  146.  
  147. procedure main;
  148. var
  149.   sachovnice: OSachovnice;
  150.   fronta: OQueue;
  151.   n: integer;
  152.   strt, cil: OPozice;
  153. begin
  154.   { -- nacteni velikosti sachovnice }
  155.   n := 10;
  156.  
  157.   { -- inicializace }
  158.   initBoard(sachovnice, n);
  159.   queueInit(fronta);
  160.  
  161.   { -- cil a start se predpoklada prohozeny, abych vyslednou
  162.        cestu jen vypsal }
  163.   strt.x := 1; strt.y := 3;   { -- ve skutecnosti cil }
  164.   cil.x := 9; cil.y := 8;       { -- ve skutecnosti start }
  165.   { -- nastavim typy poli pro cil a start }
  166.   sachovnice[cil.x, cil.y].typ := STOP;
  167.   sachovnice[strt.x, strt.y].typ := START;
  168.   { -- vlozim do fronty prvni pozici }
  169.   queuePut(fronta, strt.x, strt.y);
  170.   { -- pokud je cesta nalezena, vypisu ji }
  171.   if mainLoop(sachovnice, fronta, cil, n) then
  172.     printWay(sachovnice, cil.x, cil.y)
  173.   else
  174.     writeln('Cesta nenalezena!');
  175. end;
  176.  
  177. begin
  178.   main;
  179. end.

Opět, pokud naleznete chyby, ozvěte se. Moc jsem to netestoval.

Staon | 6.2.2006 Po 22:29 | <<< trvalý odkaz >>> | tisk | 2 komentáře

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Ben mejl web 6.2.2006 Po 23:53

Přesně po tomhle jsem celé roky toužil! Teď jen přijít na to, jak to použít a budu mít ten hlavolam z mateřídoušky vyřešený!!

Ehm, to nic, jenom hloupě žertuji o něčem, čemu vůbec nerozumím. ;o) Se omlouvám, ale mám nějakou rozvernou.

[2] reaguj
Jimi mejl web 7.2.2006 Út 09:09

Fakt neviem ako to robis, ze tam mas okrem mainu 10 procedur a funkcii… Ja by som to spravil… vlastne ja som to spravil (kedysi davno) styrmi (takmer identickymi) funkciami/procedurami. Kazdopadne, za vrchol svojej programatorskej kariery povazujem hladanie najkratsej cesty v sestuholnikovom systeme (to som uz niekde pisal), s ktorym som sa drel denno-denne asi 6 mesiacov :-)) A ty spravis ten zaklad za par desiatok minut :-) Clovek moze len zavidiet

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Matfyz je sbírka čeho?
Odpověd: malých červených kulatých kostiček naprostých cvoků

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).