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
Bot by image recognition simulating (random) human clicks

bbbot22 bot por reconhecimento de imagem simulando cliques humanos (aleatórios) inb4: sim, esse é basicamente o mesmo bot de 2021 porque a Globo não t

Yuri 2 Apr 05, 2022
Plots the graph of a function with ASCII characters.

ASCII Graph Plotter Plots the graph of a function with ASCII characters. See the change log here. Developed by InformaticFreak (c) 2021 How to use py

InformaticFreak 2 Apr 29, 2022
A QR Code encode and decode python module

A QR Code encode and decode python module

Fayas Noushad 4 Feb 10, 2022
👾 Python project to help you convert any image into a pixel art.

👾 Pixel Art Generator Python project to help you convert any image into a pixel art. ⚙️ Developer's Guide Things you need to get started with this co

Atul Anand 6 Dec 14, 2022
impy is an all-in-one image analysis library, equipped with parallel processing, GPU support, GUI based tools and so on.

impy is All You Need in Image Analysis impy is an all-in-one image analysis library, equipped with parallel processing, GPU support, GUI based tools a

24 Dec 20, 2022
Seeks to remove text from an image in a convincing way.

Text-Removal This is a Computer Vision project that seeks to successfully remove text from an image by covering the text areas in a convincing way. He

6 Nov 22, 2022
thumbor is an open-source photo thumbnail service by globo.com

Survey If you use thumbor, please take 1 minute and answer this survey? It's only 2 questions and one is multiple choice!!! thumbor is a smart imaging

Thumbor (by @globocom) 9.3k Dec 31, 2022
A scalable implementation of WobblyStitcher for 3D microscopy images

WobblyStitcher Introduction A scalable implementation of WobblyStitcher Dependencies $ python -m pip install numpy scikit-image Visualization ImageJ

CSE Lab, ETH Zurich 7 Jul 25, 2022
SALaD (Semi-Automatic Landslide Detection) is a landslide mapping system

SALaD (Semi-Automatic Landslide Detection) is a landslide mapping system. SALaD utilizes Object-based Image Analysis and Random Forest to map landslides.

NASA 14 Jan 04, 2023
pix2tex: Using a ViT to convert images of equations into LaTeX code.

The goal of this project is to create a learning based system that takes an image of a math formula and returns corresponding LaTeX code.

Lukas Blecher 2.6k Dec 30, 2022
Python Program that lets you write in your handwriting!

Handwriting with Python Python Program that lets you write in your handwriting! Inspired by: thaisribeiro.in How to run? Install Unidecode and Pillow

Amanda Rodrigues Vieira 2 Oct 25, 2021
missing-pixel-filler is a python package that, given images that may contain missing data regions (like satellite imagery with swath gaps), returns these images with the regions filled.

Missing Pixel Filler This is the official code repository for the Missing Pixel Filler by SpaceML. missing-pixel-filler is a python package that, give

SpaceML 11 Jul 19, 2022
PyGram Instagram-like image filters.

PyGram Instagram-like image filters. Usage First, import the client: from filters import * Instanciate a filter and apply it: f = Nashville("image.jp

Ajay Kumar Nagaraj 102 Feb 21, 2022
DP2 graph edit codes.

必要なソフト・パッケージ Python3 Numpy JSON Matplotlib 動作確認環境 MacBook Air M1 Python 3.8.2 (arm64) Numpy 1.22.0 Matplotlib 3.5.1 JSON 2.0.9 使い方 draw_time_histgram(

1 Feb 19, 2022
A pure python implementation of the GIMP XCF image format. Use this to interact with GIMP image formats

Pure Python implementation of the GIMP image formats (.xcf projects as well as brushes, patterns, etc)

FHPyhtonUtils 8 Dec 30, 2022
Blender addon to generate better building models from satellite imagery.

Blender addon to generate better building models from satellite imagery.

Ivan Ereshchenko 24 Apr 14, 2022
Simple to use image handler for python sqlite3.

SQLite Image Handler Simple to use image handler for python sqlite3. Functions Function Name Parameters Returns init databasePath : str tableName : st

Mustafa Ozan Çetin 7 Sep 16, 2022
Image Processing - Make noise images clean

影像處理-影像降躁化(去躁化) (Image Processing - Make Noise Images Clean) 得力於電腦效能的大幅提升以及GPU的平行運算架構,讓我們能夠更快速且有效地訓練AI,並將AI技術應用於不同領域。本篇將帶給大家的是 「將深度學習應用於影像處理中的影像降躁化 」,

2 Aug 04, 2022
A Icon Maker GUI Made - Convert your image into icon ( .ico format ).

Icon-Maker-GUI A Icon Maker GUI Made Using Python 3.9.0 . It will take any image and convert it to ICO file, for web site favicon or Windows applicati

Insanecodes 12 Dec 15, 2021
Nutrify - take a photo of food and learn about it

Nutrify - take a photo of food and learn about it Work in progress. To make this a thing, we're going to need lots of food images... Start uploading y

Daniel Bourke 93 Dec 30, 2022