True Random Generation | Theory

So I make this both the fact that I am bored but mainly the fact that I feel slightly inspired by this post: Map Generation System And I said

And I would like to go in some depth about this

Firstly, the problem would be that whenever you think of true randomness if you do not have a code to make the generation playable by the player. Except my theory would be what if we could detect for specific parts that make it unplayable

this is only a experimental theory, so this would mean we need a small room for test filled with barriers or props in all directions at nearly every coordinate in that room. So imagine for example we wanted a maze? well we would want it to be playable instead of random barriers landing randomly somewhere. We want it to be a maze. we could go easy route with preset generations but you know me and my friend named “Stubborn” what if we could make a “maze” that every playthrough would be ENTIRELY random but playable.

so like said earlier I propose a system that will somehow detect specific property placement. this would require a lot of memory but like said in this example were supposing its in a small space.
We should maybe have key areas that barriers CANNOT spawn in so those areas would always be playable.

Second question would be: could we possibly figure out efficient ways to make this for spaces bigger than a small room?

Probably yes, but it would be still memory expensive but with some strategy and techniques there could be ways to make even bigger areas.

So I conclude this thought provoking thing going on in my head here.

Research should begin in chat. I get that this is semi probably impossible but hey
why not try to concoct something close to one. I worked kinda hard writing this (was not hard writing, just the explaining part) I will add more info soon enough more about my theory

15 Likes

Probably with SPECIFIC COORDINATES. Like, random numbers (coordinates) that IF this number is there, then this number cannot exist.

In order to make absolute random generation for a maze, you would first need to make a pathfinding system in Gimkit.

9 Likes

Or many, many layouts.

1 Like

I don’t got much to say because I wasted most of my side on the guide

So I will be back in like 20 to check on this

3 Likes

First off, resources.

Can’t think of anything else…

And now, the concepts.

This should work like a tree but with two ends.
It branches out, and then all ends at the same point.

Start → Branch 1 & 2
Branch 1 → 3 & 4
Branch 2 → 5 & 6
etc.

Now, the method.

2 branches, right?

num is greater than or equal to path1
do broadcast on channel example

The randomizer chooses random blocks, and the block code fixes the mistakes along the way.
You’d flood your channels or wires though.

4 Likes

Oh!
(idea)
With some barriers, you can do this. With a LOT of if blocks, you can do the following: Start with one barrier. This is your starting point. Put broadcast channel: Barrier(x,y)
Just loop the triggers, and make sure that the og barrier’s cords are randomized. When it reaches the end barrier, deactivate both triggers.

4 Likes

Hold on…
@Gimkitsuggestor, would you want the blocks to resolve the randomizer errors from the start or the end?

alr

the channel is called memeface72
You’ll get my joke if you play Roblox Bedwars… those people are bots.

5 Likes

anything that you think works

3 Likes

There are some things such as Kruskal and Prims algorithm that can help by making mazes. They are randomly generated, from scratch I believe. I’m trying to understand more on how they work and how me might be able to incorporate them in Gimkit.

4 Likes

Wow I’ve never seen a theory in the devices section or on the forums at all! (Not sure if that’s a good or bad thing)

1 Like

Impressive, I’ve seen a lot of them.

Also, apparently, the best method we could use to make small mazes would be recursive backtracking. I know recursive is know by some users, so we might be closer to our goal.

4 Likes

Remove the clay-institute tag, it’s not that hard to think about.

Here is an example maze, resolving from the start, with 5 branches needed to be open:

If randomizer1 = 1
do broadcast on channel branch1closed
This means that branch2 is open.

If randomizer2 = 1
do broadcast on channel branch3closed
This means that branch4 is open.

etc.

Now, the randomizers:

If randomizer1 is greater than 0:
broadcast on channel startrandom2

This could be simplified to wires, but I’m lazy right now.

See? Not that hard. If you don’t understand, ask someone else to rephrase it or me to over-simplify it.

clay-institute is for things that genuinely seem impossible without any research done.

This was possible, and seemed possible from the start.

4 Likes

Yes, the nearly impossible part is actually making sure the maze is possible using a pathfinding system.

4 Likes

… Pathfinding is easy if you have the right mind to do it.

Now, there’s no built-in system, but technically that system works, no matter how big the maze is.

There are up to 3 branches from the start, and that multiplies exponentially.
Variables are the best for this task, seeing as they can be used for multiple purposes, wherein properties don’t reset by themself and are global, meaning that if the property is used in multiple systems, you’d have to rework every one of those systems.

Using just one randomizer, we combine that with 1 variable to make this work, because…

… the numbers 1/2 or 0/1 mark true/false for every branch.

