Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Komunikaty

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Tarlandil. Jeżeli został importowany poprawnie, usuń ten szablon!

WPROWADZENIE

W tym arcie postaram przybliżyć wam w jaki sposób można wykorzystać komunikaty (messages). Rozwiązania tu przedstawione będą nadawać się idealnie do gier typu RTS ;D, ale to wcale nie znaczy, że nie można ich wykorzystać gdzie indziej - a właściwie jeżeli się je dobrze zastosuje to znacznie powinno to ułatwić pisanie.

W tym arcie również będą informacje uzupełniające mojego poprzedniego arta: "Multiplayer w RTS'ach". 

KOMUNIKAT

Czyli pewna informacja, o określonej strukturze, mająca na celu poinformowanie o jakimś zdarzeniu, tak aby program mógł odpowiednio zareagować na wydarzenia. Komunikat powinien zawierać w sobie informacje:

  • jakiego jest typu
  • od kogo pochodzi
  • znaczniki (flagi)
  • ramkę (klatkę) gry w której ma zostać przetworzony
  • rozmiar
  • inne dane...

Rozmiar jest potrzebny aby móc na tym komunikacie operować, a później usunąć go z pamięci w całości - właśnie na te "inne dane" o których system zarządzania komunikatami zbyt dużo nie wie.

Przykład: Type PEMessage=^TEMessage; TEMessage= object //tylko po to aby móc w łatwy sposób dołączyć ten rekord do przez nas //definiowanych dwSize:DWORD; wFlags:WORD; wType:WORD; wSender:WORD; dwFrame:DWORD; end; Type PEMoveMessage=^TEMoveMessage; TEMoveMessage= object(TEMessage) //mamy już dołączone pola z TNEMEssage dwKto: DWORD; wGdzieX,wGdzieY:WORD; end;

Tutaj:

MoveMessage ma informować program, że jednostka, lub co kolwiek o Identyfikatorze dwKto w klatce gry o numerze dwFrame ma zacząć podążać w kierunku (wGdzieX,wGdzieY). 

DANE KTÓRE KAŻDY "KOMUNIKATYWNY" PROGRAM MUSI ZNAć

Przydałoby się, aby jak już program dostanie taki komunikat, we właściwej klatce, do przetworzenia, aby wiedział po co mu on i co ma z nim zrobić, i jak ma się z nim obchodzić. Czyli innymi słowy jak wykorzystać wFlags i wType.

Zdefiniujmy sobie np.: type DWORD=cardinal; const wf_system = 1; wf_immediate = 2; wf_engine = 4; // ..... = 8; // ..... =16; // itd. aż do 32768 wt_none=0; wt_move=1; wt_frameperm =2; wt_newframe =3; // .... =4; // .... =5; // itd. aż do 65535

I tak:

  1. ustawiona flaga system - będzie np. informował, że to nie jest dla "gry" tylko dla samego sytemu sterowania komunikatami.
  2. Immediate - oznacza, że ten komunikat ma zostać przetworzony zaraz po otrzymaniu przez system sterowania komunikatami, a nie dopiero w określonej klatce. W ten sposób mogą być wysyłane np. komunikaty od graczy do graczy (czyli nie mające bezpośredniego wpływu na grę).
  3. Engine - ze jest przeznaczona np. dla enginu gry, a nie jest to komunikat samej gry

Więcej przykładowych stałych nie będę przytaczał, gdyż nie ma to większego sensu - co najwyżej przy omawianiu niektórych efektów które można za pomocą takiego systemu komunikatów osiągnąć.

JAK PRACUJE POCZTA?

