home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1997 #3 / amigamamagazinepolishissue03-1 / ma_1995 / 06 / ami038.txt < prev    next >
Text File  |  1997-04-07  |  16KB  |  750 lines
  1. -------------------------------------------------------------
  2.  
  3. Ustawiê TAB=3 w listingach
  4.  
  5. !Rys.n! - w miarë moûliwoôci wstawiê tutaj rys. n
  6.  
  7. -------------------------------------------------------------
  8.  
  9. NAJKRÓTSZA DROGA...
  10.  
  11. <lead>W ostatnim odcinku AMOS-a pokazaîem, jak moûna sprawdziê,
  12. czy istnieje droga z jednego punktu "labiryntu" do drugiego.
  13. Tylko komu to potrzebne? Wszak wszystkim wiadomo, ûe stwory z
  14. gier komputerowych nie sâ wyposaûone nawet w jeden mililitr
  15. rozumu, a co wiëcej -- nie potrzebujâ go. W grach tego typu liczy
  16. sië przede wszystkim dobra grafika, dúwiëk i muzyka oraz szybki
  17. ruch obiektów. Ûeby to osiâgnâê, wszystkie algorytmy sterujâce
  18. sprajtami powinny byê jak najprostsze. Jakie?
  19.  
  20. <a>Krzysztof Prusik
  21.  
  22. <txt>Na przykîad takie:
  23.  
  24. <l>Spróbuj iôê w stronë celu (oblicz kierunek)
  25.  
  26. Czy moûna tam iôê?
  27.  
  28. TAK
  29.  
  30.     No to rusz obiekt
  31.  
  32.  
  33.  
  34. NIE
  35.  
  36.     To spróbuj chwilowo skrëciê na lewo od kierunku do celu
  37.  
  38.  
  39.  
  40.     Czy moûna?
  41.  
  42.  
  43.  
  44.     TAK
  45.  
  46.         No to rusz obiekt
  47.  
  48.     
  49.  
  50.     NIE
  51.  
  52.         To spróbuj skrëciê na prawo od kierunku do celu
  53.  
  54.  
  55.  
  56.         Czy moûna?
  57.  
  58.  
  59.  
  60.         TAK
  61.  
  62.  
  63.  
  64.             To rusz obiekt
  65.  
  66.  
  67.  
  68.         NIE
  69.  
  70.  
  71.  
  72.             ...
  73.  
  74.  
  75.  
  76. --------------!Rys.1!----------------------
  77.  
  78. <txt>Zaletâ tego algorytmu jest szybkoôê dziaîania, a wadâ to, ûe
  79. nie zawsze dziaîa poprawnie. Otóû czasami moûe dojôê do
  80. zapëtlenia (rys. 2.), tj. sytuacji, w której obiekt bëdzie sië
  81. poruszaî tam i z powrotem, próbujâc odnaleúê drogë do celu.
  82.  
  83. ------------------!Rys.2 - zapëtlenia!--------------------
  84.  
  85. Nie jest to jednak wielka wada, gdy dotyczy miîych potworków ze
  86. strzelawek, które przecieû mogâ sië poruszaê, jak chcâ. Nie
  87. gniewam sië, gdy grajâc w gierkë widzë, jak mój przeciwnik, ûâdny
  88. krwi, miota sië jak szalony, próbujâc do mnie dotrzeê, ale nie
  89. moûe, ze wzglëdu na prosty algorytm ruchu.
  90.  
  91. Gorzej, gdy rzecz dotyczy mnie. W sîawnym Syndycate kierujemy
  92. agentami za pomocâ myszki, klikajâc na odpowiednie miejsce
  93. ekranu. Poniewaû jednak poruszajâ sië oni wedîug tego "biednego"
  94. algorytmu, czasem zdarza sië, ûe biegajâ w kóîko, nie umiejâc
  95. znaleúê wyjôcia z "labiryntu" domów. Koïczâc wywody teoretyczne,
  96. zakodujmy wreszcie ten banalny algorytm, uûywajâc do pomocy
  97. AMOS-a.
  98.  
  99. <l>' ProstyRuch (C) 1995 By Krzysztof Prusik
  100.  
  101. '
  102.  
  103. Global OBIEKT_X,OBIEKT_Y
  104.  
  105. Global CEL_X,CEL_Y
  106.  
  107. ' ---------------------- wspóîrzëdne obiektu
  108.  
  109. OBIEKT_X=10
  110.  
  111. OBIEKT_Y=10
  112.  
  113. ' ---------------------- wspóîrzëdne celu
  114.  
  115. CEL_X=20
  116.  
  117. CEL_Y=15
  118.  
  119. ' ---------------------- gîówna pëtla
  120.  
  121. Repeat
  122.  
  123.     OBIEKT_RUSZ
  124.  
  125.     OBIEKT_WYSWIETL
  126.  
  127.     ' pëtlë powtarzamy tak dîugo, aû obiekt
  128.  
  129.     ' znajdzie sië w celu
  130.  
  131. Until (OBIEKT_X=CEL_X) and (OBIEKT_Y=CEL_Y)
  132.  
  133. ' ----------------------- procedury...
  134.  
  135.  
  136. <txt>Programik jest prosty, prawda? Znowu caîâ robotë zwalamy na
  137. gîównâ procedurë (OBIEKT_RUSZ), której zadaniem bëdzie obliczenie
  138. nowych wspóîrzëdnych (OBIEKT_X,OBIEKT_Y). Jak to zrobimy? Ano,
  139. wedîug schematu zamieszczonego na poczâtku artykuîu, tj. najpierw
  140. obliczymy poûâdany kierunek ruchu obiektu (rys. 3.), a nastëpnie
  141. postaramy sië w miarë moûliwoôci (jeôli bëdzie droga) przemieôciê
  142. obiekt w stronë celu.
  143.  
  144. ---------------!Rys.3 - kierunek ruchu!-------------------------
  145.  
  146. Myszka z poprzedniego artykuîu potrafiîa sië przemieszczaê jedynie 
  147. w pionie i w poziomie (rys. 4.).
  148.  
  149. -----------------------!Rys.4 - przemieszczanie w pionie i poziomie!
  150.  
  151. Tym razem utrudnimy sobie zadanie i umoûliwimy jej ruch równieû
  152. "po skosie" (rys. 5.).
  153.  
  154. ---------------------------!Rys.5 - równieû po skosie!
  155.  
  156. No dobrze, a oto ta "skomplikowanie prosta" procedura w AMOS-ku:
  157.  
  158. <l>Procedure OBIEKT_RUSZ
  159.  
  160.     ' przemieszcza obiekt o wsp. OBIEKT_X,OBIEKT_Y
  161.  
  162.     ' o jednâ pozycjë w kierunku CEL_X,CEL_Y
  163.  
  164.     ' (oczywiôcie w miarë moûliwoôci)
  165.  
  166.     '
  167.  
  168.     ' --------------- kierunek ruchu obiektu w X i Y
  169.  
  170.     RX=Sgn(CEL_X-OBIEKT_X)
  171.  
  172.     RY=Sgn(CEL_Y-OBIEKT_Y)
  173.  
  174.     '---------------- czy moûna przesunâê obiekt o RX,RX?
  175.  
  176.     CZY_MOZNA[RX,RY] : MOZNA=Param
  177.  
  178.     If MOZNA
  179.  
  180.         ' czyli moûna obiekt tutaj przesunâê, wiëc przesuwamy
  181.  
  182.         OBIEKT_PRZESUN[RX,RY]
  183.  
  184.         ' i wychodzimy z procedury
  185.  
  186.         Pop Proc
  187.  
  188.     End If
  189.  
  190.     ' nie moûna, wiëc badamy dalej
  191.  
  192.     CZY_MOZNA[RX,0] : MOZNA=Param
  193.  
  194.     If MOZNA
  195.  
  196.         OBIEKT_PRZESUN[RX,0] : Pop Proc
  197.  
  198.     End If
  199.  
  200.     ' i jeszcze raz... aû do skutku
  201.  
  202.     CZY_MOZNA[0,RY] : MOZNA=Param
  203.  
  204.     If MOZNA
  205.  
  206.         OBIEKT_PRZESUN[0,RY] : Pop Proc
  207.  
  208.     End If
  209.  
  210.     CZY_MOZNA[-RX,RY] : MOZNA=Param
  211.  
  212.     If MOZNA
  213.  
  214.         OBIEKT_PRZESUN[-RX,RY] : Pop Proc
  215.  
  216.     End If
  217.  
  218.     CZY_MOZNA[RX,-RY] : MOZNA=Param
  219.  
  220.     If MOZNA
  221.  
  222.         OBIEKT_PRZESUN[RX,-RY] : Pop Proc
  223.  
  224.     End If
  225.  
  226.     CZY_MOZNA[0,-RY] : MOZNA=Param
  227.  
  228.     If MOZNA
  229.  
  230.         OBIEKT_PRZESUN[0,-RY] : Pop Proc
  231.  
  232.     End If
  233.  
  234.     CZY_MOZNA[-RX,0] : MOZNA=Param
  235.  
  236.     If MOZNA
  237.  
  238.         OBIEKT_PRZESUN[-RX,0] : Pop Proc
  239.  
  240.     End If
  241.  
  242.     CZY_MOZNA[-RX,-RY] : MOZNA=Param
  243.  
  244.     If MOZNA
  245.  
  246.         OBIEKT_PRZESUN[-RX,-RY] : Pop Proc
  247.  
  248.     End If
  249.  
  250.     ' skoro tutaj dotarliômy, to znaczy, ûe obiektu
  251.  
  252.     ' nigdzie nie moûna przesunâê
  253.  
  254. End Proc
  255.  
  256. Procedure CZY_MOZNA[RX,RY]
  257.  
  258.     ' bada, czy moûna przesunâê obiekt w kierunku RX,RY
  259.  
  260.     ' czyli po prostu mówi, czy pole 
  261.  
  262.     ' OBIEKT_X+RX,OBIEKT_Y+RY
  263.  
  264.     ' znajduje sië w obrëbie tablicy i czy jest wolne
  265.  
  266.     '
  267.  
  268.     '--------------- potencjalne wsp. obiektu
  269.  
  270.     NX=OBIEKT_X+RX
  271.  
  272.     NY=OBIEKT_Y+RY
  273.  
  274.     '--------------- pesymistyczne zaîoûenie
  275.  
  276.     MOZNA=False
  277.  
  278.     If (NX>=0) and (NX<=X_MAX)
  279.  
  280.         If (NY>=0) and (NY<=Y_MAX)
  281.  
  282.             If POLE(NX,NY)=WOLNE
  283.  
  284.                 MOZNA=True
  285.  
  286.             End If
  287.  
  288.         End If
  289.  
  290.     End If
  291.  
  292. End Proc[MOZNA]
  293.  
  294. Procedure OBIEKT_PRZESUN[RX,RY]
  295.  
  296.     ' przesuwa obiekt w kierunku RX,RY
  297.  
  298.     Add OBIEKT_X,RX
  299.  
  300.     Add OBIEKT_Y,RY
  301.  
  302.     ' pokaû obiekt na ekranie
  303.  
  304. End Proc
  305.  
  306. Procedure OBIEKT_WYSWIETL
  307.  
  308.     ' wyôwietla obiekt w punkcie o wspóîrzëdnych
  309.  
  310.     ' OBIEKT_X,OBIEKT_Y
  311.  
  312.     POKAZ_KURSOR[OBIEKT_X,OBIEKT_Y]
  313.  
  314. End Proc
  315.  
  316.  
  317. <txt>Wszystko jasne? Nie pociemniaîo Ci w oczach? No to doprowadú
  318. do odpalenia programu. Oczywiôcie nie zapomnij, ûe najpierw
  319. trzeba zbudowaê labirynt (procedura opisana w poprzednim
  320. artykule), oraz m.in. zdefiniowaê procedurkë POKAZ_KURSOR.
  321.  
  322. A teraz wykonajmy maîy
  323.  
  324. <sr>Eksperyment
  325.  
  326. <txt>Sprawmy, ûeby ruchomy byî nie tylko obiekt, ale równieû cel. Jak
  327. to zrobiê? Dopiszmy nowâ procedurë na przesuwanie celu (i umieôêmy
  328. jej wywoîanie w pëtli <Do...Loop>, tuû za OBIEKT_RUSZ).
  329.  
  330. <l>Procedure CEL_RUSZ
  331.  
  332.     ' losowy kierunek ruchu
  333.  
  334.     RX=1-Rnd(2) : Rem moûe byê -1,0 albo 1
  335.  
  336.     RY=1-Rnd(2) : Rem moûe byê -1,0 albo 1
  337.  
  338.     ' przesuï
  339.  
  340.     Add CEL_X,RX
  341.  
  342.     Add CEL_Y,RY
  343.  
  344. End Proc
  345.  
  346. Procedure CEL_WYSWIETL
  347.  
  348.     ...
  349.  
  350. End Proc
  351.  
  352.  
  353. <txt>Procedurka CEL_WYSWIETL równieû nie jest zbyt trudna do
  354. napisania (analogiczna do POKAZ_KURSOR), jednak celowo jej tutaj
  355. nie zamieôciîem, aby Ci, drogi Czytelniku, nie robiê w gîowie
  356. sieczki. Otóû wiedza podana na tacy nie jest zapamiëtywana i robi
  357. uczâcemu sië wiëcej szkody niû poûytku.  Dlaczego tak jest? Bo
  358. czytajâc dokîadne porady typu "jak to zrobiê", nie uûywamy
  359. czynnie wîasnego umysîu, lecz przyswajamy materiaî metodâ
  360. "zrozumieê-zapomnieê".
  361.  
  362. Aby nauczyê sië programowaê, naleûy uruchomiê wîasne procesy
  363. myôlowe. Czytajâc programy zamieszczone w artykuîach, staraj sië
  364. podchodziê do nich w sposób: "a jak ja bym to napisaî?". Ûeby Ci
  365. w tym pomóc, staram sië jak najczëôciej zostawiaê furtkë dla
  366. Twojej kreatywnoôci i indywidualnoôci. Czy teraz nie gniewasz
  367. sië, ûe nie zamieôciîem peînej procedury CEL_WYSWIETL? Dla
  368. uîatwienia dodam, ûe najlepiej skorzystaê z dobrodziejstw, jakie
  369. oferujâ sprite'y i boby.
  370.  
  371. Czy juû uruchomiîeô program? Ômieszne, prawda? Dwa sprite'y
  372. ganiajâce sië po ekranie... Co zrobiê, ûeby ich byîo wiëcej?
  373.  
  374. <sr>Minigierka
  375.  
  376. <txt>Napiszmy program, który wstrzyma sîoïce, a wzruszy stadko
  377. obiektów.  Taka zabawa: pierwszy obiekt goni drugi, drugi --
  378. trzeci, trzeci -- czwarty... ostatni -- pierwszy. Powinno byê
  379. ciekawie. Lubië programowaê! Szybko, zróbmy to! Na poczâtku
  380. trzeba zadeklarowaê tablicë wspóîrzëdnych obiektów.
  381.  
  382. <l>LICZBA_OBIEKTOW=4 : Rem --- na poczâtek wystarczy
  383.  
  384. Dim OBIEKT_X(LICZBA_OBIEKTOW)
  385.  
  386. Dim OBIEKT_Y(LICZBA_OBIEKTOW)
  387.  
  388. Global OBIEKT_X(),OBIEKT_Y()
  389.  
  390. <txt>I to wîaôciwie prawie wszystkie modyfikacje w gîównym
  391. listingu. Teraz trzeba kaûdâ z procedurek operujâcych na
  392. obiektach zmodyfikowaê tak, aby w zaleûnoôci od parametru I,
  393. przesuwaîa obiekt I. Potrafisz to zrobiê sam?  Oczywiôcie w
  394. gîównym listingu, w pëtli <Do...Loop>, zamiast:
  395.  
  396. <l>OBIEKT_RUSZ
  397.  
  398. OBIEKT_WYSWIETL
  399.  
  400. <txt>trzeba bëdzie wstawiê:
  401.  
  402. <l>For I=1 To LICZBA_OBIEKTOW
  403.  
  404.     OBIEKT_RUSZ[I]
  405.  
  406.     OBIEKT_WYSWIETL[I]
  407.  
  408. Next
  409.  
  410. ------------------!Rys.6 - rysunek, z czterema ganiajâcymi sië sprite-ami!
  411.  
  412. <txt>Czy teraz wszystko jasne? Mam cichâ nadziejë... Czy juû zmodyfikowaîeô
  413. i odpaliîeô program? Teraz to dopiero zabawa, co? Budujesz
  414. labirynt, a obiekty ganiajâ sië jak gîupie.
  415.  
  416. <sr>Najkrótsza droga
  417.  
  418. <txt>Tytuî artykuîu sugerowaî, ûe caîy odcinek AMOS-a poôwiëcony
  419. bëdzie wyszukiwaniu NAJKRÓTSZEJ drogi, a nie jakiemuô tam
  420. ograniczonemu algorytmowi, który nawet nie jest w stanie
  421. stwierdziê, czy dana droga w ogóle istnieje. Dlaczego zaczâîem od
  422. takiego wstëpu? Poniewaû chciaîem pokazaê, ûe sâ algorytmy bardzo
  423. szybkie (i zarazem proste), tj. takie, które nie tracâ czasu na
  424. zbyt wiele obliczeï, lecz majâ, niestety, wiele ograniczeï
  425. (zapëtlenia).
  426.  
  427. Algorytm z poprzedniego artykuîu jest juû bardziej inteligentny
  428. (potrafi stwierdziê, czy dana droga istnieje i na dodatek
  429. odnajduje jâ), lecz juû nie jest aû tak szybki. Ten zaô algorytm,
  430. którym sië zajmiemy teraz, jest, niestety, powolny (na
  431. pocieszenie dodam, ûe lepszego nie da sië juû napisaê).
  432. Dlaczego? Bo wyszukujâc najkrótszâ drogë trzeba porównaê
  433. wszystkie inne, czyli przelecieê caîâ tablicë ze zdefiniowanym
  434. labiryntem (rys. 7.).
  435.  
  436. --------------------!Rys.7 - kilka dróg!
  437.  
  438. Oczywiôcie nie ma sensu sprawdzaê kilka razy danego odcinka drogi
  439. (rys. 8.).
  440.  
  441. ---------------------!Rys.8 - drogi nachodzâ na siebie!
  442.  
  443. Nie wspomnë juû o zapëtleniach. Chyba teraz jest juû jasne, ûe
  444. ten algorytm nie jest banalny? No wiëc pytanie za sto punktów:
  445. Jak go napisaê? Trudne, prawda? No wiëc inne pytanie: Jak
  446. rozwiâzaê zadanie przy uûyciu kartki i dîugopisu (ewentualnie
  447. oîówka, moûe byê równieû mazak)? Geniusze, do dzieîa! Myôleê,
  448. myôleê! (Patrz pomocniczy rysunek 9.).
  449.  
  450. ---------------------!Rys.9 - labirynt pomocniczy do myôlenia!
  451.  
  452. No i jak? Przyznam sië szczerze, ûe gdy pierwszy raz usîyszaîem
  453. treôê zadania, sam nie potrafiîem go zrobiê. Tak wiëc wszyscy,
  454. którym sië to równieû nie udaîo, niech nie rozpaczajâ, tylko
  455. posîuchajâ czîowieka oôwieconego.
  456.  
  457. Dîugoôê drogi, to liczba kratek, które musi pokonaê obiekt,
  458. docierajâc do celu (pomijajâc zapëtlenia). Zwykle, gdy
  459. rozwiâzujemy jakiekolwiek zadanie, dzielimy je na kawaîeczki. No
  460. wiëc tak: ruszamy obiekt o jedno pole w kaûdâ stronë (oczywiôcie
  461. tylko tam, gdzie moûna) i wpisujemy w to pole odlegîoôê od punktu
  462. startu. Dla kaûdego z pól, gdzie stanëliômy, wykonujemy to samo.
  463. I tyle! Proste? Jeôli nie, to spójrz na rys. 10.
  464.  
  465. Oto nieco inne wyjaônienie: W punkcie startu wpisujemy 0.
  466. Bierzemy wszystkie punkty odlegîe o jeden od startu i wpisujemy
  467. tam jedynkë. Bierzemy wszystkie punkty odlegîe o dwa (czyli
  468. jeszcze nie zapisane i odlegîe od ostatnio zapisanych punktów o
  469. jeden) i wpisujemy dwójkë. I tak dalej, i tak dalej... Czy juû
  470. potrafiîbyô napisaê taki program? Zastanów sië nad tym...
  471.  
  472. <sr>Kolejka
  473.  
  474. <txt>Utrudnieniem jest to, ûe trzeba skorzystaê z pewnej (byê
  475. moûe dla Ciebie nowej) struktury danych, jakâ jest kolejka.
  476. Potrzebna jest nam ona do przechowywania wspóîrzëdnych punktów
  477. odlegîych od startu o n.  Jak ona dziaîa? Dokîadnie tak samo, jak
  478. w dawnych komunistycznych czasach kolejki po miësko. "Nowi"
  479. przychodzâ na koniec, "zaîatwieni" odchodzâ z poczâtku.
  480.  
  481. Ok? Implementacja takiej kolejki w AMOS-ie moûe wyglâdaê np. tak:
  482.  
  483. <l>' Kolejka (C) 1995 By Krzysztof Prusik
  484.  
  485. '
  486.  
  487. KOLEJKA_N=MAX_X : Rem --- rozmiar kolejki (chyba wystarczy...)
  488.  
  489. ' --------- kolejka
  490.  
  491. Dim KOLEJKA_X(KOLEJKA_N-1),KOLEJKA_Y(KOLEJKA_N-1)
  492.  
  493. Global KOLEJKA_X(),KOLEJKA_Y(),N,
  494.  
  495. ' --------- pozycja pierwszego i ostatniego el-tu kolejki
  496.  
  497. Global KOLEJKA_PIERWSZY,KOLEJKA_OSTATNI
  498.  
  499. ' --------- liczba elementów kolejki
  500.  
  501. Global KOLEJKA_ILE
  502.  
  503. '---------- bieûâce zmienne
  504.  
  505. Global X,Y
  506.  
  507.  
  508.  
  509. Procedure KOLEJKA_INICJUJ
  510.  
  511.     ' inicjalizuje kolejkë wspóîrzëdnych punktów
  512.  
  513.     KOLEJKA_ILE=0
  514.  
  515.     KOLEJKA_PIERWSZY=0
  516.  
  517.     KOLEJKA_OSTATNI=KOLEJKA_N-1
  518.  
  519. End Proc
  520.  
  521. Procedure KOLEJKA_NIEPUSTA
  522.  
  523.     ' sprawdza, czy kolejka nie jest pusta
  524.  
  525.     If KOLEJKA_ILE>0
  526.  
  527.         NIEPUSTA=True
  528.  
  529.     Else
  530.  
  531.         NIEPUSTA=False
  532.  
  533.     End If
  534.  
  535. End Proc[NIEPUSTA]
  536.  
  537. Procedure KOLEJKA_POBIERZ
  538.  
  539.     ' usuwa pierwsze wspóîrzëdne z kolejki
  540.  
  541.     ' i podstawia podstawia pod zmienne X,Y
  542.  
  543.     KOLEJKA_NIEPUSTA : NIEPUSTA=Param
  544.  
  545.     If NIEPUSTA
  546.  
  547.         Dec KOLEJKA_ILE
  548.  
  549.         X=KOLEJKA_X(KOLEJKA_PIERWSZY)
  550.  
  551.         Y=KOLEJKA_Y(KOLEJKA_PIERWSZY)
  552.  
  553.         KOLEJKA_PIERWSZY=(KOLEJKA_PIERWSZY+1)mod KOLEJKA_N
  554.  
  555.     Else
  556.  
  557.         Print "Kolejka pusta!"
  558.  
  559.         End
  560.  
  561.     End If
  562.  
  563. End Proc
  564.  
  565. Procedure KOLEJKA_WSTAW[X,Y]
  566.  
  567.     ' Wstawia wspóîrzëdne X,Y do kolejki
  568.  
  569.     If KOLEJKA_ILE=KOLEJKA_N
  570.  
  571.         Print "Kolejka peîna!"
  572.  
  573.         End
  574.  
  575.     Else
  576.  
  577.         KOLEJKA_OSTATNI=(KOLEJKA_OSTATNI+1)mod KOLEJKA_N
  578.  
  579.         KOLEJKA_X(KOLEJKA_OSTATNI)=X
  580.  
  581.         KOLEJKA_Y(KOLEJKA_OSTATNI)=Y
  582.  
  583.         Inc KOLEJKA_ILE
  584.  
  585.     End if
  586.  
  587. End Proc
  588.  
  589. <txt>Na specjalne ûyczenie Czytelników (listy) w nastëpnych
  590. artykuîach mogë opisaê dokîadniej "kolejkowâ" strukturë danych,
  591. na razie jednak wystarczy, jeôli bëdziesz wiedziaî, ûe
  592. dysponujemy operacjami, które robiâ, co robiâ (patrz rys. 11.). A
  593. oto algorytm (zaimplementowany w AMOS-ie) wyszukujâcy najkrótszâ
  594. drogë.
  595.  
  596. <l>' NajkrótszaDroga (C) 1995 By Krzysztof Prusik
  597.  
  598. '
  599.  
  600. WOLNE=-1 : Rem --- pole wolne
  601.  
  602. SCIANA=-2 : Rem --- sciana
  603.  
  604. Global WOLNE,SCIANA
  605.  
  606. ...tu wstawiê obsîugë kolejki
  607.  
  608. ...inicjalizacjë labiryntu (tablica POLE())
  609.  
  610. ...itp.
  611.  
  612. Procedure NAJKROTSZA_DROGA[_START_X,_START_Y,CEL_X,CEL_Y]
  613.  
  614.     ' wyszukuje najkrótszâ drogë od punktu
  615.  
  616.     ' o wspóîrzëdnych _START_X,_START_Y
  617.  
  618.     ' do punktu CEL_X,CEL_Y
  619.  
  620.     ' w tym celu przeszukuje tablicë POLE()
  621.  
  622.     ' wypeînionâ wartoôciami:
  623.  
  624.     '   -1 (WOLNE) - tam, gdzie pole jest wolne
  625.  
  626.     '   -2 (SCIANA) - tam, gdzie jest ôciana
  627.  
  628.     ' po wykonaniu procedury, w zmiennej WYNIK
  629.  
  630.     ' zawarta bëdzie dîugoôê najkrótszej drogi
  631.  
  632.     ' lub -1, gdy takiej nie ma.
  633.  
  634.     '
  635.  
  636.     '------------------- pesymistyczne zaîoûenie
  637.  
  638.     WYNIK=-1
  639.  
  640.     JEST=False
  641.  
  642.     KOLEJKA_INICJUJ
  643.  
  644.     X=_START_X
  645.  
  646.     Y=_START_Y
  647.  
  648.     If POLE[_START_X,_START_Y]=WOLNE
  649.  
  650.         POLE[X,Y]=1 : Rem odlegîoôê jeden
  651.  
  652.         If (X=CEL_X) and (Y=CEL_Y)
  653.  
  654.             JEST=True
  655.  
  656.             WYNIK=1
  657.  
  658.         Else
  659.  
  660.             ' wstawiamy pierwszy punkt do kolejki
  661.  
  662.             KOLEJKA_WSTAW[X,Y]
  663.  
  664.         End If
  665.  
  666.     Else
  667.  
  668.         Print "Pole powinno byê wolne!"
  669.  
  670.         End
  671.  
  672.     End If
  673.  
  674.     '--------------- zaczynamy pëtlë
  675.  
  676.     KOLEJKA_NIEPUSTA : NIEPUSTA=Param
  677.  
  678.     While NIEPUSTA and Not JEST
  679.  
  680.         KOLEJKA_POBIERZ
  681.  
  682.         I=1
  683.  
  684.         For RX=-1 To 1
  685.  
  686.             For RY=-1 To 1
  687.  
  688.                 If Not ((RX=0)and(RY=0))
  689.  
  690.                 SX=X+RX
  691.  
  692.                 SY=Y+RY
  693.  
  694.                 If (SX>=0)and(SX<=X_MAX)and(SY>=0)and(SY<=Y_MAX)
  695.  
  696.                     If POLE(SX,SY)=WOLNE
  697.  
  698.                         POLE(SX,SY)=POLE(X,Y)+1
  699.  
  700.                         If (SX=CEL_S)and(SY=CEL_Y)
  701.  
  702.                             JEST=True
  703.  
  704.                             WYNIK=POLE(SX,SY)
  705.  
  706.                         Else
  707.  
  708.                             ' jeszcze nie sprawdzony
  709.  
  710.                             KOLEJKA_WSTAW[SX,SY]
  711.  
  712.                         End If
  713.  
  714.                     End If
  715.  
  716.                 End If
  717.  
  718.                 End If
  719.  
  720.             End If
  721.  
  722.         End If
  723.  
  724.         KOLEJKA_NIEPUSTA : NIEPUSTA=Param
  725.  
  726.     Wend
  727.  
  728. End Proc[WYNIK]
  729.  
  730. <txt>W jaki sposób "wypisaê" najkrótszâ drogë? Po prostu jedziemy
  731. od koïca: najpierw ostatni, nastëpnie znajdujemy sâsiada o jeden
  732. mniejszego, póúniej o jeszcze jeden mniejszego i tak, aû dotrzemy
  733. do zera. Zwróê uwagë, ûe dla komputera îatwiej (szybciej) jest
  734. znaleúê najkrótszâ drogë w labiryncie peînym ôcian i zakamarków
  735. (poniewaû mniejsza jest wtedy powierzchnia do obliczania).
  736. Zupeînie inaczej czîowiek. Ten woli czystâ powierzchnië (bez
  737. ôcian).
  738.  
  739. A teraz, drogi Czytelniku, weú kartkë i dîugopis, a nastëpnie rób
  740. dokîadnie to, co kaûe algorytm. Ok? Najpierw narysuj sobie
  741. labirynt, a nastëpnie wypeîniaj kolejne polecenia programu.
  742. Myôlë, ûe to Ci wyjaôni jego dziaîanie.
  743.  
  744. -------------------- tu rys. 10 -------------------------------
  745.  
  746. Na tym miaîbym ochotë zakoïczyê ten juû trochë przydîugi i byê
  747. moûe z tego powodu nudnawy odcinek AMOS-a. Zauwaû, ûe programy
  748. tutaj zaprezentowane sâ wielce niedoskonaîe, z wielu wzglëdów
  749. (np. niezbyt pîynny, skokowy ruch obiektów). Popracuj nad nimi.
  750.