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
imgAnalyser - Un script pour obtenir la liste des pixels d'une image correspondant à plusieurs couleurs

imgAnalyser - Un script pour obtenir la liste des pixels d'une image correspondant à plusieurs couleurs Ce script à pour but, à partir d'une image, de

Théo Migeat 1 Nov 15, 2021
HtmlWebShot - A python3 package which Can Create Images From url, Html-CSS, Svg and from any readable file and texts with many setup features.

A python3 package which Can Create Images From url, Html-CSS, Svg and from any readable file and texts with many setup features

Danish 24 Dec 14, 2022
Rotates your images in the spirit of rot13

Image Rotator (imrot10) Its like rot13 but for images. Calling the algorithm imrot10 for im = image, rot = rotation, 10 = default magnitude. Unfortuna

Sarah 2 Dec 10, 2021
This app finds duplicate to near duplicate images by generating a hash value for each image stored with a specialized data structure called VP-Tree which makes searching an image on a dataset of 100Ks almost instantanious

Offline Reverse Image Search Overview This app finds duplicate to near duplicate images by generating a hash value for each image stored with a specia

53 Nov 15, 2022
Forza painter app with python

forza-painter Discord: A-Dawg#0001 (AE) Supports: Forza Horizon 5 Offically (OTHER v1.405.2.0, MS STORE v3.414.967.0, STEAM v1.414.967.0) Unofficially

320 Dec 31, 2022
Parking management project which generates barcode parking ticket with user-friendly Tkinter program GUI

Parking-management-system Parking management project which generates barcode parking ticket with user-friendly Tkinter program GUI How to run Download

1 Jul 03, 2022
A simple python script to reveal the contents of a proof of vaccination QR code.

vaxidecoder A simple python script to reveal the contents of a proof of vaccination QR code. It takes a QR code image as input, and returns JSon data.

Hafidh 2 Feb 28, 2022
An automated Comic Book downloader (cbr/cbz) for use with SABnzbd, NZBGet and torrents

Mylar Note that feature development has stopped as we have moved to Mylar3. EOL for this project is the end of 2020 and will no longer be supported. T

979 Dec 13, 2022
Create QR Code for link using Python

Quick Response QR is short and named for a quick read from a cell phone. Used to view information from transitory media and put it on your cell phone.

Coding Taggers 1 Jan 09, 2022
A drop-in replacement for django's ImageField that provides a flexible, intuitive and easily-extensible interface for quickly creating new images from the one assigned to the field.

django-versatileimagefield A drop-in replacement for django's ImageField that provides a flexible, intuitive and easily-extensible interface for creat

Jonathan Ellenberger 490 Dec 13, 2022
Craft PNG files that appear completely different in Apple software

Ambiguous PNG Packer Craft PNG files that appear completely different in Apple software

David Buchanan 1k Dec 29, 2022
Xmas-Tree-GIF-Tool - Convert any given animated gif file into an animation in GIFT CSV format

This repo is made to participate in Matt Parker's XmasTree 2021 event. Convert a

Aven Zitzelberger 2 Dec 30, 2021
Conversion of Image, video, text into ASCII format

asciju Python package that converts image to ascii Free software: MIT license

Aju Tamang 11 Aug 22, 2022
Ascify-Art - An easy to use, GUI based and user-friendly colored ASCII art generator from images!

Ascify-Art This is a python based colored ASCII art generator for free! How to Install? You can download and use the python version if you want, modul

Akash Bora 14 Dec 31, 2022
A tool to maintain an archive/mirror of your Google Photos library for backup purposes.

Google Photos Archiver Updated Instructions 8/9/2021 Version 2.0.6 Instructions: Download the script (exe or python script listed below) Follow the in

Nick Dawson 116 Jan 03, 2023
Create a 2D mesh for an airfoil in GMSH using python.

GMSHFoil A simple class to create a 2D mesh for an airfoil in GMSH using python. Requirements pip install airfoils

Charilaos Mylonas 1 May 16, 2022
Pythonocc nodes for Ryven

Pythonocc-nodes-for-Ryven Pythonocc nodes for Ryven Here a way to work on Pythonocc with a node editor, Ryven in that case. To get it functional you w

Tanneguy 30 Dec 18, 2022
The coolest python qrcode maker for small businesses.

QR.ify The coolest python qrcode maker for small businesses. Author Zach Yusuf Project description Python final project. Built to test python skills P

zachystuff 2 Jan 14, 2022
Python QR Code image generator

Pure python QR Code generator Generate QR codes. For a standard install (which will include pillow for generating images), run: pip install qrcode[pil

Lincoln Loop 3.5k Dec 31, 2022
This is an app that allows users to upload photos and display and store the photos in a file until the user deletes them.

Qt Photo App This is an app that allows users to upload photos and display and store the photos in a file until the user deletes them. Setup python3 -

Kathy Yang 5 Jan 22, 2022