I’ll extend this tomorrow.

3 Likes

Possible. We need a way to interpret the first minute of this video into block coding. [1]

We have to keep a record of moves the generator has tried, and set boundaries for where it can go. If it cannot find an open spot, then it backtracks, hence the log that is needed.

I will work on this tomorrow I am able to :3


  1. The rest talks about how to make it in the Unity Engine. ↩︎

3 Likes

…
This website might help:

Oh nevermind that’s python, oh well, I guess I’ll just share another idea, but the logic of that post might help.


I forgot to mention, the following stuff I'm saying applies to if you had barriers applied in a grid-like way. Mark each cell of the maze with an id, the id being the coordinates. The id being stored in a property. Make it a text property so it can hold multiple values in a substring, such as coords, number of open directions, and, a special value that determines if it's a corner, side or a cell in the middle of other cells. The cell that the generation is started in needs to be random, as well. So, you'd need to randomly generate the first cell in a random location which the generation of every other cell will depend on. So, first, make block code that creates the first cell, then make the block code that will be repeated for every other cell. Now... I know what you might be thinking.. how will you create the repeation of cell generation if the first cell that is generated is not in a corner. Solution: thinking of all the cells in a square, the X position (in this case, just counting what cell you are on ON the X-axis) will reset to 0 or the max X. This also applies to the Y-axis. The generation will go X to Y, and count for every direction for all the cells on the X-axis. So, once the counter reaches ten, then the Y will be the Y+1. And then the same for the X-axis. Every cell is connected to 2-4 other cells, making the generation process easier yet more confusing. But again, the random location generation should only be for one of the axes, for what I'm going to explain next; pathfinding.

So, that will work, but if any errors happen, we’d need to re-generate.
So I thought about what Inky said about pathfinding.
I made a research topic which required pathfinding, and the system that finally worked could work for this.
So, first the um… let’s refer to it as “the pathfining”, will start above the maze. It will find any open cells at the top to begin the maze. And then it will… “rotate” if you will, and begin to look around for open cells, by using the properties stored in the data of the cell it is in.
If one is open, then it will proceed to move forward. This will work and not infinetely repeat itself by changing a variable, or just a number property attached to a counter with a target of 4. This will change which directions the pathfinding that it will go in, so it does not infinitely scout in a loop. Yet there is still a possibility it could happen. So a trigger loop and a counter will keep track of time to keep track of the pathfining loop to make sure it doesn’t go on infinitely or the maze doesn’t work so the player doesn’t have to restart the game if the maze generation doesn’t work.

A major flaw: the pathfinding can’t learn. It doesn’t have any stored memory, so it will likely regenerate quite a few times.

The final step: making sure there is an open cell at the end.
So, the pathfining system, I think, should have the ability to deactivate other barriers based on the location of the pathfinding, if it is at the bottom of the maze. One it get’s there, and IF it reaches and impasse, it will deactivate the barrier it’s at.
So, in conclusion I estimate around 80% memory.


Does this help, @InkyDarkBird?
5 Likes

I think this might be the solution to the pathfinding issue.

1 Like

I think we should assume that the maze only has one entrance and one exit and that all the outer walls are properly generated without holes besides the entrance and exit.

I will also be assuming that the pathfinder will have a direction property to indicate where the pathfinder will go next.

Now, moving onto some obstacles:
Let’s assume that the pathfinder starts by facing rightwards in the bottom left corner. There are 3 cells to the right of the pathfinder, and the 2nd rightward cell has a cell connected on top of it. The pathfinder naturally goes rightwards until it reaches the 3rd cell, and then it turns around. However, because the pathfinder only changes its direction when it hits the wall, the pathfinder will simply move leftwards back to the start, ignoring the cell above the 2nd rightward cell.

In order to prevent this from occurring, each cell would have to have a boolean property indicating whether or not a cell has been explored by the pathfinder already. Before each movement, the pathfinder should check if a cell has already been explored and keep “rotating” its direction until it reaches a cell that has not been explored yet. If the pathfinder can only move onto an explored cell, then it should.

To determine whether or not the pathfinder made it to the end of the maze, simply track the current position of the pathfinder using pseudo x and y coordinates to represent the cells and the start and the end. Assuming we are starting at a bottom left corner and moving rightwards and ending at a top right corner and moving rightwards, the starting coordinates should be x = 0, y = 1, and x = n + 1, y = n, where n is the height and width of the maze (which I assume is square).

7 Likes

Also, if all the inner maze walls are not connected, then each of the cells might need a numerical, instead of boolean, value to represent how many times the pathfinder checked the cell in order to prevent it from going around in a loop.

7 Likes