Maze generator with most popular shapes - hexagon, triangle, square

Overview

Maze-Generator

Maze generator with most popular shapes - hexagon, triangle, square (sqaure not implemented yet):

  1. Theory:
  • Planar Graph https://en.wikipedia.org/wiki/Planar_graph Its role is to make the structure of the maze. In this graph information is stored information about nodes, edges and faces of the grid. Nodes are (x, y) points position, edges (a, b) contains indexes of nodes which create specific edge. Faces are a lists of lists of edges [(a, b), (b, c), ..., (f, a)] which create specific face.

  • Dual Graph https://en.wikipedia.org/wiki/Dual_graph Its role is to make the grid of the possible moves between cells (faces of the planar graph)

  • k-nearest neighbour algorithm https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm Is used for determining neighbour cells for each cell

  • randomized depth-first search algorithm https://en.wikipedia.org/wiki/Maze_generation_algorithm Is used for determining possible moving ways in the maze. It is just one of many possibilities to make ways. I choosed recursive implementation

  • edges intersection https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ Testing wheter edges are intersecting using vectors theory. Orientation of two vectors (edges) is computed and is tested whether intersect point is a part of the segments. Implementation is took from the link. It is neccessary to test whether planar graph's wall is intersecting with possible way (dual graph's edges). If yes, wall is deleted.

  1. Idea:
  • Program is built based on graph theory. Maze is made of two graphs. The idea is to make a planar graph which creates grid of shapes (hexagons, triangles etc.) and create another graph which is dual to the first graph. The role of this second graph is to create possible moving ways in the maze. This graph has nodes in the centers of faces defined by the planar graph and edges, which connecting every neighbour face with k-nearest neighbour algorithm. The next step is to run Randomized depth-first search algorithm which travels around the dual graph and creates actual maze. The last step is to delete walls which are intersected by the edges of the dual graph.
  1. Program's structure:

3.1 In first step the planar graph is constructed with possibility to change the number of columns and rows of the maze. This creates a structure of the maze (e.g. 10x10):

image

  • In prepareGraph() function is called Hex() function (columns * rows) times which creates (columns * rows) hexagons. Hex() called multiple times creates duplicated nodes and edges in the graph which is undesirable, so in the next part of the prepareGraph function duplicated nodes are removed and the edges indexes are repaired (because after deleting some nodes, edges has references to nodes which actually do not exist (look 1. Theory links))

3.2 Second step is construction dual graph to the planar graph. It creaetes structure of the possible moves to choose by the algorithm (red one, case 10x10):

image

  • Dual graph F is created in DualGraph() function which takes another Graph G which it will be dual to. Nodes of graph F are computed by calculating center of each face in graph G ((average(sum(each x)), average(sum(each y)), each x and y from all nodes which create specific face). After that, edges are defined with k-nearest-neighbours algorithm. It takes 6 nearest candidates to be a neighbour and make edge between nodes which are in distance < 3 * a. Thats because not every node has 6 neighbours, so this restriction decreasing number of neighbours for side hexagons.

3.3 Next step is to make actual maze. To do this I used randomized depth-first search algorithm (one of many possibilities, one of the easiest and which gives simplest mazes):

image

  • Firstly, algorithm selects random node from dual graph (red one) and marks it as visited and add it to possible backtrack. Then it makes list with possible ways (edges) to unvisited nodes and selects random way. If unvisited node in nearest neighbourhood does not exists (dead end) it backtracks (move to the last node at the backtrack list and removes this node from this list). If unvisited node or nodes exist algorithm selects it randomly and marks new node to the visited nodes. Then add this node to the "Backtrack" list and add selected way to the "journey" list which contains traveled ways. After each completed iteration (without dead ends) algorithm checks for all the edges if the nodes which are connected by the edge are both visited. If yes, it tests if this edge is in the "journey". If not, it can be deleted.

3.4 Last step is to delete walls between cells connected by dual graph's edges (10x10 case):

image

  • Function DeleteIntersections() deletes all the walls (planar graph's edges) which are intersecting with the ways (dual graph's edges). For every edge in dual graph it takes every edge in planar graph and tests whether the edges intersect. If yes, the wall is deleted and another way is took to test (because way could intersect with only one wall so it has no sense to continue this iteration). To tell if the edges are intersected I use functions doIntersect() which uses orientation(), which returns orientation of the given vectors, and onSegment which tells us whether the intersect point is in the range of the vectors.
  1. Some information
  • It is possible to turn off display of the dual graph (ways), just comment last but one for loop

image

  • Program is inefficient for large mazes (32x32 is constructing 30sec), so it is recommended to test program for max 20x20 size :)

  • Changing shape's edge size to enough small value (a = 1) could cause some bugs in dual graph's structure

  • To get the best effect in triangle maze call prepareGraph with columns and rows values in ratio 3:2 (18x12, 24x16 etc.)

    image

Owner
Kacper Plesiak
Student of the Gdańsk University of Technology in the field of Control Engineering. Interested in Machine Learning, Chess and Football
Kacper Plesiak
A Gtk based Image Selector with Preview