Co i po co, ale jak? Ja tu przedstawię według mnie najlepsze rozwiązanie przechowywania komunikatów (pod warunkiem, że nikt nie będzie wysyłał komunikatu który ma zostać przetworzony za np. 10000000 klatek. - Ale nie sądze, aby jakakolwiek gra miała więcej klatek gry (nie fpsow) więcej niż 100 na sekundę. Więc komunikat byłby przetworzony dopiero po 27 godzinach :D). Do tego celu zastosuję 2 typy kolejek, zrobionych za pomocy list dynamicznych (jak ktoś nie wie co to, niech się nie martwi - cały kod będzie tutaj). W kolejce pierwszego typu będą przechowywane komunikaty.
A w kolejce drugiego typu będą przechowywane kolejki komunikatów.

Teraz pewnie wielu z was zapyta: "A po co tak?, czemu nie można tego wszystkiego w jednej kolejce? Będzie prościej". Niby tak, ale przecież komunikaty mogą mieć różne klatki przetworzenia, a my chcemy aby to działało jak najszybciej. Gdy zastosujemy kolejki w kolejce to wkładanie komunikatu i wyciąganie pierwszego będzie bardzo szybkie. Natomiast W przypadku jednej kolejki wyciąganie będzie znacznie dłuższe - trzeba ten komunikat znaleźć.

Oto kawałek kodu z zaimplementowaną kolejką komunikatów (a właściwie to dwoma):

