Alright, this doesn’t look like much, but I am now using a flipflop to generate the walls. I store each wall as North, South, East, West, and a boolean called “Outside”. This allows me now to start doing a depth first search, and “visiting” each tile. If it can’t go between two cells, it will delete a wall. It will then switch to a new random unvisited cell, and do the same thing. I am almost finished with it.
Alright, I think I’ve figured it out. I will post the results once I consider it a little more stable.
I’m pretty close on my alternate version, too. I’ll send that one to you when I’m done for comparison. I think I’m having a problem with my processed count and the while loop. I’m messing around with that right now but compiling is taking a long time now so I know i just messed something up. Lol
That’s pretty funny, I am running into the same issue. I decided to re-approach it from a much simpler standpoint.
Wow, I didn’t expect it to take this long, I’ve never created a maze without a 2D array (let alone in blueprint), and this is a challenge. I think I am going to step back, and instead create an entire project dedicated to procedural mazes. I will toss you a copy when it’s done. I need time to figure this out correctly.
Everything I’ve done so far is not generating paths correctly.
I will get a fresh start on this tomorrow, good luck on your side.
Yeah, it’s DEFINITELY a learning curve to attempt this with a one dimensional array AND doing it in BP. But I’m also getting closer. Still having trouble with the pathing on this side, too.
TECHNICALLY speaking, I should have a complete North wall, and a complete East wall. But I’m only ever getting one or the other. AND there shouldn’t be any inaccessible parts, but I’m still running into that also. BUT I have to agree: besides all the aggravation (and cigarettes), I’m enjoying the challenge of moving to this way of thinking. One thing is certain, I think we’ll both be a whole lot smarter when this is sorted out. LOL
I’m packing it in for the night, too. I’ve fought with this enough today, too.
So, I decided to take a new approach. It’s not quite done.
- Generate the floor tiles.
- Generate 4 walls for each side and assign them an enum.
- Give each wall a tile owner, the floor tiles act as cells.
- The image is where I left off. It chooses a random tile, and then goes into the main loop.
- It chooses a random direction based upon the wall enum.
What’s not done:
- It checks that tile to make sure that the direction is free, and if it is, it makes sure that the flag Is Swept is not true.
- If it meets those checks, it deletes the wall for that direction the last tile, and the opposite wall on the tile we just checked.
- It then marks that tile as swept.
- The while loop then kicks back over, and it chooses a random direction from our new tile.
- If for some reason the tile fails the check, then it just goes back and tries again, the while loop will run until processed tiles == the tile count.
- We don’t increment the processed tiles, unless we make a successful move.
To check for up and down on the Y, just add or subtract Size Y, to check to make sure we are not on the sides, make sure that we are not a multiple of Y. I added a macro called Is Multiple. You just plug the index (that’s the one on the struct, not the actual index) in to the first part, and the number to check against is the Grid Size minus 1. That will tell you if you are on the side of the grid.
I will PM you the project if you want to continue where I left off. I will be attempting more work on it after work tomorrow. You just need to continue on the switch position and figure out the task above. Everything else works great.
This is how to do a side check for X:
Basically, you want to preemtively set the Current Tile to the new value, even if it is wrong. So say for example I was checking the next tile on the Y Up.
Current Tile = Current Tile + Size Y
I would do this first, even if it is outside the check. Then the check would be.
If Current Tile < Grid Size - 1 Then (We are inside the grid.)
Say we were checking X Left.
Current Tile = Current Tile - 1
If Current Tile > 0 and IsMultiple(Current Tile, Size Y - 1) Then (We are inside the grid.)
We can know if we are on the edge because the edge will always follow a multiple of SizeY-1. You can’t just subtract 1, because we could land on the end or beginning of the last row. Let me know if it helps at all.
Grid Spacing - The size of each cell.
Grid Size - SizeX*SizeY
Random Seed - Because we generate a new random number each run.
You are wanting to continue from “Cut Maze” on the switch.
I brought my development laptop to work to work on it some more and look over my logic, and I’m actually thinking I also may have a flaw in my processing the edges, but I’ve got to double check that. I’m treating (0,0) as being the bottom right corner, and (5,5) as being the top right corner. This gives me an array of 0-24 for my index values. SO:
Given that SizeX and SizeY are the number of tiles in each direction, and index is the current 1D tile number (array index):
if ( index%SizeX == 0 ) then we’re a left side tile and can’t go West
if ( (index+1)%SizeX==0 || (index+1==SizeX*SizeY) ) then we’re a right side tile and can’t go East (This is the worst one.)
if ( index > (SizeX*(SizeY-1) ) then we’re on the top and can’t go North
if ( index < SizeX ) then we’re on the bottom and can’t go South
Now I’ve just got to make sure I’ve implemented that properly in this new BP. The reason I’m suddenly doubting myself on this is because with this new version I’ve been keeping the 2D thinking and converting to a 1D as needed when processing the array. But I’m thinking that this time around I’ve flubbed the proper boundary checks because of treating the grid this way. I still need to pour over it to make sure, but there’s a problem SOMEWHERE, and this could be another spot where I’m missing something. This will be where I start when I’m out of work and have a clearer head.
I’m definitely going to post this version for you to download and check out, and I’m looking forward to seeing your solutions, also. Gotta admit, this is just as much fun as it is aggravating.
This is where I think my current version may go astray. But the LocalY and LevelSizeY-1 should be enough for it to trip the branch and catch any problems with an improper checking of the array. But I’m going to add my extra steps in here and see what happens.
I’ve resorted to some creative debugging techniques to try and track what’s going on. I added a GridX and GridY to the cells to store the actual X and Y locations of each of the tiles X and Y coordinates. Then I wrote a TestBuild function that uses a ForEach loop to iterate through the entire array and place a tile with all the walls on the sides that got marked blocked. The results are quite shocking. Now it’s a matter of deciphering the similarities of each compile to try to figure out where the execution path is breaking down. So far I’m not seeing any East walls being placed at all, and originally what should have been 25 cells in the array actually counted up to 27. (That helped track down one problem). This is the “debug” build viewport: Each step is 50 above the previous in execution. And there are certain steps that get missed altogether. Very puzzling.
And this is the “Frankenstein” function I wrote in place of the normal build:
LOL! Definitely the crappiest looking BP I’ve ever written, but it works. lol
Holy *! HUGE smoking-a-cigarette-epiphany moment!! I just thought of a MAJOR oversight in my computations! I’m still using x and y coordinates and converting them as I need by calculating xy instead of the CORRECT formula of (YSizeX)+X HUGE FACEPALM
I’m an idiot!! That’s such a rookie mistake. I can’t believe I never thought about it before! Time to go adjust some computations and see what happens. That explains why the paths seem to stop at the edges and some other anomalies I’ve seen! Besides, that’s not even the math I need.
I am using X and Y, but X and Y are referring to a grid layout that multiplies against grid size. I just about have this working right. I am using a simple river algorithm. So we will see how it goes.
I figured out a way to massively simplify everything using a little smart math. I think you are going to like this setup. I will post a screenshot and maybe the whole thing shortly.
All I need to do now is some adjustments with my step back routine, and it will be working perfectly.
I created some really useful functions like “Cut Between Indexes”.
It needs a couple of small adjustments, it is making some unreachable places. Nothing that can’t be fixed real quick with a complexity check. I need to do some speed adjustments though. The bright spots are where it started again after getting trapped. The blue spots are paths.
Even weirder, it only works with square mazes. Trying it with a rectangle maze leads to outer walls being eaten.
This project seems to have broken Unreal, as I am being forced to manually locate my engine installation upon launching now. I guess all those loops just killed it. I need to work on a better depth recursion method that doesn’t eat so much memory.
Right now, a 10x10 maze takes an hour to generate, which is way to much. I do have a load of useful functions now, like testing if you can go a direction, and deleting walls between directions. So you might find those helpful.
For now, I think I will get some sleep.
I got to make some changes to my own some more last night after realizing my math error. Didn’t fix all my problems yet, though. Still not sure why my eastern walls aren’t being built, and my pathing is stopping early, but it’s behaving QUITE a bit better.
I’m also running into a complexity issue with relatively small mazes taking a long time to generate. 5x5s seem to work just fine, but larger mazes like the 10x10 you mentioned are taking forever over here, too.
I’m really close on this one now, I can feel it. I think I may have broken a few things while trying to fix a few other things and I just need to go back and look at the BP flow against my old source code.
BTW, I did download the one you sent me last night, but didn’t have time to look at it yet. If work is slow again I should be able to do some work again this morning and check out what is there.
I’m curious how you got yours down to such a small size. I guess I need to figure out a way to only include the used items when zipping it up. But then when I did a test build of my oculus project, the executable and data directory came up to almost 2GB just for a very simple map, also.
That reminds me, I don’t know how you’re able to debug your BPs. Every breakpoint I set or any watches I set don’t seem to do anything. Even in simulation.
That project I sent is now outdated and useless. Like I said before, you need to delete your Intermediate and Saved folders before sending a project. I will send you the new one later tonight.
I made some great progress in my down time, I came up with a novel way to handle the 1d problem without slowing everything down. I will post the results tonight.
Awesome! Can’t wait to see it. Where possible I’ve tried precomputing the math to variables and using those. Thankfully because I’m doing this, that stupid math error only needed to be changed in one spot so far as I could tell. I’m about to try to get moving on it a bit more shortly.