Fastbar
Powrót do strony głównej
Trzymaj pliki na gmclan.org!
Game Maker w pytaniach i odpowiedziach!
Polska dokumentacja
Tabela wyników ligi 24
Pobierz GM
Akademia GMCLANu
Kategorie bazy artykułów
Artykuły -> Kąciki programowania -> Algorytmy i struktury danych
Treść artykułu
Wprowadzenie do teorii grafów - cz. 1
autor: Platyna (24.05.09)
Wstęp do teorii grafów - cz. 1

Wprowadzenie
     Witam w pierwszej części artykułu mającego na celu wprowadzenie czytelnika do zagadnienia teorii grafów. Przedstawione tu zostaną podstawowe pojęcia dotyczące grafów, trochę teorii oraz kilka przykładów ich zastosowania. Czyli w skrócie: Z czym to się je. ;)
     Na początku należy powiedzieć, co to w ogóle jest teoria grafów? Według Wikipedii, jest to dział matematyki zajmujący się badaniem własności grafów. Ale w takim razie czym jest graf? W dużym uproszczeniu, jest to zbiór wierzchołków oraz łączących je krawędzi. Bardziej formalnie jest to pewna struktura danych, czyli sposób uporządkowania informacji w komputerze. Rysunek 1 przedstawia przykładowy spójny graf. Ma on 7 wierzchołków i 8 krawędzi.


Podstawowe pojęcia dotyczące grafów
     Wiem, że nikt nie lubi masy teorii no ale niestety trzeba się z tym zapoznać. Na szczęście nie będzie tu żadnych pogiętych, wymyślnych nazw tylko bardzo intuicyjne pojęcia. :)

Rodzaje grafów:
Graf spójny - jest to graf w którym poruszając się po krawędziach możemy znaleźć ścieżkę między dowolną parą wierzchołków.
Graf pełny - jest to taki graf w którym każda para wierzchołków jest połączona pojedynczą krawędzią.
Graf acykliczny - jest to graf w którym nie występują żadne cykle, tj. nie mamy żadnej możliwości chodzenia w kółko. :)
Graf skierowany - rodzaj grafu w którym każda krawędź ma swój określony kierunek w którym możemy się po niej poruszać. Przykładowo, jeśli krawędź prowadzi od wierzchołka 2 do wierzchołka 4 to nie możemy jej wykorzystać do podróży z wierzchołka 4 do 2. ;)

Mam nadzieję, że nie muszę wyjaśniać takich pojęć jak graf niespójny, graf cykliczny czy graf nieskierowany. Liczę na waszą wrodzoną inteligencję ;)
Istnieje jeszcze wiele rodzajów grafów jednak nie będę tu ich wszystkich wyjaśniał. Wymieniłem te najważniejsze.

Inne pojęcia:
Cykl - Już przy definicji grafu acyklicznego powiedziałem czym jest cykl, jednak tutaj podam bardziej sztywną definicję. Cykl to droga zamknięta, czyli taka której pierwszy wierzchołek jest jednocześnie ostatnim. Na grafie z rysunku 1 możemy odnaleźć dwa rozłączne cykle.
Waga krawędzi - Krawędziom grafu możemy przypisywać różne wagi. Jest to jakby koszt podróży tą krawędzią.
Stopień wierzchołka - Jest to liczba krawędzi sąsiadujących z wierzchołkiem. W grafach skierowanych możemy wyróżnić stopień wchodzący i wychodzący czyli odpowiednio liczbę krawędzi prowadzących do i wierzchołka z niego wychodzących.
Sąsiad wierzchołka - Jest to wierzchołek połączony z danym wierzchołkiem pojedynczą krawędzią.

Przykłady zastosowania grafów
     No dobrze, wszystko pięknie, ale po co nam to? Rozważmy następujący problem: Jaś wraca ze szkoły. Jest bardzo zmęczony po ciężkim dniu i chciałby jak najszybciej położyć się w wygodnym łóżku. Chciałby więc dowiedzieć się jaka jest najkrótsza droga ze szkoły do domu prowadząca jedynie po wyznaczonych ścieżkach. Możemy mu powiedzieć, żeby nie marudził i zdrzemną się na jakimś kamieniu, albo możemy przedstawić ten problem w postaci grafu i w ten sposób pomóc Jasiowi w znalezieniu najkrótszej drogi do domu. ;)
     Gdybyśmy wszystkie skrzyżowania dróg w miasteczku Jasia potraktowali jako jakieś punkty, natomiast drogi jako krawędzie wychodzące z tych punktów, o wagach równych długości odpowiadających im dróg, uzyskali byśmy graf przedstawiający system dróg w miasteczku. Istnieje tzw. algorytm Dijkstry znajdujący najkrótszą drogę od dowolnego wierzchołka do wszystkich pozostałych.
     No, ale co nas obchodzi jakiś Jaś i jego problemy? Jakie korzyści nam dostarczają grafy? Otóż okazuje się, że algorytmy oparte na grafach znajdują wiele praktycznych zastosowań. Przykładowo, możliwość szybkiego wyliczenia najkrótszej drogi przez komputer jest zastosowana w samochodowych GPSach. Wiem, że większość osób czytających ten artykuł to amatorzy programowania gier. Również w tej dziedzinie grafy są nam niezwykle pomocne. Wyobraźmy sobie, że piszemy sztuczną inteligencję postaci sterowanej przez komputer i chcemy by postać ta była w stanie odnaleźć najkrótszą drogę między jakimiś punktami nie wpadając po drodze na ściany, czy inne przeszkody. Wystarczy w odpowiedni sposób przedstawić mapę gry jako graf. Analogicznie możemy zaprogramować inteligentny pocisk omijający przeszkody, albo komputerowego przeciwnika w jakiejś samochodówce.

