Actually now that I look at that blueprint again you can see that in that section I am actually doing the entire creation and populating of the “Mesh” array.
It is just an empty array to begin with and it checks if that mesh exists in there and add’s it if it doesn’t.
@ZoltanJr: I promise you, if I had the slightest idea how to do the tree-growing thing you mention, I would totally do that. My current polygon-thing is only an option because it’s the only way I can currently put together and understand without an actual map to show me how. But hey, gotta start somewhere. I learn every day. 
Your generator sounds awesome. I’d love to see a shot of what it produces, but I can totally understand if you want to keep the actual blueprint private.
Give it another week or 2 and I will slowly be getting there. At the moment it’s all in bits and pieces so not really worth showing the end result. I keep jumping between the different functionalities when I start to get bored or frustrated too hah.
There was a twitch stream the epic guys did a little while ago showing off how they made these procedural vines and stuff, that actually seems like it could be a decent method for growing roads from a seed too. I will see if I can find it. The guy who made the “Dungeon Architect” plugin was also working on a city generator system, mostly just the roads side of things but im sure he will combine all his knowledge together and blow us all out of the water with everything too.
@ZoltanJr: Ahhh yeah, I remember that stream, I was running it in the background at work, but didn’t really pay proper attention. You’re right, might be some good stuff in there.
[Edit:] Found it, starts on the procedural vines and roots about 58 minutes in. Paragon Feature Examples: Foliage & Parallax Occlusion Mapping | Feature Highlight | Unreal Engine - YouTube
I dont know if thats still relevant, but in case you still nedd a way to make a irregular shape that doesnt fold over, her is what I used in one of my 2D projects:
Draw vectors with variables length from a set origin, do this clockwise or counterclockwise with random angle incerements and vector lengths.
Then connect the points. The resulting figure is guranteed to be convex and non folded.
@KVogler: It’s definitely relevant! Sounds like a cool approach. I’ll give it a shot. Can you give me a hint about how I might generate a vector along a set angle? I actually tried to do that in another situation yesterday and had to give up, I couldn’t figure out how.
Ok.
I start witha a vector in a default direction (RND/0), being a vector of random length, pointimg “to the right”.
Then I rotate this vector (or the onit vector counterpart of it) by a random degree angle. After the rotation, I scale the vector to a new arbitrary length.
You just keep adding the rotation angles up until you accumulate 360 deg (or 2pi rad):
EDIT: Just saw that I forgot to include the brown line in my masterpiece… But I guess you get what I mean… 
When you connect the points to a polygon, say clockwise, the next vertex is guaranteed to be “left” of the current one. So folding over is impossible, no matter what the random values are.
Just avoid the zero vector, so set reasonable ranges for rhe randoms in length and angle.
The functions are quite simple. Here is the code.
(Sorry, no C++, Im a Delphi coder).
Please note that in Delphi a function does not return result assignments immediately to the caller. Only if the function body is left, the result is returned, making the result effectively a local variable.)
type
TVector = record
X : extended; // X component
Y : extended; // Y component
end;
const
SafeZero = 0.000000000000001; // A "zero" that you can safely divide by
VZero : TVector = (X:0;Y:0);
VBaseX : TVector = (X:1;Y:0); // Vector space base vector, X-axis
VBaseY : TVector = (X:0;Y:1); // Vector space base vector, Y-axis
function VRotate(V:TVector;A:TScalar):TVector;
begin
Result.X := (V.X*cos(DegToRad(A))) - (V.Y*sin(DegToRad(A)));
Result.Y := (V.X*sin(DegToRad(A))) + (V.Y*cos(DegToRad(A)));
end;
function VScale(V: TVector; S: TScalar): TVector;
begin
Result.X := V.X * S;
Result.Y := V.Y * S;
end;
As you can see, the rotation is a simple implementation of the rotation matrix : https://en.wikipedia.org/wiki/Rotation_matrix
If you have the above setup, you can then place some of those polygons randomly near/over each other, so that they overlap in an interesting way.
Then you check all polygon edges for collisions.
My collision test looks like this:
type
TCollisionResult = record
C : boolean; // Collision result
P : TPoint; // Collision coordinates
end;
type
TLine = record
A : TVector; // Line start
B : TVector; // Line end
end;
Function VCollision(P,Q:TLine):TCollisionResult;
Var
T,S,N:Extended;
Begin
Result.C := false;
N:= P.A.X*Q.B.Y + Q.B.X*P.B.Y + P.B.X*Q.A.Y + Q.A.X*P.A.Y -
Q.B.X*P.A.Y - P.A.X*Q.A.Y - Q.A.X*P.B.Y - P.B.X*Q.B.Y;
If N=0 then Exit;
T:=(P.A.X*P.B.Y + P.B.X*Q.A.Y + Q.A.X*P.A.Y -
P.B.X*P.A.Y - Q.A.X*P.B.Y - P.A.X*Q.A.Y) / N;
If (T<0) or (T>1) then Exit;
S:=(P.A.X*Q.B.Y + Q.B.X*Q.A.Y + Q.A.X*P.A.Y -
Q.B.X*P.A.Y - Q.A.X*Q.B.Y - P.A.X*Q.A.Y) / N;
If (S<0) or (S>1) then Exit;
Result.P := point(Round(Q.A.X+T*(Q.B.X-Q.A.X)),Round(Q.A.Y+T*(Q.B.Y-Q.A.Y)));
Result.C := true;
End;
When you then subdivide the polygons at the intersections you get a nice network of random roads that dont look too fabricated…
That’s actually the method I thought he was doing before, just with the odd mesh and socket to figure it out.
Get the central point which would be 0,0,0 on your blueprint.
Generate a random number to divide the circle by (3-30 let say)
Divide 360 by that number and add some randomization in there to give them different angles.
Generate a random distance from the centre along that rotation to get your point.
Store those points and then spawn a spline along them.
You could change things about and generate a random angle rather than the number of points first might make things easier but I would personally like to have the control over the number of points.
That is the difference indeed. It is much simpler to accumulate random angle values and just stop once you reach 360 that distributing random values to a set number of points so that their angular sum makes exactly 360. Also keep in mind that just assigning random values to the rotation wouldnt work. Its the strict ascending (or descending) order of point “orientations” that prevents folding.
If you apply the second part of my proposition, the number of points becomes random as well (no point in setting it… pun intended 
)
As the shapes will overlap randomly an rbitrary number of new intersection points may be generated…
The number of points could be influenced however by the rotation value range.
For example, if I choose random angles between 36 and 72 deg, the polygon will have no less than 5 and no more than 10 line segments.
Well the sum of the angles doesn’t necessarily have to equal exactly 360 degrees, as long as its 270-360 it’s fine.
I was actually thinking of a way this could be improved to create the entire road map too. Not sure how it will actually turn out though but with some set params i think it might be ok.
So lets say we start out with a square. We generate a spline for that with 90 degree angles. We then store those 4 points in an array with each of the 4 points having an “unoccupied flag”.
We then do a loop to go from each point and use the 360 rotation method.(the loop is valid on all with false on the “unoccupied flag”)
Starting from the first point we can get the direction vector of the incoming and outgoing and know that we have 270 degrees to work with. So we do our random distance outwards and the random angle between 30-90 and stop when it gets >=270.(Or a random maximum so that we get more right angles potentially,depending what kind of roads you want)
Rather than generating the full spline again this time though we actually go and find the closest spline point to the first new spline point. That becomes our starting point for the 2nd road segment. Then we trace along the rest of the spline points in order until we get to the last 1. Then it’s the same deal with the last. Rather than join it back to it’s first point, we go and find the closest spline point again (ignoring it’s own spline) and make that the end point for it. We don’t bother to create a closed spline because it will get the illusion that its a closed spline by joining up with the first 1. Now whichever spline points we have used as the first and last on this become marked as "occupied"and we then jump to the next unoccupied 1 and do the new spline again.
For the joining on the first and last 1s we probably want to clamp the angle again and only look for closest within that angle etc. And then make sure it’s not occupied, but this could probably be enhanced to handle maximum number of connections maybe.
I might have a crack at this later today if I get a chance but I wont be back on it until Monday most likely
Another thing I forgot to mention here was that when the spline is generated I would attach a placeholder mesh on it so that there can be line traces to check that it doesn’t crash into another road. If it does then you increase the angle of the first 1. So you would do that before spawning each point. Another improvement here would be to check the distance to the closest spline point (corner) and if it is above a certain distance than you just shorten that length to be a new corner.
Actually just came up with another piece to add in there too during my playing around.
If we keep all of the initial line draw out’s that we did from each of the spline points I have found that those can then be used to create the smaller streets to join between the main roads and it looks great. Just need to do a check on the points they start and end on and make sure they don’t have more than 4 or 5 intersections and that the angle would be in the desirable range then you spawn it as a smaller road and you don’t have to worry about doing another breakdown to add smaller streets. Surpisingly effective actually
I usually made a random rotation between 5 and 10 degrees and used the accumulated angle in a while-less-than-360 loop. So the maximum gap would have been close to 10 deg and give me between 36 and 72 vertices…
Thats too much overhead. Take into account that if you connect two points of different splines this way, you may create new crossings. So this would have to deone recursively.
On the other hand, if you just create some splines (simple operation, just repeat it). Then process the splines linearly for overlaps. Also done very simple (crossing of line segments test). And because you only add the intersection vertices and dont add new lines, you dont create new crossings in the process.
The next step, if needed, would be an associative list with all vertices (individual splines are no longer relevant at this point) that map the neighborhood relation of them.
This provides then also a basis for efficient path finding on the roads. (You could store the travel costs as edge weights of the graph).
EDIT:
here is a little graph to illustrate:
(forgot one red-blue crossing…)
First all colored polygons are created with the circular-random-sweep method from above.
Then all polygons are tested and the new vertices (black) are creted and the colored polygons subdivided at these points. So per intersection, the number of two polygons increases by 2.
Then, we can view it as one connected graph now.
PS: This way, you will only get vertices with max 4 connected edges, unless 3 or more polygons cross the same point. it is more likely to have intersections that are not exactly congruent, but very close.
You can then still collapse vertices by averaging them and connecting all edges to the new vertx. For example the red/blue/purple triple near the conter of the graph could be merged to a 6-roads crossing…
this way you avoid super short edges if intersection are too close…
You can also use polar coordinates and convert them to your vector cartesian coordinates.
So you’d have your origin, number of points, and min and max distance from the origin (the polar distance, keep these the same for a regular polygon) as inputs, then either divide 360 by the number of points for a regular polygon, or use some random value between a min and max angle (not bigger then 180 or you can get complex - overlapping - polygons) to have the polar coordinate angle. The min and max angle could also be inputs. Then convert the points generated from that to local (in relation to the origin) carthesian coordinates, and do the Z trace from there.
True. I also use polar coordinates, but since he wasnt sure about the concept of rotation matrix, I avoided to make it even more “complicated”…
But if you want to use polar coordinates, this is what I use for conversion:
type
TPolar = record
R : extended; // Radial component
A : extended; // Ascension component
end;
function VLength(V: TVector): TScalar;
begin
Result := hypot(V.X,V.Y);
if Result = 0 then Result := SafeZero;
end;
function VectorToPolar(V:TVector):TPolar;
begin
Result.R := VLength(V);
if Result.R = 0 then Result.A := 0
else Result.A := arctan2(V.Y,V.X);
end;
function PolarToVector(P:TPolar):TVector;
begin
Result.X := P.R * cos(P.A);
Result.Y := P.R * sin(P.A);
end;
This all looks awesome. I’ve been pondering how on earth to do intersections, and this looks very promising. It’s sadly way out of my league just yet, I’m afraid. Basically, once it involves actual code, it’s beyond my artist-brain. 
I tried my hand at setting up some math but I ran into something i cannot figure out.
I can generate a pretty clean circle, but how do i make it so my points are distributed over the total circumference? I’m at a loss
&stc=1 &stc=1 &stc=1 &stc=1Well, for quite a while I was looking for a nice little project to code. This thing had made me start to code something like a graph editor that could be used to create these type of road networks. I just started with it yesterday, no not much progress, since Im starting from scratch. But once I get to a presentable alpha state, I can send you a preview link.
I couldnt really figure out your BP graph, so I made a little example.
Here it is
Start with a BP, based on actor, add a Spline component and make it the root. (why not :p)
Then we add a function that does nthing but adds a splinepoint to our spline. Yes, we could call the AddSplinePoints method of the spline also from our other code (commin up next), but Id like to keep things separated in functions… Thats just a matter of style. Oh, and dont get bothered that I named my function “AddSplinePoint” as well. Thats perfectly ok…
Next, create a function, called GenerateCircle that does the follwing:
The local variable AbsoluteAngle has 0 has default value.
Now just call the function from your construction script. The length of the pointer dictates the circle radius. If you replug the float add node from fixed value to a random range, you can also get irregular shapes.
With fixed values, it looks like this:
So, that gets the points going. Now the random modulation of our pointer length would give us the random distorted polygons that never fold over…
Just add a random scale multiplier:
And you get this:
Of course with less extreme paramters, you get more decent and natural shapes… 
To account for height changes, which will require square-root-2 more splinepoints for 45 deg inlcine for example.
This sis indeed a bit tricky. Taken the BP from above, you need to interpolate the delta elevation between two spline points.
That means you would need to store an array of spline point coordiantes and insert them appropriately.
A bit like Zak Parrish made the SplineTrack Editor tutorial.
https://www.youtube.com/watch?v=wR0fH6O9jD8
however in your case, since you want to insert, you dont need the add and remove logic he is using.
Just rebuild the spline from scratch each time… (like I do above)
@KVogler: I’d absolutely love getting a look under the hood of that if you’ll allow me. My approach to learning more advanced stuff so far has been to track down blueprints that sort of do what I want, and try to reverse engineer them. “Ahh…so when that goes in there, it does this…!”-kinda thing. It’s served me well so far, at least for the not-too-complicated stuff. I’ve saved the entire series of pics you just put up - I wanna recreate it while trying to figure out what makes it tick step for step. It’s pretty close to the one I’ve done in some regards, but I definitely see some things done smarter in yours. Also, thanks a lot for that stream-link, that looks really good! Will watch it right now.
Anyway. I pulled KVogler’s lovely blueprint apart and added some pieces from my own previous version. That allowed me to get rid of my janky “rotate a mesh with a socket on it”-version of getting coordinates for my spline points, and finally got a way to make sure the points never cross. I think I’ll be calling the basic spline generation done now. Thanks so much for the hints.
Next point of order for me should probably be to spawn a bunch of those circles, within a set distance from each other, and spawn connecting “roads” between them, as per my original plan:
So one way would be this:
Or, if I figure out how, since I sort of prefer this in my head:
