------------------------------------------------------------- Ustawiê TAB=3 w listingach !Rys.n! - w miarë moûliwoôci wstawiê tutaj rys. n ------------------------------------------------------------- NAJKRÓTSZA DROGA... W ostatnim odcinku AMOS-a pokazaîem, jak moûna sprawdziê, czy istnieje droga z jednego punktu "labiryntu" do drugiego. Tylko komu to potrzebne? Wszak wszystkim wiadomo, ûe stwory z gier komputerowych nie sâ wyposaûone nawet w jeden mililitr rozumu, a co wiëcej -- nie potrzebujâ go. W grach tego typu liczy sië przede wszystkim dobra grafika, dúwiëk i muzyka oraz szybki ruch obiektów. Ûeby to osiâgnâê, wszystkie algorytmy sterujâce sprajtami powinny byê jak najprostsze. Jakie? Krzysztof Prusik Na przykîad takie: Spróbuj iôê w stronë celu (oblicz kierunek) Czy moûna tam iôê? TAK No to rusz obiekt NIE To spróbuj chwilowo skrëciê na lewo od kierunku do celu Czy moûna? TAK No to rusz obiekt NIE To spróbuj skrëciê na prawo od kierunku do celu Czy moûna? TAK To rusz obiekt NIE ... --------------!Rys.1!---------------------- Zaletâ tego algorytmu jest szybkoôê dziaîania, a wadâ to, ûe nie zawsze dziaîa poprawnie. Otóû czasami moûe dojôê do zapëtlenia (rys. 2.), tj. sytuacji, w której obiekt bëdzie sië poruszaî tam i z powrotem, próbujâc odnaleúê drogë do celu. ------------------!Rys.2 - zapëtlenia!-------------------- Nie jest to jednak wielka wada, gdy dotyczy miîych potworków ze strzelawek, które przecieû mogâ sië poruszaê, jak chcâ. Nie gniewam sië, gdy grajâc w gierkë widzë, jak mój przeciwnik, ûâdny krwi, miota sië jak szalony, próbujâc do mnie dotrzeê, ale nie moûe, ze wzglëdu na prosty algorytm ruchu. Gorzej, gdy rzecz dotyczy mnie. W sîawnym Syndycate kierujemy agentami za pomocâ myszki, klikajâc na odpowiednie miejsce ekranu. Poniewaû jednak poruszajâ sië oni wedîug tego "biednego" algorytmu, czasem zdarza sië, ûe biegajâ w kóîko, nie umiejâc znaleúê wyjôcia z "labiryntu" domów. Koïczâc wywody teoretyczne, zakodujmy wreszcie ten banalny algorytm, uûywajâc do pomocy AMOS-a. ' ProstyRuch (C) 1995 By Krzysztof Prusik ' Global OBIEKT_X,OBIEKT_Y Global CEL_X,CEL_Y ' ---------------------- wspóîrzëdne obiektu OBIEKT_X=10 OBIEKT_Y=10 ' ---------------------- wspóîrzëdne celu CEL_X=20 CEL_Y=15 ' ---------------------- gîówna pëtla Repeat OBIEKT_RUSZ OBIEKT_WYSWIETL ' pëtlë powtarzamy tak dîugo, aû obiekt ' znajdzie sië w celu Until (OBIEKT_X=CEL_X) and (OBIEKT_Y=CEL_Y) ' ----------------------- procedury... Programik jest prosty, prawda? Znowu caîâ robotë zwalamy na gîównâ procedurë (OBIEKT_RUSZ), której zadaniem bëdzie obliczenie nowych wspóîrzëdnych (OBIEKT_X,OBIEKT_Y). Jak to zrobimy? Ano, wedîug schematu zamieszczonego na poczâtku artykuîu, tj. najpierw obliczymy poûâdany kierunek ruchu obiektu (rys. 3.), a nastëpnie postaramy sië w miarë moûliwoôci (jeôli bëdzie droga) przemieôciê obiekt w stronë celu. ---------------!Rys.3 - kierunek ruchu!------------------------- Myszka z poprzedniego artykuîu potrafiîa sië przemieszczaê jedynie w pionie i w poziomie (rys. 4.). -----------------------!Rys.4 - przemieszczanie w pionie i poziomie! Tym razem utrudnimy sobie zadanie i umoûliwimy jej ruch równieû "po skosie" (rys. 5.). ---------------------------!Rys.5 - równieû po skosie! No dobrze, a oto ta "skomplikowanie prosta" procedura w AMOS-ku: Procedure OBIEKT_RUSZ ' przemieszcza obiekt o wsp. OBIEKT_X,OBIEKT_Y ' o jednâ pozycjë w kierunku CEL_X,CEL_Y ' (oczywiôcie w miarë moûliwoôci) ' ' --------------- kierunek ruchu obiektu w X i Y RX=Sgn(CEL_X-OBIEKT_X) RY=Sgn(CEL_Y-OBIEKT_Y) '---------------- czy moûna przesunâê obiekt o RX,RX? CZY_MOZNA[RX,RY] : MOZNA=Param If MOZNA ' czyli moûna obiekt tutaj przesunâê, wiëc przesuwamy OBIEKT_PRZESUN[RX,RY] ' i wychodzimy z procedury Pop Proc End If ' nie moûna, wiëc badamy dalej CZY_MOZNA[RX,0] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[RX,0] : Pop Proc End If ' i jeszcze raz... aû do skutku CZY_MOZNA[0,RY] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[0,RY] : Pop Proc End If CZY_MOZNA[-RX,RY] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[-RX,RY] : Pop Proc End If CZY_MOZNA[RX,-RY] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[RX,-RY] : Pop Proc End If CZY_MOZNA[0,-RY] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[0,-RY] : Pop Proc End If CZY_MOZNA[-RX,0] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[-RX,0] : Pop Proc End If CZY_MOZNA[-RX,-RY] : MOZNA=Param If MOZNA OBIEKT_PRZESUN[-RX,-RY] : Pop Proc End If ' skoro tutaj dotarliômy, to znaczy, ûe obiektu ' nigdzie nie moûna przesunâê End Proc Procedure CZY_MOZNA[RX,RY] ' bada, czy moûna przesunâê obiekt w kierunku RX,RY ' czyli po prostu mówi, czy pole ' OBIEKT_X+RX,OBIEKT_Y+RY ' znajduje sië w obrëbie tablicy i czy jest wolne ' '--------------- potencjalne wsp. obiektu NX=OBIEKT_X+RX NY=OBIEKT_Y+RY '--------------- pesymistyczne zaîoûenie MOZNA=False If (NX>=0) and (NX<=X_MAX) If (NY>=0) and (NY<=Y_MAX) If POLE(NX,NY)=WOLNE MOZNA=True End If End If End If End Proc[MOZNA] Procedure OBIEKT_PRZESUN[RX,RY] ' przesuwa obiekt w kierunku RX,RY Add OBIEKT_X,RX Add OBIEKT_Y,RY ' pokaû obiekt na ekranie End Proc Procedure OBIEKT_WYSWIETL ' wyôwietla obiekt w punkcie o wspóîrzëdnych ' OBIEKT_X,OBIEKT_Y POKAZ_KURSOR[OBIEKT_X,OBIEKT_Y] End Proc Wszystko jasne? Nie pociemniaîo Ci w oczach? No to doprowadú do odpalenia programu. Oczywiôcie nie zapomnij, ûe najpierw trzeba zbudowaê labirynt (procedura opisana w poprzednim artykule), oraz m.in. zdefiniowaê procedurkë POKAZ_KURSOR. A teraz wykonajmy maîy Eksperyment Sprawmy, ûeby ruchomy byî nie tylko obiekt, ale równieû cel. Jak to zrobiê? Dopiszmy nowâ procedurë na przesuwanie celu (i umieôêmy jej wywoîanie w pëtli , tuû za OBIEKT_RUSZ). Procedure CEL_RUSZ ' losowy kierunek ruchu RX=1-Rnd(2) : Rem moûe byê -1,0 albo 1 RY=1-Rnd(2) : Rem moûe byê -1,0 albo 1 ' przesuï Add CEL_X,RX Add CEL_Y,RY End Proc Procedure CEL_WYSWIETL ... End Proc Procedurka CEL_WYSWIETL równieû nie jest zbyt trudna do napisania (analogiczna do POKAZ_KURSOR), jednak celowo jej tutaj nie zamieôciîem, aby Ci, drogi Czytelniku, nie robiê w gîowie sieczki. Otóû wiedza podana na tacy nie jest zapamiëtywana i robi uczâcemu sië wiëcej szkody niû poûytku. Dlaczego tak jest? Bo czytajâc dokîadne porady typu "jak to zrobiê", nie uûywamy czynnie wîasnego umysîu, lecz przyswajamy materiaî metodâ "zrozumieê-zapomnieê". Aby nauczyê sië programowaê, naleûy uruchomiê wîasne procesy myôlowe. Czytajâc programy zamieszczone w artykuîach, staraj sië podchodziê do nich w sposób: "a jak ja bym to napisaî?". Ûeby Ci w tym pomóc, staram sië jak najczëôciej zostawiaê furtkë dla Twojej kreatywnoôci i indywidualnoôci. Czy teraz nie gniewasz sië, ûe nie zamieôciîem peînej procedury CEL_WYSWIETL? Dla uîatwienia dodam, ûe najlepiej skorzystaê z dobrodziejstw, jakie oferujâ sprite'y i boby. Czy juû uruchomiîeô program? Ômieszne, prawda? Dwa sprite'y ganiajâce sië po ekranie... Co zrobiê, ûeby ich byîo wiëcej? Minigierka Napiszmy program, który wstrzyma sîoïce, a wzruszy stadko obiektów. Taka zabawa: pierwszy obiekt goni drugi, drugi -- trzeci, trzeci -- czwarty... ostatni -- pierwszy. Powinno byê ciekawie. Lubië programowaê! Szybko, zróbmy to! Na poczâtku trzeba zadeklarowaê tablicë wspóîrzëdnych obiektów. LICZBA_OBIEKTOW=4 : Rem --- na poczâtek wystarczy Dim OBIEKT_X(LICZBA_OBIEKTOW) Dim OBIEKT_Y(LICZBA_OBIEKTOW) Global OBIEKT_X(),OBIEKT_Y() I to wîaôciwie prawie wszystkie modyfikacje w gîównym listingu. Teraz trzeba kaûdâ z procedurek operujâcych na obiektach zmodyfikowaê tak, aby w zaleûnoôci od parametru I, przesuwaîa obiekt I. Potrafisz to zrobiê sam? Oczywiôcie w gîównym listingu, w pëtli , zamiast: OBIEKT_RUSZ OBIEKT_WYSWIETL trzeba bëdzie wstawiê: For I=1 To LICZBA_OBIEKTOW OBIEKT_RUSZ[I] OBIEKT_WYSWIETL[I] Next ------------------!Rys.6 - rysunek, z czterema ganiajâcymi sië sprite-ami! Czy teraz wszystko jasne? Mam cichâ nadziejë... Czy juû zmodyfikowaîeô i odpaliîeô program? Teraz to dopiero zabawa, co? Budujesz labirynt, a obiekty ganiajâ sië jak gîupie. Najkrótsza droga Tytuî artykuîu sugerowaî, ûe caîy odcinek AMOS-a poôwiëcony bëdzie wyszukiwaniu NAJKRÓTSZEJ drogi, a nie jakiemuô tam ograniczonemu algorytmowi, który nawet nie jest w stanie stwierdziê, czy dana droga w ogóle istnieje. Dlaczego zaczâîem od takiego wstëpu? Poniewaû chciaîem pokazaê, ûe sâ algorytmy bardzo szybkie (i zarazem proste), tj. takie, które nie tracâ czasu na zbyt wiele obliczeï, lecz majâ, niestety, wiele ograniczeï (zapëtlenia). Algorytm z poprzedniego artykuîu jest juû bardziej inteligentny (potrafi stwierdziê, czy dana droga istnieje i na dodatek odnajduje jâ), lecz juû nie jest aû tak szybki. Ten zaô algorytm, którym sië zajmiemy teraz, jest, niestety, powolny (na pocieszenie dodam, ûe lepszego nie da sië juû napisaê). Dlaczego? Bo wyszukujâc najkrótszâ drogë trzeba porównaê wszystkie inne, czyli przelecieê caîâ tablicë ze zdefiniowanym labiryntem (rys. 7.). --------------------!Rys.7 - kilka dróg! Oczywiôcie nie ma sensu sprawdzaê kilka razy danego odcinka drogi (rys. 8.). ---------------------!Rys.8 - drogi nachodzâ na siebie! Nie wspomnë juû o zapëtleniach. Chyba teraz jest juû jasne, ûe ten algorytm nie jest banalny? No wiëc pytanie za sto punktów: Jak go napisaê? Trudne, prawda? No wiëc inne pytanie: Jak rozwiâzaê zadanie przy uûyciu kartki i dîugopisu (ewentualnie oîówka, moûe byê równieû mazak)? Geniusze, do dzieîa! Myôleê, myôleê! (Patrz pomocniczy rysunek 9.). ---------------------!Rys.9 - labirynt pomocniczy do myôlenia! No i jak? Przyznam sië szczerze, ûe gdy pierwszy raz usîyszaîem treôê zadania, sam nie potrafiîem go zrobiê. Tak wiëc wszyscy, którym sië to równieû nie udaîo, niech nie rozpaczajâ, tylko posîuchajâ czîowieka oôwieconego. Dîugoôê drogi, to liczba kratek, które musi pokonaê obiekt, docierajâc do celu (pomijajâc zapëtlenia). Zwykle, gdy rozwiâzujemy jakiekolwiek zadanie, dzielimy je na kawaîeczki. No wiëc tak: ruszamy obiekt o jedno pole w kaûdâ stronë (oczywiôcie tylko tam, gdzie moûna) i wpisujemy w to pole odlegîoôê od punktu startu. Dla kaûdego z pól, gdzie stanëliômy, wykonujemy to samo. I tyle! Proste? Jeôli nie, to spójrz na rys. 10. Oto nieco inne wyjaônienie: W punkcie startu wpisujemy 0. Bierzemy wszystkie punkty odlegîe o jeden od startu i wpisujemy tam jedynkë. Bierzemy wszystkie punkty odlegîe o dwa (czyli jeszcze nie zapisane i odlegîe od ostatnio zapisanych punktów o jeden) i wpisujemy dwójkë. I tak dalej, i tak dalej... Czy juû potrafiîbyô napisaê taki program? Zastanów sië nad tym... Kolejka Utrudnieniem jest to, ûe trzeba skorzystaê z pewnej (byê moûe dla Ciebie nowej) struktury danych, jakâ jest kolejka. Potrzebna jest nam ona do przechowywania wspóîrzëdnych punktów odlegîych od startu o n. Jak ona dziaîa? Dokîadnie tak samo, jak w dawnych komunistycznych czasach kolejki po miësko. "Nowi" przychodzâ na koniec, "zaîatwieni" odchodzâ z poczâtku. Ok? Implementacja takiej kolejki w AMOS-ie moûe wyglâdaê np. tak: ' Kolejka (C) 1995 By Krzysztof Prusik ' KOLEJKA_N=MAX_X : Rem --- rozmiar kolejki (chyba wystarczy...) ' --------- kolejka Dim KOLEJKA_X(KOLEJKA_N-1),KOLEJKA_Y(KOLEJKA_N-1) Global KOLEJKA_X(),KOLEJKA_Y(),N, ' --------- pozycja pierwszego i ostatniego el-tu kolejki Global KOLEJKA_PIERWSZY,KOLEJKA_OSTATNI ' --------- liczba elementów kolejki Global KOLEJKA_ILE '---------- bieûâce zmienne Global X,Y Procedure KOLEJKA_INICJUJ ' inicjalizuje kolejkë wspóîrzëdnych punktów KOLEJKA_ILE=0 KOLEJKA_PIERWSZY=0 KOLEJKA_OSTATNI=KOLEJKA_N-1 End Proc Procedure KOLEJKA_NIEPUSTA ' sprawdza, czy kolejka nie jest pusta If KOLEJKA_ILE>0 NIEPUSTA=True Else NIEPUSTA=False End If End Proc[NIEPUSTA] Procedure KOLEJKA_POBIERZ ' usuwa pierwsze wspóîrzëdne z kolejki ' i podstawia podstawia pod zmienne X,Y KOLEJKA_NIEPUSTA : NIEPUSTA=Param If NIEPUSTA Dec KOLEJKA_ILE X=KOLEJKA_X(KOLEJKA_PIERWSZY) Y=KOLEJKA_Y(KOLEJKA_PIERWSZY) KOLEJKA_PIERWSZY=(KOLEJKA_PIERWSZY+1)mod KOLEJKA_N Else Print "Kolejka pusta!" End End If End Proc Procedure KOLEJKA_WSTAW[X,Y] ' Wstawia wspóîrzëdne X,Y do kolejki If KOLEJKA_ILE=KOLEJKA_N Print "Kolejka peîna!" End Else KOLEJKA_OSTATNI=(KOLEJKA_OSTATNI+1)mod KOLEJKA_N KOLEJKA_X(KOLEJKA_OSTATNI)=X KOLEJKA_Y(KOLEJKA_OSTATNI)=Y Inc KOLEJKA_ILE End if End Proc Na specjalne ûyczenie Czytelników (listy) w nastëpnych artykuîach mogë opisaê dokîadniej "kolejkowâ" strukturë danych, na razie jednak wystarczy, jeôli bëdziesz wiedziaî, ûe dysponujemy operacjami, które robiâ, co robiâ (patrz rys. 11.). A oto algorytm (zaimplementowany w AMOS-ie) wyszukujâcy najkrótszâ drogë. ' NajkrótszaDroga (C) 1995 By Krzysztof Prusik ' WOLNE=-1 : Rem --- pole wolne SCIANA=-2 : Rem --- sciana Global WOLNE,SCIANA ...tu wstawiê obsîugë kolejki ...inicjalizacjë labiryntu (tablica POLE()) ...itp. Procedure NAJKROTSZA_DROGA[_START_X,_START_Y,CEL_X,CEL_Y] ' wyszukuje najkrótszâ drogë od punktu ' o wspóîrzëdnych _START_X,_START_Y ' do punktu CEL_X,CEL_Y ' w tym celu przeszukuje tablicë POLE() ' wypeînionâ wartoôciami: ' -1 (WOLNE) - tam, gdzie pole jest wolne ' -2 (SCIANA) - tam, gdzie jest ôciana ' po wykonaniu procedury, w zmiennej WYNIK ' zawarta bëdzie dîugoôê najkrótszej drogi ' lub -1, gdy takiej nie ma. ' '------------------- pesymistyczne zaîoûenie WYNIK=-1 JEST=False KOLEJKA_INICJUJ X=_START_X Y=_START_Y If POLE[_START_X,_START_Y]=WOLNE POLE[X,Y]=1 : Rem odlegîoôê jeden If (X=CEL_X) and (Y=CEL_Y) JEST=True WYNIK=1 Else ' wstawiamy pierwszy punkt do kolejki KOLEJKA_WSTAW[X,Y] End If Else Print "Pole powinno byê wolne!" End End If '--------------- zaczynamy pëtlë KOLEJKA_NIEPUSTA : NIEPUSTA=Param While NIEPUSTA and Not JEST KOLEJKA_POBIERZ I=1 For RX=-1 To 1 For RY=-1 To 1 If Not ((RX=0)and(RY=0)) SX=X+RX SY=Y+RY If (SX>=0)and(SX<=X_MAX)and(SY>=0)and(SY<=Y_MAX) If POLE(SX,SY)=WOLNE POLE(SX,SY)=POLE(X,Y)+1 If (SX=CEL_S)and(SY=CEL_Y) JEST=True WYNIK=POLE(SX,SY) Else ' jeszcze nie sprawdzony KOLEJKA_WSTAW[SX,SY] End If End If End If End If End If End If KOLEJKA_NIEPUSTA : NIEPUSTA=Param Wend End Proc[WYNIK] W jaki sposób "wypisaê" najkrótszâ drogë? Po prostu jedziemy od koïca: najpierw ostatni, nastëpnie znajdujemy sâsiada o jeden mniejszego, póúniej o jeszcze jeden mniejszego i tak, aû dotrzemy do zera. Zwróê uwagë, ûe dla komputera îatwiej (szybciej) jest znaleúê najkrótszâ drogë w labiryncie peînym ôcian i zakamarków (poniewaû mniejsza jest wtedy powierzchnia do obliczania). Zupeînie inaczej czîowiek. Ten woli czystâ powierzchnië (bez ôcian). A teraz, drogi Czytelniku, weú kartkë i dîugopis, a nastëpnie rób dokîadnie to, co kaûe algorytm. Ok? Najpierw narysuj sobie labirynt, a nastëpnie wypeîniaj kolejne polecenia programu. Myôlë, ûe to Ci wyjaôni jego dziaîanie. -------------------- tu rys. 10 ------------------------------- Na tym miaîbym ochotë zakoïczyê ten juû trochë przydîugi i byê moûe z tego powodu nudnawy odcinek AMOS-a. Zauwaû, ûe programy tutaj zaprezentowane sâ wielce niedoskonaîe, z wielu wzglëdów (np. niezbyt pîynny, skokowy ruch obiektów). Popracuj nad nimi.