Use Prim's Algo to make a tile maze

Get help using Construct 2

Post » Wed Jun 26, 2013 1:36 am

Hi all,

I'm working on a tile maze and I want to generate a tile maze using prim's algorithm. I've seen some threads/projects on here that are doing something similar but using other techniques. I really like the result of the prim's algorithm.

I found this: http://www.youtube.com/watch?v=ucWX34Vrel8

I understand the basics of what he is doing there. But, I'm having a little trouble figuring out the code for construct.

I know I can use an array to do it. use my x and y cords for the grid and my z cord for variables such as weight, and if the cell is open or closed.

But I need some help on how it moves through the grid choosing the lowest weight and so forth.

Any suggestions/help would be appreciated.

Thanks guys
B
5
Posts: 9
Reputation: 883

Post » Wed Jun 26, 2013 7:28 pm

I had a crack at it and here's my result:
https://dl.dropboxusercontent.com/u/5426011/examples18/maze_prims.capx

I used an array of size (20,20,2) to store the weights and weather or not a bit was plotted there (0 or 1).

It is rather slow since it scans the entire grid every time a piece is added. It can be made much faster if you find a way to only scan through neighboring cells.
B
85
S
27
G
85
Posts: 5,062
Reputation: 57,858

Post » Thu Jun 27, 2013 1:55 am

Hound,

Thanks for taking the time to help out with this.
This looks exactly like I'm going for.
I'm going through the code trying to reverse engineer what you've done.

I would like to be faster.. Could you possibly add some comments in the code so I can grasp what you have done better?

Thanks again!

Edit: I think I've got what you did figured out. If you figure out a way to make it faster please let me know. I'll be working on it as well.

Thanks again.sirrance2013-06-27 02:21:59
B
5
Posts: 9
Reputation: 883

Post » Thu Jun 27, 2013 7:02 am

To make it faster requires to optimize the forEach loop mostly. In this loop, we are looking for the point that has :
- exactly 1 neighbor
- isn't plot already
- has minimum weight
The problem is that every time the loop is done, neighbor count is recalculated for every (X,Y). I tried to add a 3rd Z layer on the Array, storing the number of neighbor for every point, and maintaining it every time we plot one more time (so only in the plot function). This let me remove completely the greedy calculation of the local "neighbors", that was removed too.
Last optimization, changing the organisation of the ForEach Loop to check the conditions in a special order :
- first, neighbor count, as the set of cells with only 1 neighbor is finite and minimal in the maze
- second, applying the "not constructed" condition"
- last, the most greedy, the "minimum weight" check
It works consistantly on a bigger maze, I didn't try to go higher than 100x100 though
capx
B
17
S
8
G
4
Posts: 461
Reputation: 6,077

Post » Thu Jun 27, 2013 7:20 pm

@Guizmus I like the idea of adding another layer to the array to keep track of the number of neighbors. Here is an updated example that also has a major optimization of only scanning through the edge positions where a cell can be made. It should be much faster, and the main slowdown will be from drawing all the sprites.
@sirrance i added some comments to help show what's being done.
https://dl.dropboxusercontent.com/u/5426011/examples18/maze_prim_faster.capx

Edit: thinking about it there may be a certain amount of bias with me using the repeat condition. There is no visual indication of this but not all the edges will be considered as the 10 created ones won't be picked until the next toplevel event. It may be of no relevance at all now but may be an issue if the capx were redesigned to make the maze instantly instead of progressively.
B
85
S
27
G
85
Posts: 5,062
Reputation: 57,858

Post » Thu Jun 27, 2013 11:41 pm

Thanks a million guys,
I'm Going to dive into this when I get home tonight.

Again thanks for the help.
B
5
Posts: 9
Reputation: 883

Post » Fri Jun 28, 2013 8:36 am

Wow very interesting, i hope that we see a dungeon generator soon (with rooms and corridors, like the plugin in construct classic :P
B
31
S
7
G
2
Posts: 159
Reputation: 3,739


Return to How do I....?

Who is online

Users browsing this forum: dmrev, DutovLoppa, just2pale, kototouchdown, mekonbekon, newt, OddConfection, VnM2016 and 9 guests