Type PEMessageQueue=^TEMessageQueue; TEMessageQueue= object frame:DWORD; //klatka dla ktorej sa przechowywane komunikaty First: PEMessage; //wskaźnik do elementu typu TEMessage z dołączonym na końcu Last: PEMessage; //pointerem Next: PEMessageQueue; //wskaźnik do następnej TEMessageQueue. closed: boolean; //czy juz nie mozna jeszcze dodawac komunikatow? procedure Add(XM:PEMessage); //dodaje do tej kolejki dopisując na koniec 4 bajtowy //pointer procedure Get(var XM:PEMessage); //pobiera pierwszy z kolejki, usuwając go z niej procedure Free(XM:PEMessage); // zwalnia Message wraz z 4 bajtowym pointerem procedure Init; procedure Clear; procedure PushNewFrameMsg; procedure SortMessages; end; type PEMessageSystem=^TEMessageSystem; TEMessageSystem= class immediate:PEMessageQueue; first:PEMessageQueue; last:PEMessageQueue; constructor Create; destructor destroy;override; procedure Add(EM:PEMessage); //dodaje do wlasciwej kolejki function Get:PEMessage; //pobiera pierwszy dostepny komunikat //trzeba jednak pamietac aby go potem zwolnic procedure FreeMsg(EM:PEMessage); //to samo co w TEMessageQueue procedure ProcessSysMsg(EM:PEMessage); procedure CreateNewFrame; function FindQueue(FR:cardinal):PEMessageQueue; function FirstFrame:cardinal; end; procedure TEMessageQueue.Add(XM: PEMessage); var x,a,n:pointer; begin if closed then raise Exception.Create('Zagubiony komunikat (Out-Of-Date) - Closed'); GetMem (x,XM^.dwSize+sizeof(pointer)); //pobieramy pamięć na przechowanie tego //komunikatu i robimy jego kopię - i tu się już przydaje rozmiar Move(XM^,x^,XM^.dwSize); if last<>nil then begin a:=pointer(cardinal(last)+last^.dwSize);//obliczamy gdzie powinien być wskaźnik w //ostatnim elemencie kolejki Move(x,a^,sizeof(pointer)); last:=x; end else begin first:=x; last:=x; end; n:=nil; x:=pointer(cardinal(x)+XM^.dwSize); //gdzie jest wskaźnik nowego elementu Move(n,x^,sizeof(pointer)); end; procedure TEMessageQueue.Clear; var t:PEMessage; begin while first<>nil do //dopoki cos jest begin Get(t); //pobieramy wskaznik Free(t); //zwalniamy pamiec end; end; procedure TEMessageQueue.Free(XM: PEMessage); begin FreeMem(XM,XM^.dwSize+sizeof(pointer)); //tyle ile wynosi rozmiar plus nasz wskaznik end; procedure TEMessageQueue.Get(var XM: PEMessage); var x:PEMessage; begin XM:=first; //pobieramy x:=first; x:=pointer(cardinal(x)+x^.dwSize); //liczymi gdzie jest wskaznik Move(x^,first,sizeof(pointer)); //ustawiamy kolejny element jako pierwszy if first=nil then last:=nil; //gdy pusta to pusta end; procedure TEMessageQueue.Init; begin first:=nil; //poczatkowe wartosci last:=nil; Next:=nil; closed:=false; end; procedure TEMessageQueue.PushNewFrameMsg; var EM:TEMessage; begin EM.dwSize:=sizeof(EM); //ustawiamy rozmiar EM.wFlags:=wf_engine or wf_system;//komunikat nalezy do enginu EM.wType:=wt_newframe; //info o nowej klatce EM.wSender:=0; //komunikat lokalny - w razie sortowania bedzie na poczatku EM.dwFrame:=Frame; //numer klatki Add(@EM); //do kolejki end; procedure TEMessageQueue.SortMessages; begin end; { TEMessageSystem } procedure TEMessageSystem.Add(EM: PEMessage); begin if (EM.wFlags and wf_immediate)>0 then begin immediate.Add(EM); end else begin if (first.frame>EM.dwFrame) and (last.frame>EM.dwFrame) and (last.frame>=first.frame) then //prawdopodobnie klatka opozniona, ktora nie powinna sie zdarzyc begin if (EM.dwFrame=1) and (first.frame>$7FFFFFFF) //nie opozniona, tylko przepelnil sie licznik :D - DWORD then begin while (last.frame<>1) do CreateNewFrame; //trzeba dorobic tyle klatek ile jest to konieczne FindQueue(EM.dwFrame).Add(EM);//i dodajemy do wlasciwej kolejki end else raise Exception.Create('Zagubiony komunikat (Out-Of-Date)'); end else //wszystko w porzadku begin if EM.dwFrame=0 then raise Exception.Create('Klatka nie-immediate ma klatke 0!'); while last.frame <> nil do //dopoki cos jest // tu były jakieś dziwne śmieci, skasowałem je - przyp. redaktora begin F:=First; First:=First^.next; //drugi w miejsce pierwszego F.Clear; //pierwszy usuwany Dispose(F); end; immediate.Clear; //immediate tez jest usuwany dispose(immediate); inherited; end; function TEMessageSystem.FindQueue(FR: cardinal): PEMessageQueue; var F:PEMessageQueue; begin result:=nil; if last.frame=FR then result:=last //sprawdzic warto else //jak nie to musimy poszukac begin F:=First; while (F<>last) and (result=nil) do begin if F.Frame=FR then result:=F; F:=F.next; end; end; end; function TEMessageSystem.FirstFrame: cardinal; begin result:=first.frame; end; procedure TEMessageSystem.FreeMsg(EM: PEMessage); begin FreeMem(EM,EM^.dwSize+sizeof(pointer)); //tyle ile wynosi rozmiar plus nasz wskaznikend; end; function TEMessageSystem.Get: PEMessage; var F:PEMessageQueue; begin first.Get(result); //pobieramy pierwsza wiadomosc if first.first=nil then //jak to byla ostatnia to trzeba ta klatke usunac begin if first.next=nil then CreateNewFrame; //jak nie ma nastepnej klatki to tworzymy pusta F:=first; first:=first.next; //juz jej w kolejce nie ma F.clear; //zwalniamy pamiec Dispose(F); end; if (result.wFlags and wf_system)>0 then ProcessSysMsg(result); end; procedure TEMessageSystem.ProcessSysMsg(EM: PEMessage); begin case EM.wType of wt_newframe: First.SortMessages; end; end;

Przedstawione powyżej fragmenty kodu razem tworzą pełny moduł (no tylko uses, interface i implementation - jeszcze brakuje). Kod wraz z przykładowym programem możesz sciągnąc go tutaj. I tym razem zawiodą się programujący w C(++) - ale dobry programista, który zna chociażby podstawy Pascala nie powinien mieć problemu z przepisaniem tego na C(++).

POSZCZEGÓLNYCH ZASTOSOWAń PRZYK£ADY...

A teraz czas na zastosowania takiego systemu obsługi komunikatów.
Po pierwsze czym się taki system cechuje:

  1. Bardzo szybki odczyt z kolejek
  2. Zapis: jeżeli dopisujemy do ostatniej utworzonej kolejki - bardzo szybki jeżeli nie: to czas jest zależny liniowo od ilości kolejek (wątpię, żeby ktoś w jakiejkolwiek grze miał więcej niż 100 kolejek na raz - czyli również jest szybki)
  3. Informuje automatycznie o rozpoczynaniu klatki.
  4. Umożliwia obsługę komunikatów które mają zostać przetworzone najszybciej jak tylko się da (immediate)
  5. Komunikaty są przechowywane w poszczególnych kolejkach na zasadzie kolejki FIFO (First In First Out)

Pewnie każdy uważny czytelnik, zauważył, że procedura SortMessages należąca do kolejki, jest pusta. Zostało to zrobione celowo (tak samo zmienna closed nigdzie nie jest ustawiana na true)- ponieważ czasem możemy chcieć aby komunikaty były przetwarzane dokładnie w takiej kolejności w jakiej zostały "wrzucone do skrzynki".

I zastosowanie (i chyba jedno z ważniejszych) czyli:

SYNCHRONIZACJA KOMPÓW NA KOMUNIKATACH

Tutaj właśnie w tym akapicie rozszerzę mój art o multiplayerze.

Wyobraźmy sobie, że każdy rozkaz wydany jakiejkolwiek jednostce, lub jakakolwiek czynność wykonana przez gracza, powoduje zmianę aktualnego toru przebiegu gry (póki gracz trzyma się z daleka od kompa, to wymiana danych nie jest potrzebna, gdyż każdy komp potrafi obliczyć co będzie w następnej klatce) jest wysyłana do wszystkich zainteresowanych jako właśnie wiadomość (np. potomny obiekt od TEMessage). Już sam TEMessage rozwiązuje nam problem wysyłania - tj. rozróżniania które dane do czego należą - gdyż zawiera w pierwszych bajtach informacje o swoim rozmiarze. Wszyscy którzy otrzymali taki komunikat (ten co wysyłał też oczywiście) robią MessageSystem.Add(@Nowy Komunikat). I na razie o nim zapominają.

Dalej każdy komp gdy przetwarza daną klatkę, przetwarza po kolei wszystkie komunikaty związane z tą klatką (oczywiście, jeżeli były jakieś komunikaty typu Immediate to je przetwarza na samym początku). Więc wszyscy wykonują to samo (zakładam na razie, że wszyscy robią takim w takim samym tempie i otrzymują wiadomości w dokładnie takiej samej kolejności). Ponieważ robią to samo, to mają taki sam stan i te same dane, więc są zsynchronizowane. Ilość danych wysyłanych jest bardzo mała (taki komunikat o rozkazie ruch może zajmować z 30B - a to jest prawie nic - modem w zupełności wystarczy takiej grze). Sposób pakowania danych i takiego ich doboru aby ilość danych była jak najmniejsza nadaje się na osobny artykuł, w związku z tym pominę ten temat.

Więc oprócz tych dwóch założeń wszystko już jest ok. Ale nie zawsze tak jest może okazać się, że jeden komunikat dojdzie do kogoś wolniej niż inny, a do kogoś innego szybciej, i co wtedy, kompy zrobią co innego i wszystko siada. Jak się tego pozbyć. Po pierwsze wiemy, że na pewno komunikaty od jednego kompa będą wzgleem siebie w dobrej kolejności. W taki razie wystarczy te komunikaty tuż przed przetworzeniem danej klatki posortować, ze względu na nadawcę. I już każdy ma to samo - i to jest zadanie procedury SortMessages.

Kolejna sprawa. A co będzie gdy jakiś komp już będzie na 1520 klatce, a tu nagle komunikat z 567 klatki? Też siądzie wszystko. Jak tego uniknąć?: Wystarczy że, każdy komputer np. co 10 klatek wysyła wszytkim zezwolenie na dojście do klatki o 30 wyższej niż ta którą ma ten co wysyła. A wykonanie jakiejś klatki jest tylko możliwe pod warunkiem że wszyscy wyrazili na nią zgodę. Wysyłane rozkazy są z wyprzedzeniem 31 klatkowym. Wtedy nikt niczego nie przekroczy. Taki komunikat zajmuje kilka bajtow. Więc łącza też obciążać specjalnie nie będzie. A wszystko dzięki komunikatom.

Ustalenie co ile klatek należy wysyłać taki komunikat i na ile klatek do przodu, można pozostawić graczowi, lub ustawiać na bieżąco w zależności od tego jaki jest lag itp.

Uwaga, jeżeli ktoś ma zamiar stosować liczby losowe, to wystarczy tuż przed gra zsynchronizować (np. host narzuci wszystkim) stany zmiennej RandSeed.

Oto kod przykładowej procedury sortującej: procedure TEMessageQueue.SortMessages; var msgs,msgs2:PEMessageArray; s,i:cardinal; f,x:PEMessage; procedure sort(s,e:integer); //merge-sort var i,j,k,p:integer; begin if s>=e then exit; p:=(s+e) div 2; sort(s,p); //wywolanie rekurencyjne sort(p+1,e); i:=s; j:=p+1; k:=0; while (i<=p) or (j<=e) do //scalanie begin if (i>p) then begin msgs2[k]:=msgs[j]; inc(j); inc(k); end else if (j>e) then begin msgs2[k]:=msgs[i]; inc(i); inc(k); end else begin if msgs[i].wSender<=msgs[j].wSender then begin msgs2[k]:=msgs[i]; inc(i); inc(k); end else begin msgs2[k]:=msgs[j]; inc(j); inc(k); end; end; end; for i:=0 to k-1 do msgs[s+i]:=msgs2[i]; //juz posortowane z powrotem do talbicy end; begin s:=0; f:=first; while f<>nil do begin inc(s); x:=pointer(cardinal(f)+f.dwSize); Move(x^,f,sizeof(pointer)); end; //liczymy ile jest komunikatow GetMem(msgs,s*sizeof(pointer)); GetMem(msgs2,s*sizeof(pointer)); i:=0; while first<>nil do begin Get(msgs[i]); //wrzucamy je do tablicy inc(i); end; if s>0 then begin Sort(0,s-1); //sortujemy for i:=0 to s-1 do begin Add(msgs[i]); //i z powrotem do kolejki Free(msgs[i]); end; end; FreeMem(msgs,s*sizeof(pointer)); FreeMem(msgs2,s*sizeof(pointer)); closed:=true; end;

II zastosowanie czyli:

REPLAY'E

Mając taki system gry, oparty na komunikatach, że wszystkie rozkazy zmieniające aktualny tor przebiegu gry są komunikatami, można w bardzo łatwy sposób wprowadzić zapis gry. Wystarczy tuż po odebraniu komunikatu z kolejki, a przed tego przetworzeniem, przekazać go odpowiedniej procedurze filtrującej, która jeżeli uzna, że ten komunikat jest potrzebny do odtworzenia przebiegu rozgrywki, automatycznie zapisze go do pliku.

Procedure filtr(EM:PEMessage); begin if (EM.wFlags and wf_game)>0 then SaveToFile(EM) else case EM.wType of wf_chat: SaveToFile(EM); //...itp. end; end;

III zastosowanie czyli:

