Use Prim's Algo to make a tile maze

Post reply
0 favourites
  • 7 posts
From the Asset Store
Piano tiles
$9.99 USD
Template for a piano tiles game, fully documented in comments and video
bartalluyn's avatar
bartalluyn

  • 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: youtube.com/watch

    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

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads

  • I had a crack at it and here's my result:

    dropbox.com/s/ufmptfuadafxz76/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.

  • 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.

  • 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

  • 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.

    dropbox.com/s/gr2b0phywb7ycvq/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.

  • Thanks a million guys,

    I'm Going to dive into this when I get home tonight.

    Again thanks for the help.

  • Wow very interesting, i hope that we see a dungeon generator soon (with rooms and corridors, like the plugin in construct classic :P

Post reply
  • 7 posts
Return to board index
Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)