I am currently working on generating a random path. To begin with I am using cubes as dummy-path elements.
The idea itself is fairly simple : place a pre-specified number of dummy-path (cubes) elements on plane - right next to each other in such a way that they will form a closed circuit. Each dummy-path-element will have 4 possible “docking” points ( cubes - 4 sides 90°).
My idea was to create a “dummy-path” prefab (cube) that would have 4 empty game objects attached to it - each being a/2 unity away from the prefabs centre ( a = length of a side of the cube).
I would then use Random.Range() to create a random integer to choose one of these 4 instantiation points and instantiate a new dummy-path-node at this point and so on.
For obvious reasons I would restrict the 3rd and all following cubes from instantiating at an already blocked point. …
I simply cannot think of a way to finally end up at dummy-path element 0 or in other words, how can I create an algorithm that realises “i have only 5 more nodes left to get back to my origin” ?
alternatively → do you think it would be better to generate a grid instead of having those 4 instantiation points ? ( ultimately i want this path to be creatable on uneven surfaces - that is why i am struggeling with using a grid).
Thank you for your help. If the problem is not stated precisely enough, please let me know and I will try to reformulate it.
I can think of a couple of different approaches. Here’s the one I like best given your specs. Start with a grid with a one unit square path (four lines). At each iteration, randomly try to replace one path segment with three new segments.
The red line is a candidate for replacement. Blue is the replacement. For Inside corners, you have a choice. You can either leave them alone, or turn them into outside corners. You might play with both to see which produces the best results.
A candidate would fail if 1) it creating it would impinge on the existing path, 2) it runs outside the boundary you set for your path, or 3) inside corner if you so elect.
Processing would continue until 1) the path is a long as you specify, or 2) the code had tried and failed to extend the graph a defined number of times on a given turn. In case #2, you have the option of tossing the path and starting over.
I would use two data structures to implement the algorithm. The first would be a two dimensional array of booleans. Each bool would represent one end node of each path segment (i.e. where the blue lines intersect below). The value for the position would be set to true if the a segment starts or ends on the intersection.
The second data data structure would be a list of positions in the order of the path. I would define a struct that contain just two integers for Row and Column. The array would be from the List class with each element one of the these row/col structs. So walking this list from the start to the finish would be the same as walking the path from point to point. When a new three-sided path segment is inserted, the original segment would be removed from the list and the three new ones would be inserted so that the list always remained in path order. As the new path segment is inserted, the boolean values in the first data structure would be set to true for any new nodes used.
A couple of thoughts. For the 2D boolean table of values, if you set all the outside edges to true, you won’t have to have special code to detect the bounds of the array. For the list, you might consider making the last entry in the list equal to the first (i.e one extra entry). This might avoid some nasty special purpose code.
Once you have the finished path, you can translate the row/column entries into real-world coordinates based on the size of your game playing area.
