- Home /
Question is off-topic or not relevant
Generate closed, random path in C#
Good evening,
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.
Daniel
There are a number of different ways to approach this problem. I think the list could be more helpful if you specified final goal path and how you will handle all the conditions:
Are you going for perfect right angles in your turns or do you want something more arbitrary?
What does it mean (if anything) when the path crosses itself?
What is the purpose of the path?
Are the path segments to be of the same length or of a more arbitrary length?
How is the path contained (rectangular region, circular region, other).
Is it truly random, or are you looking to wander?
Etc.
Answering your questions :
Yes as a start I will restrict the creation process to right angles. The important part for me is to fully understand the process first. I can then modify things later - hopefully.
I have to admit, I forgot about that problem. Indeed the path should not cross itself - and I see the possible problem here as well. What if the path creates a cage for itself. This would be another problem , that I could use help with.
The path is going to be the basic for a board game - (ultimately this board game will be played on an uneven terrain)
To keep things simple, YES all dummy-path-nodes have the exact same scale, rotation, etc.
at the moment the path has no boundaries yet. But for a start I am thinking of either creating a grid [row][column] or a rectangular "cage" with colliders attached to them and if a path-node will reach an adjacent position to the border it will not be possible to build another path-node colliding with the border.
I do not fully understand the question. It is random in the sense that I do want to create a new circular path every time the game starts
(so basically everytime the game starts the player has a new playing field)
Thank you for your interest.
this is a general program$$anonymous$$g question.
it is not related to Unity.
ask on stackexchange, or gamedev
Answer by robertbu · Feb 07, 2013 at 05:57 AM
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.