Non-perfect maze generation using Kruskal algorithm
| Autor: | Syarifah Meurah Yuni, Marwan Ramli, Ikhsan Maulidi, Mahyus Ihsan, Dedi Suhaimi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Vertex (graph theory)
Loop (graph theory) Spanning tree Computer Science::Neural and Evolutionary Computation Orientation (graph theory) Quantitative Biology::Other Quantitative Biology::Cell Behavior Disjoint-set Computer Science::Emerging Technologies General Energy Kruskal's algorithm Hardware_INTEGRATEDCIRCUITS Graph (abstract data type) cycle bias grid graph kruskal algorithm modifications non-perfect maze wall bias lcsh:Science (General) Lattice graph Algorithm psychological phenomena and processes MathematicsofComputing_DISCRETEMATHEMATICS lcsh:Q1-390 Mathematics |
| Zdroj: | Jurnal Natural, Vol 21, Iss 1 (2021) |
| ISSN: | 2541-4062 1411-8513 |
| DOI: | 10.24815/jn.v21i1.18840 |
| Popis: | A non-perfect maze is a maze that contains loop or cycle and has no isolated cell. A non-perfect maze is an alternative to obtain a maze that cannot be satisfied by perfect maze. This paper discusses non-perfect maze generation with two kind of biases, that is, horizontal and vertical wall bias and cycle bias. In this research, a maze is modeled as a graph in order to generate non-perfect maze using Kruskal algorithm modifications. The modified Kruskal algorithm used Fisher Yates algorithm to obtain a random edge sequence and disjoint set data structure to reduce process time of the algorithm. The modification mentioned above are adding edges randomly while taking account of the edge’s orientation, and by adding additional edges after spanning tree is formed. The algorithm designed in this research constructs an non-perfect maze with complexity of where and denote vertex and edge set of an grid graph, respectively. Several biased non-perfect mazes were shown in this research by varying its dimension, wall bias and cycle bias. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|