PORZ¡DEK W NASZYM ENGINE:

Chyba, każdy wie, że w zagmatwanym kodzie ciężko się dokonuje poprawki i dodaje nowe rzeczy. W niektórych grach (zależy od programisty), można podzielić czas na różne fazy. Np. Przetworzenie wejścia gracza; przetworzenie AI; wysłanie danych przez siec; przetworzenie nowych rozkazów dla jednostek; obliczenie nowych danych, współrzędnych i stanów; obsługa dźwięków i muzyki; renderowanie grafiki;

Teraz, aby wszystko było wykonywane wtedy kiedy być powinno (w większości przypadków różnicy może nie być czy wejście użytkownika, lub inne rzeczy zostaną wykonane / przetworzone w dowolnym momencie czy też w wyznaczonym do tego czasie, ale w przypadkach skrajnych - np. LAAAG, gracz opuszcza grę, coś znowu winda zaczęła wariować i trzeba trochę przeczekać ;D; albo po prostu programista gdzieś zrobił błąd; i wiele różnych rzeczy które mi teraz do głowy nie przychodzą. - może się okazać że coś gdzieś się wysypie. Jeżeli mamy teraz porządek i wiemy co kiedy jest robione, mamy logowanie komunikatów, będziemy w stanie szybko znaleźć błąd / problem i go zlikwidować, bądź ominąć. A wystarczy tylko w odpowiednio wyznaczonym czasie pobierać odpowiednie komunikaty i je przetwarzać.

Tutaj mamy również możliwość kontroli czasowej wykonywanych poszczególnych faz. A niektórym przyznać odpowiednie ilości czasu. Po upływie tego czasu faza przestaje przetwarzać komunikaty, które poczekają do następnego razu (no chyba że komunikatów jest więcej np. niż 100 to przetwarza tyle aby była bezpieczna ilość).

IV zastosowanie, czyli

ARTIFICIAL INTELIGENCE

Ten temat również nadaje się na arta, a nawet kilka, więc przedstawię to tylko od strony komunikatów, bo o tym jest ten art..

W wielu grach, a w szczególności RTS'ach, decyzje komputera można uzależnić od aktualnego zadania. Np. To co ma budować może znajdować się w kolejce, a on to po kolei jak tylko może robi. Tak samo, planowanie ataków, czy innych działań, może odbywać się w ten sposób, że są pewne rozkazy - zadanie przechowywane w kolejce i kiedy potrzeba są one wykonywane.

Ale może się zdarzyć coś takiego: mamy w kolejce: zbuduj: zelaot.zealot,dragoon,zealot.

A tutaj nagle kończą nam się wolne sloty (miejsca na jednostki, lub jedzonko, lub prądu za mało, jak tam kto co woli). I trzeba dobudować Pylona. Dodanie go do kolejki budowy nie ma najmniejszego sensu, bo AI padnie i nic nie będzie robić. Ale np. Gdyby ustawić Pylonowi większy priorytet to byłoby wszystko OK.

W takim razie przydałaby się nam jakaś sprawna kolejka priorytetowa, która wyciąga komunikaty, ale zaczynając od tych które mają wyższe priorytety, niezależnie od tego w jakiej kolejności były wrzucane. Kod:

type PAIMessage=^TAIMessage; TAIMessage= object(TEMessage) wPriority:WORD; end; type PPriorityQueue=^TPriorityQueue; TPriorityQueue= //to bedzie kolejka oparta na kopcu czasy operacji wynosza O(lg n) object tab:array[1..4096] of PAIMessage; size:cardinal; procedure Add(AIM:PAIMessage); function Get:PAIMessage; procedure FreeMsg(AIM:PAIMessage); procedure init; procedure clear; end; procedure TPriorityQueue.Add(AIM: PAIMessage); var n:integer; x:PAIMessage; begin inc(size); GetMem (tab[size],AIM^.dwSize); //pobieramy pamięć na przechowanie tego //komunikatu i robimy jego kopię //bez pointera na koncu bo trzymamy komunikaty w tablicy Move(AIM^,tab[size]^,AIM^.dwSize); n:=size; while (n>1) and (tab[n].wPriority>tab[n shr 1].wPriority) do begin x:=tab[n]; //zamieniamy tab[n]:=tab[n shr 1]; tab[n shr 1]:=x; n:=n shr 1; end; end; procedure TPriorityQueue.clear; var i:integer; begin for i:=1 to size do FreeMsg(tab[i]); //usuwamy wszystko size:=0; end; procedure TPriorityQueue.FreeMsg(AIM: PAIMessage); begin FreeMem(AIM,AIM^.dwSize); //tyle ile wynosi rozmiar end; function TPriorityQueue.Get: PAIMessage; var a:integer; n:integer; x:PAIMessage; begin result:=nil; if size=0 then exit; result:=tab[1]; tab[1]:=tab[size]; dec(size); n:=1; a:=1; while (n shl 1<=size) and (a>0) do begin a:=0; if tab[n].wPriority < tab[n shl 1].wPriority then a:=1; //lewy syn if ((n shl 1)+1<=size) then //prawy syn begin if (a=0) and (tab[n].wPriority < tab[(n shl 1)+1].wPriority) then a:=2; if (a=1) and (tab[n shl 1].wPriority < tab[(n shl 1)+1].wPriority) then a:=2; end; if a=1 then //zamieniamy z lewym synem begin x:=tab[n]; tab[n]:=tab[n shl 1]; tab[n shl 1]:=x; n:=n shl 1; end; if a=2 then //zamieniamy z prawym synem begin x:=tab[n]; tab[n]:=tab[(n shl 1)+1]; tab[(n shl 1)+1]:=x; n:=(n shl 1)+1; end; end; end; procedure TPriorityQueue.init; begin size:=0; //poczatkowa wartosc end;

Opis algorytmu: Tutaj zastosowałem kopiec. Kopiec jest to drzewo binarne (ojciec ma zawsze dwóch synów: lewego i prawego - wyjątkiem są te w ostatnim rzędzie na samym dole). Takie drzewo można zapisać w tablicy. Wtedy węzeł o numerze n ma: lewego syna z numerem n*2, prawego syna z numerem n*2+1, i ojca z numerem n/2. Ten kopiec charakteryzuje się tym, że każdy ojciec ma wyższy priorytet od każdego z jego synów, więc najwyższy priorytet ma węzeł numer 1. Jeżeli dodajemy do kopca jakiś węzeł, to musimy go przesuwać w górę, aż te właściwości kopca będą spełnione. Jeżeli wyciągamy coś z kopca, to ostatni element idzie na miejsce pierwszego, a potem jest zsuwany w dół też aby zachowane były wszystkie właściwości kopca (podczas zsuwania jest zamieniany z tym synem który ma największy priorytet).

Przykład kopca:

                                     12
                              /            \ 
                            10              8
                          /    \          /  \ 
                        3       9       2     5
                      /   \    /  \     /
                     2     1  2  5   1 

EPILOG

To już wszystko w tym arcie. Mam nadzieję, że ktoś się czegoś nauczył, a w szcególności robienia kolejek dynamicznych, oraz kolejek priorytetowych.

Pytania, uwagi, i inne pochwały proszę kierować na Forum Warsztatu, bądź

Jeżeli byłoby wiele osób zainteresowanych to również jestem skłonny napisać art./kurs dotyczący struktur danych i algorytmów. Również po algorytmy odsyłam do "Wprowadzenie do algorytmów" Cormen'a

Autor: Tarlandil
Data: 23 marca 2001

Tekst dodał:
Adam Sawicki
01.04.2006 15:52

Ostatnia edycja:
Adam Sawicki
01.04.2006 15:52

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 01.04.2006 15:52 Adam Sawicki 26.07 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)