gtk-image-selector This is an attempt to restore Gtk Image Chooser "lost functionality": displaying an image preview when selecting images... This is

Spiros Georgaras 2 Sep 28, 2022
Imutils - A series of convenience functions to make basic image processing operations such as translation, rotation, resizing, skeletonization, and displaying Matplotlib images easier with OpenCV and Python.

imutils A series of convenience functions to make basic image processing functions such as translation, rotation, resizing, skeletonization, and displ

PyImageSearch 4.3k Jan 01, 2023
Img-to-ascii-art - Converter of image to ascii art

img-to-ascii-art Converter of image to ascii art Latest Features. Intoducing Col

1 Dec 31, 2021
vsketch is a Python generative art toolkit for plotters

Generative plotter art environment for Python

Antoine Beyeler 380 Dec 29, 2022
image-processing exercises.

image_processing Assignment 21 Checkered Board Create a chess table using numpy and opencv. view: Color Correction Reverse black and white colors with

Benyamin Zojaji 25 Dec 15, 2022
ModernGL is a python wrapper over OpenGL 3.3+ core

ModernGL is a python wrapper over OpenGL 3.3+ core that simplifies the creation of simple graphics applications like scientific simulations, games or user interface

ModernGL 1.4k Jan 01, 2023
Viewer for NFO files

NFO Viewer NFO Viewer is a simple viewer for NFO files, which are "ASCII" art in the CP437 codepage. The advantages of using NFO Viewer instead of a t

Osmo Salomaa 114 Dec 29, 2022
Easily turn large sets of image urls to an image dataset. Can download, resize and package 100M urls in 20h on one machine.

img2dataset Easily turn large sets of image urls to an image dataset. Can download, resize and package 100M urls in 20h on one machine. Also supports

Romain Beaumont 1.4k Jan 01, 2023
Image Reading, Metadata Conversion, and Image Writing for Microscopy Images in Python

AICSImageIO Image Reading, Metadata Conversion, and Image Writing for Microscopy Images in Pure Python Features Supports reading metadata and imaging

Allen Institute for Cell Science - Modeling 137 Dec 14, 2022
PyGtk Color - A couple of python scripts to select a color (for scripting usage)

Selection Scripts This repository contains two scripts to be used within a scripting project, to aquire a color value. Both scripts requir

Spiros Georgaras 1 Oct 31, 2021
Plots is a graph plotting app for GNOME.

Plots is a graph plotting app for GNOME. Plots makes it easy to visualise mathematical formulae. In addition to basic arithmetic operations, it supports trigonometric, hyperbolic, exponential and log

Alex Huntley 138 Dec 14, 2022
This is a python project which detects color of an image when you double click on it.

This is a python project which detects color of an image when you double click on it. You have to press ESC button to close the pop-up Image window. There are mainly two library CV2 and Pandas that a

Yashwant Kumar Singh 0 Aug 16, 2022
Anaglyph 3D Converter - A python script that adds a 3D anaglyph style effect to an image using the Pillow image processing package.

Anaglyph 3D Converter - A python script that adds a 3D anaglyph style effect to an image using the Pillow image processing package.

Kizdude 2 Jan 22, 2022
A minimal, standalone viewer for 3D animations stored as stop-motion sequences of individual .obj mesh files.

ObjSequenceViewer V0.5 A minimal, standalone viewer for 3D animations stored as stop-motion sequences of individual .obj mesh files. Installation: pip

csmailis 2 Aug 04, 2022
Sombra is simple Raytracer written in pure Python.

Sombra Sombra is simple Raytracer written in pure Python. It's main purpose is to help understand how raytracing works with a clean code. If you are l

Hernaldo Jesus Henriquez Nuñez 10 Jul 16, 2022
Fast Image Retrieval (FIRe) is an open source image retrieval project

Fast Image Retrieval (FIRe) is an open source image retrieval project release by Center of Image and Signal Processing Lab (CISiP Lab), Universiti Malaya. This project implements most of the major bi

CISiP Lab 39 Nov 25, 2022
Nudity detection with Python

nude.py About Nudity detection with Python. Port of nude.js to Python. Installation from pip: $ pip install --upgrade nudepy from easy_install: $ eas

Hideo Hattori 881 Jan 06, 2023
Gaphor is the simple modeling tool

Gaphor Gaphor is a UML and SysML modeling application written in Python. It is designed to be easy to use, while still being powerful. Gaphor implemen

Gaphor 1.3k Dec 31, 2022
GIMP script to export bitmap as GRAPHICS 4 file (aka SCREEN 5)

gimpfu-msx-gr4.py GIMP script to export bitmap as GRAPHICS 4 file (aka SCREEN 5). GRAPHICS 4 specs are: 256x212 (or 256x192); 16 color palette (from 5

Pedro de Medeiros 4 Oct 17, 2022
NFT collection generator. Generates layered images

NFT collection generator Generates layered images, whole collections. Provides additional functionality. Repository includes three scripts generate.py

Gleb Gonchar 10 Nov 15, 2022