I to by było na tyle...
     ...w tej części artykułu. Być może trochę cię zanudziłem, ale wydaje mi się, że to była ta nudniejsza część. Dalej będzie ciekawiej. W następnych częściach opiszę sposoby reprezentacji grafów w programowaniu, oraz kilka podstawowych algorytmów operujących na grafach. Czyli trochę więcej praktyki (oczywiście teorii też nie zabraknie). ;)


Przejdź do następnej części
głosów: 4 | ocena: 7.75 oceń zasób | dodał: Platyna
Komentarze
stron: 1

1


av

propaganja (14:25, 4.06.2009)

kim był dijkstra?

stron: 1

1



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
26 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 26, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
exp (23:59, 9.12.18):
teraz spoko wygląda
MaxGaming (23:28, 9.12.18):
To już dużo lepsze! Chociaż nadal wygląda trochę jakby to był bug a nie feature
gnysek (22:33, 9.12.18):
ok, to zostawię wersję pierwszą jaką miałem - zmniejszenie przeźroczystości. Będą lekko jaśniejsze ikonki.
MaxGaming (22:24, 9.12.18):
ale nie wszystko na szaro(bo najczęściej większość tematów jest szara przez mały ruch)
MaxGaming (22:24, 9.12.18):
lepiej już oznaczyć wykrzyknikiem małym te nowe, albo coś
MaxGaming (22:23, 9.12.18):
Według mnie to glupio działa. Nagle wszystko jest szare jakby się zepsuło
gnysek (17:26, 9.12.18):
Od teraz posty napisane przed waszą ostatnią wizytą dostaną szarka ikonkę na stronie głównej - łatwiej znaleźć nowy kontent
MaxGaming (17:22, 9.12.18):
po prostu rób coś, zdobywaj doświadczenie i czytaj na jakiś temat żeby się rozwijać
exp (16:43, 9.12.18):
kurczę chciałbym się znać na czymś tak jak ty na gamedevie
exp (16:42, 9.12.18):
aha, więc to o to chodzi
gnysek (13:51, 9.12.18):
prawdopodobnie po to, żeby Steam VAT odprowadzał w stanach, w których trzeba, w Twoim imieniu.
gnysek (13:51, 9.12.18):
bo teraz 100$ wystarczy, tylko z polskiego punktu widzenia musisz zgłosić firmę do podatku (zerowego), w USA (telefonicznie), żeby dostać ichni NIP.
exp (13:40, 9.12.18):
właśnie też wyczytałem to w regulaminie, no ale coś mi tu nie pasuje. ludzie ciągle wrzucają na steama takie gówienka, że nie wierzę, że oni się tak wysilali
gnysek (13:24, 9.12.18):
musiałbyś założyć firmę, zawrzeć umowę ze steam itd.
Temporal (9:52, 8.12.18):
ambicje zawsze nas gubią
exp (22:52, 7.12.18):
w sensie 99 dolarów
exp (22:50, 7.12.18):
tak z ciekawości, jakbym chciał sprzedawać swoją grę, np. na steamie, to po prostu wystarczy zrobić upgrade do wersji "developer" za cztery stówki?
exp (14:37, 7.12.18):
ale mój poprzedni koncept był całkiem fajny i chyba oryginalny. było to tak jakby połączenie spelunky i contry, choć nie do końca
exp (14:36, 7.12.18):
znów naszła mnie ochota na zrobienie gierki i dobrze wiem, że skończy się tak, że mój prosty pomysł się rozrośnie i nigdy jej nie skończę
MaxGaming (23:53, 6.12.18):
co tam u was mordeczki
MaxGaming (3:01, 5.12.18):
też o tym myślałem, lub po prostu ograniczenie np maks 4 strzał i trzeba wytwarzaćnowe
gnysek (23:04, 4.12.18):
Dzida/oszczep. Można rzucać i ma jakaś tam wytrzymałośc, nie trzeba naboi, w razie czego można wytwarzać nową.
exp (19:16, 4.12.18):
może zastawianie pułapek
MaxGaming (17:45, 4.12.18):
U mnie to działa trochę inaczej. Ciężko ranne zwierze przyśpiesza i albo ucieka albo podejmuje walkę i wtedy szarżuje w naszym kierunku
MaxGaming (17:41, 4.12.18):
np łuk, tylko trzeba to tak zrobić aby taki łuk nadawał się jedynie do absolutnie podstawowych celów
MaxGaming (17:41, 4.12.18):
ze trzeba coś zrobić jako taką broń powszednią która akurat będzie miała sporo naboi i łatwo je będzie zdobyć
MaxGaming (17:40, 4.12.18):
hmm, ciekawy system, ale na razie chodzi mi
gnysek (17:37, 4.12.18):
wtedy można mieć mało naboi i ryzykujesz, albo strzelasz 2/3 razy i zgon od razu, albo czekasz aż padnie
gnysek (17:36, 4.12.18):
duże powinny krwawić, jednym strzałem = czekasz 5 minut na śmierć, albo strzelasz dalej
MaxGaming (17:35, 4.12.18):
a chodzi mi o stworzenie bardzo realnego respectu dla dużych zwierząt, chcę żeby polowanie na coś dużego było dla gracza czymś wyjątkowym i odświętnym, kiedy znajdzie jakąś amunicję do fajniejszej broni
MaxGaming (17:34, 4.12.18):
Co nie jest takie proste, bo strzelanie z łuku 3 razy żeby zabić zająca to na przykłąd pomyłka i byłoby bardzo śmiesznie. Zabicie zająca za jendym strzałem = obrażeniom na tyle dużym że na upartego upolowałoby się i dużo większe zwierzęta
MaxGaming (17:34, 4.12.18):
coś takiego żeby nie dało się z tego za wiele zrobić, ale żeby wystarczyło na polowanie na najprostrze zwierzęta pokorju zająca żeby zdobyć pożywienie
MaxGaming (17:33, 4.12.18):
a same pociski będą na wagę złota. Tylko muszę wymyślić jak w to wszystko wpleść uzbrojenie inne niż broń palna
MaxGaming (17:33, 4.12.18):
broń krótka na prawdę nie za bardzo nadaję się do polowania ze względu na swój bardzo mały zasięg i celność, broń pokroju kar98k dla gracza który według fabuły nie za bardzo miał wcześniej kontakt z militariami nie jest szybka do przeładowania i chociaż ma duży zasięg i potrafi powalać z nóg na prawdę szybko to jednak jeden pochopny strzał i zanim przeładujemy to możemy być już martwi
MaxGaming (17:31, 4.12.18):
ale jednoczęśnie funkcjonalna. Unikam realizmu na siłę który by komplikował rozgrywkę i zmieniał ją w niezrozumiałą, a staram się to nadrobić po prostu realizmem w postaci ograniczeń które nałożone są na nas
MaxGaming (17:30, 4.12.18):
jak wspominałem już moja gra ma być jak najprostrza zarówno dla gracza jak i dla mnie w rozwijaniu
MaxGaming (17:30, 4.12.18):
a w grze otwartego świata wcale być nie miało, dopiero w trakcie tworzenia doszedłem do wniosku że można to łatwo i fajnie zrobić i jednoocześnie uniknąc problemów typu "mam misje fabularną 10tyś pikseli ode mnie"
MaxGaming (17:29, 4.12.18):
ale to ma swój haczyk, bo nie dałoby się w tak prosty sposób zrobić otwartego świata, ale wiem jak obejść minusy tego
MaxGaming (17:28, 4.12.18):
Zrobiłem w swojej grze teoretycznie nie limitowany niczym otwarty świat, w praktyce jedynym limitem jest pozycja, czyli zwyczajnie żeby x i y były w stanie się zmieścić w int'cie
MaxGaming (17:09, 4.12.18):
#JANUSZ100%
MaxGaming (17:05, 4.12.18):
To ja daję 20euro jak zorganizujesz to tak że ja ją wygram
gnysek (10:43, 4.12.18):
mam nadzieję w święta w końcu wgrać zmiany które mam gotowe i ruszyć z drugim sezonem ligi 24... jakieś nagrody zorganizujemy, sam osobiście dam kartę na 25eur na Steam
gnysek (10:41, 4.12.18):
że kiedyś był cebulacki ?
Wojo (23:53, 3.12.18):
polemizowałbym
exp (22:56, 3.12.18):
Wojo gmclan raczej nie jest takim cebulackim forum, może kiedyś trochę było, ale i tak wszystko w granicach
MaxGaming (1:05, 3.12.18):
słuszna uwaga w sumie
gnysek (0:42, 3.12.18):
spróbuj z while
MaxGaming (23:34, 2.12.18):
Wybaczcie bo nie jestem w stanie wygooglować. Ma ktoś pojęcie jaka jest maksymalna ilość znaków dla stringa w GMS 1.4?
Wojo (21:55, 2.12.18):
czyli mniej więcej tak jak na gmclanie
exp (19:57, 2.12.18):
potem mogą walić konia do swojej elitarności na swoim forum z 9 użytkownikami
Ankieta
» Jakie kursy najchętniej widziałbyś na stronie ?
GM Studio
GM Studio 2
Godot
Construct

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2018. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2018 {=|=} fable_inside();

[ Czas generowania strony: 0.02204 sekund ] [ Liczba zapytań MySQL: 13 ]