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) | czas czytania: 4 minuty, 39 sekund
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
1 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
doctor (11:31, 26.04.19):
Np. PHP umożliwia przerobienie JSON na tablice, tablice można sortować, mieszać (...), a w GM CHYBA trzeba użyć DSów
doctor (11:30, 26.04.19):
Ja się zdecentralizowałem, elo benc. Ciekawi mnie czemu w GM stosuje się DSy zamiast ogarnąć strukturę tablic?
Wojo (11:11, 26.04.19):
Fervi czasami był człowiekiem dalszym od rzeczywistości niż ja sam.
doctor (0:18, 26.04.19):
A no (Steem dokładniej). Trochę upada, ale parę gier jest (czy dobre ...? Tak sobie). Steem Monsters, Drug Wars czy NextColony
I am Lord (23:10, 25.04.19):
Fervi już chyba z 2 lata temu coś gadał o blockchainowym steemit
MaxGaming (21:52, 25.04.19):
Ja jak przeglądam fora biznesowe to kojarzy mi się od razu z bajką Pinki i Mózg - "Co dzisiaj robimy? - Jak to co? Budować kolejnego blockchaina!"
doctor (21:08, 25.04.19):
Kiedyś czytałem o blockchainie do robienia zdecentralizowanych baz danych, chyba kompatybilnych z SQLite
MaxGaming (18:18, 25.04.19):
Plotki mówią, że niedługo powstanie blockchain do robienia blockchainów
doctor (17:50, 25.04.19):
Nie no, już kiedyś mówiłem xD Czasem jak projekt wypali (pewnie nie) to nagle dają dużo hajsuf
Wojo (17:30, 25.04.19):
Jest 2019 rok, trudno się dziwić, że nawet na niszowym forum ktoś o tym wspomniał
MaxGaming (14:40, 25.04.19):
Kiedy nawet na gmclanie ludzie już mówią o blockchainie
doctor (14:08, 25.04.19):
hmm, nie o to mi chodziło, ale może coś wywnioskuję
doctor (14:05, 25.04.19):
No proszę, widać da się zrobić mój projekt i zintegrować z magicznym blokczejnem - dzięki
gnysek (11:34, 25.04.19):
Oczywiście, że tak. Jest przykład wysyłania i odbierania danych na stronie - gmclan.org/index.php?plik=227
doctor (11:23, 25.04.19):
Pytanie też inne - czy może się strona w PHP jakoś skomunikować z grą? Np. by grać potrzebujesz się autoryzować w PHP, który potem login ze strony przekazuje do gry?
doctor (11:20, 25.04.19):
To spróbuję, bo myslałem, że 1.4 początkowo nie miał takiej opcji, a to w sumie dużo by zmieniło ... Tylko muszę ogarnąć jak wgrać Game Makera, bo tak sobie chodzi
gnysek (0:34, 25.04.19):
Generalnie do tej samej domeny bez problemu.
gnysek (0:34, 25.04.19):
Zawsze się dało. Tylko nie do każdego serwera ale to już zabezpieczenia przeglądarek. Poczytaj o CORS.
doctor (19:42, 24.04.19):
Czy da się wysyłać HTTP Requesty (Events) z poziomu gry w GMS1.4 HTML5? Bo kiedyś się chyba nie dało ...
doctor (19:41, 24.04.19):
Moim zdaniem Game Maker poniżej Studio 2.0 są specjalnie komplikowane. Wgranie 1.4 jest wielkim problemem Elo
SimianVirus7 (20:50, 18.04.19):
ten program działa, bo odpalanie starych game makerowych gier w trybie zgodności nie zdaje egzaminu (przynajmniej u mnie)
exp (17:52, 18.04.19):
pamiętam że ktoś zrobił naprawdę dobrego tower defence na początku ligi
MaxGaming (21:21, 17.04.19):
groups.google.c...ers/w17mO9qGiD0 - możliwe, że to by komuś mogło pomóc. Resztę kodu mam tylko potrzebuję systemu który pozwoli mi rozgraniczyć sesję przeglądarki między kontrolkami webbrowser
MaxGaming (21:15, 17.04.19):
Jest ktoś w stanie napisać mi funkcje o której mówię w poście na forum(abym mógł w dwóch kontrolkach webbrowser być zalogowany na dwa różne konta na stronach WWW) za 50-150zł? Podejrzewam, że jeśli ktoś zna rozwiązanie to jest kilka linijek kodu, ale ja nie mam pojęcia już jak to ugryźć. Blokowanie ciasteczek uniemożliwia logowanie, a usuwanie ich co sesje usuwa też z innej aktywnej sesji.
I am Lord (18:50, 17.04.19):
A zobaczcie jakie gierki były robione na ligę na początku. Przecież z nich teraz by szło zrobić całkiem dobre pełnoprawne gierki, kiedyś to był gmclan
nowy_user (15:24, 17.04.19):
Z drugiej jednak strony, gdyby wspomniani GMclanowicze urodzili się 15 lat później i ich czas twórczości przypadłby na dzisiejsze czasy, to bez wątpienia zostaliby pełnoetatowymi twórcami gier i mogliby spełniać swoje marzenia. A tak to nie wiadomo co z nimi się dzieje, pewnie mają jakąś ‘normalną’, wysysającą z kreatywności i nadziei pracę.
nowy_user (15:05, 17.04.19):
To prawda, GMS nas rozpieściło. Kiedyś, gdy prawie nikt nie zarabiał na tworzeniu gier w GMie, to tworząc nowy projekt nawet nie myślałeś o $, tylko o tym, aby innym sprawić radość. Dzięki temu mieliśmy okazję zagrać w naprawdę niezłe produkcje za free, a gdyby powstały dziś to musielibyśmy za nie słono zapłacić. Mam tu na myśli np. Bruce Lee 2004 Mataska, Mario Forever Borka czy też Jump! Jump! Anacondy.
I am Lord (13:09, 17.04.19):
bo odbiera przyjemność
I am Lord (13:09, 17.04.19):
A teraz z co bym się nie zabrał to myślę z tyłu głowy jak na tym zarobić i to mi psuje wszystklo
I am Lord (13:08, 17.04.19):
Kiedyś to było, robiliśmy gry dla samej frajdy i była masa pomysłów
gnysek (10:58, 17.04.19):
na szczęście takich artystów jak BigShark i PrzeAss kojarzę.
gnysek (10:36, 17.04.19):
Liczę na Cairo 4
I am Lord (0:05, 17.04.19):
xd
I am Lord (0:05, 17.04.19):
BigShark
Wojo (16:00, 16.04.19):
Nieważne, już znalazłem
Wojo (16:00, 16.04.19):
Ja jakoś nie mogę znaleźć profilu Pietra.
Wojo (15:45, 16.04.19):
To jest na tyle bierny człowiek, że nie zakładał wcześniej konta
gnysek (15:38, 16.04.19):
mnie zastanawia kim faktycznie jesteś, bo nie nowym_userem, znasz znacznie więcej historii niż ja.
nowy_user (20:02, 15.04.19):
Chociaż Ranmus chyba wybaczył już Pieterowi(przywódcy buntu), bo zdaje się że widziałem Pietera ostatnio na GMclanie. Po wielu latach w końcu zakopali topór wojenny
nowy_user (19:57, 15.04.19):
I tak wygląd jest dużo lepszy niż u konkurencji, mam tu na myśli oczywiście GMxxl. Ich stronka chyba już nawet nie istnieje, pewnie Ranmus ma osobistą satysfakcję: swego czasu kilku prominentnych użytkowników Gmclanu nieźle napsuło mu krwi, tworząc Gmxxl'a, dokonując tym samym wielkiego rozłamu na Polskiej scenie GMa.
MaxGaming (19:34, 15.04.19):
Mi tam pasuję głównie wersja mobilna stronki. Jest świetna
gnysek (19:16, 15.04.19):
btw. kiedyś był taki podobny zielony motyw do jPortal, od Ranmy, ale niestety w odmętach internetu zaginął - niby w internecie jest wszystko, ale szczerze to 15 lat temu było więcej niż dziś
gnysek (19:15, 15.04.19):
żadne droczenie, nigdy nikt z was nic lepszego nie zaproponował, więc wiem, że każdemu pasuje
XBlacKX (15:22, 15.04.19):
też lubię ten wygląd, chciałem się podroczyć tylko
I am Lord (12:54, 15.04.19):
to jest niezła archeologia
I am Lord (12:54, 15.04.19):
Apropos Gothiczka @Wojo www.youtube.com...h?v=raudY3eVrGI
gnysek (11:34, 15.04.19):
btw. naprawiłem też wyświetlanie błędów przy wysyłaniu shoutów które... chyba nigdy przez 15 lat się nie wyświetlały, a były zaprogramowane Brakowało 2-3 linijek kodu.
gnysek (11:10, 15.04.19):
A skoro obecny działa... nie wiem czy sens go zmieniać, i tracić 300-400 godzin na pisanie zmian.
Ankieta
» Ile powinny trwać tury Ligi 24?
24h
48h
54h (piątek od 18:00)
7 dni
inna długość (podałem w komentarzu ankiety)

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

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