Maze generation algorithms

Post reply

❤Follow Topic(5)

0 favourites

16 posts
- 1
- 2

From the Asset Store

A-STAR ALGORITHM (PATHFINDING) IN ISOMETRY

$8 USD

Finding the shortest path through the cells based on the A-star algorithm

q3olegka

- dop2000
- - Joined 26 May, 2016
  - 139 topics • 12,602 posts
- 2
- 30 Aug, 2020
- Quote
I'm looking for Construct implementation of popular maze generation algorithms - Prim's, Kruskal's etc.

R0J0hound Do you still have the examples from this old post? Could you re-upload them please?
Tagged:

maze
maze-generation
- eleanorjmorel
- - Joined 7 May, 2020
  - 24 topics • 417 posts
- 2
- 30 Aug, 2020
- Quote
cr31.co.uk/stagecast/wang/perfect.html
- dop2000
- - Joined 26 May, 2016
  - 139 topics • 12,602 posts
- 1
- 30 Aug, 2020
- Quote
eleanorjmorel Thanks. There is a lot of information in the internet, but I'm looking for Construct examples.
- tarek2
- - Joined 26 Jan, 2016
  - 38 topics • 1,252 posts
- 1
- 30 Aug, 2020
- Quote
Casualty I have been playing with Mazes last month or so and I had those two Algorithm names on the list to test but I managed to do only a different one because I didn't have the time.

Is the "Hunt & Kill" Algorithm, it works pretty good

I didn't do any refactoring or anything so not sure if it's needed, I just did it and left it like that, as was planning to come back to them so I will leave it like this see it helps you.

https://www.dropbox.com/s/o0qb47a05gv8weo/4-hunt%20%26%20kill%20algorithm%20%28maze%29%20new%20animation.capx?dl=0
- o0o
- - Joined 20 Jul, 2020
  - 2 topics • 8 posts
- 1
- 30 Aug, 2020
- Quote
cr31.co.uk/stagecast/wang/perfect.html

Great link. Thanks.
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 1
- 30 Aug, 2020
- Quote
Updated the links in that old post. I found some older maze generators but it used a third party plugin i no longer have.

-cheers
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 1
- 30 Aug, 2020
- Quote
Here's another attempt with another algorithm.

dropbox.com/s/6ux3pv6bvaofuo0/mazegen1.capx
- dop2000
- - Joined 26 May, 2016
  - 139 topics • 12,602 posts
- 2
- 31 Aug, 2020
- Quote
tarek2 R0J0hound These are great examples, thank you!

Here's another attempt with another algorithm.

What's the name of this algorithm? I'd like to read about it.
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 1
- 31 Aug, 2020
- Quote
It's this one:

en.wikipedia.org/wiki/Maze_generation_algorithm
I did a bit of a twist with the part about neighbors to make the events look cleaner.

I went for visualizing the maze but depending on how the maze would be represented things can change up.
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 2
- 31 Aug, 2020
- Quote
Some more fiddling with things. It can be made more like prims algo by pulling from a random point on the stack instead of the first. Also can be made to fill a shape with the maze.

dropbox.com/s/ejadw6go33j4b0i/mazegen2.capx
- dop2000
- - Joined 26 May, 2016
  - 139 topics • 12,602 posts
- 1
- 31 Aug, 2020
- Quote
Also can be made to fill a shape with the maze.

Wow, this is actually exactly what I was looking for!

Is it possible to make the maze solvable, and allow to specify entry and exit points?
- tarek2
- - Joined 26 Jan, 2016
  - 38 topics • 1,252 posts
- 1
- 31 Aug, 2020
- Quote
Hoh that some Grate examples from Rojoh

Also the old Avatar is back, Grate so we can recognize him quicker ))
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 1
- 31 Aug, 2020
- Quote
It‘a all connected so a path can be found between any two points.

You could start the generating from one end or the other, or simultaneously generate from both ends and the somehow connect the two mazes later. Maybe utilize the astar algorithm on an empty weighted grid to find a meandering path between the points, and then fill in the rest with more random maze.

Ultimately I don’t think it improves the maze generated over just a random one.

It can be made to highlight the path between two points though.
Try Construct 3

Develop games in your browser. Powerful, performant & highly capable.
Try Now Construct 3 users don't see these ads
- dop2000
- - Joined 26 May, 2016
  - 139 topics • 12,602 posts
- 1
- 1 Sep, 2020
- Quote
R0J0hound Oh, the black sprites are passages, and the white space is walls. Now it makes sense :)
Indeed all passages are connected and it works nicely with EasyStar.js pathfinding. Thanks again for your help!
- R0J0hound
- - Joined 15 Jun, 2009
  - 90 topics • 7,276 posts
- 1
- 1 Sep, 2020
- Quote
My pleasure. Glad it was useful!

-cheers