Generatory labiryntów: modyfikacje algorytmu komórkowego i analiza właściwości generowanej klasy

• Autorzy: Noga P.

Warianty tytułu

EN

Maze generators: modifications of the cell connection algorithm, and analysis of properties of generated class of labyrinths

• Języki publikacji: PL

Abstrakty

PL

Wyróżniamy trzy podstawowe algorytmy generujące labirynty, których grafowa reprezentacja ma postać drzew: błądzenia losowego, budowania ścian i komórkowy[1]. W pracy przedstawione zostaną modyfikacje algorytmu komórkowego, które potrafią wygenerować tę samą klasę labiryntów, co podstawowa wersja algorytmu, przy jednoczesnej zmianie parametrów opisujących ich wygląd (preferencja kierunku wyjścia, średnia liczba wyjść z pokoju, średnia długość korytarza itp.); jak i modyfikacje zawężające klasę generowanych labiryntów (przez wprowadzenie masek hipsometrycznych). Omówiony zostanie również istotny wpływ tych modyfikacji na fabularyzację labiryntów.

EN

We consider three main maze generators with output graph representations as a tree: random walking, wall building, cell connection. In this paper modifications of cell connection algorithm are presented, that generate the same class of mazes as standard algorithm, but with different parameters describing their shape (direction preference, average number of exits, numbers of dead-end tunnels, average length of tunnel etc.) Also, a modification is presented that can generate other (smaller or larger) classes of mazes. (for example: the hypsometric masks).

Słowa kluczowe

PL

generatory labiryntów; algorytm komórkowy; właściwości generowanej klasy

EN

maze generators; cell connection algorithm; properties of generated class of labyrinths

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 19
• Strony: 389--393
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Noga P.

• Politechnika Gdańska Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] P, Noga: Algorytmy generujące labirynty, praca magisterska, Wydział Mat.-Fiz.-Inf., Uniwersytet Gdański (2006).
• [2] J. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem, Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50.
• [3] W. H. Matthews: Mazes and Labyrinths, at sacred-texts.com, chapter XXI.
• [4] R. Diestel: Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag (2005).