I’m trying to build a network of roads that don’t clip into each other, each road segment is represented as a List representing equally-spaced points along its length. Right now I simply compare a prospective new segment to every already-placed segment, and for each existing segment I simply run this:
List<List<Vector3>> accepted;
float segmentWidth = 3f;
public bool Intersects(List<Vector3> potential)
{
for (int i = 0; i < potential.Count; i++)
{
for (int x = 0; x < accepted.Count; x++)
{
for (int z = 0; z < accepted[x].Count; z++)
{
if (Vector3.Distance(accepted[x][z], potential[i]) <= segmentWidth)
{
return true;
}
}
}
}
return false;
}
It’s really simple, but it’s also incredibly brute force-y and the large amounts of iteration means that performance is going to scale down dramatically as the number of potential segments increases. Is there a more performant way to check if two List segments of a given width intersect, or is manually comparing the distance between their component points really the best way to go?
Mostly straight- they curve maybe 5-10% of the time, but I can change the rule to make them always straight if it makes reliably preventing intersections significantly easier.
Well my suggestion would be finding the equation that links each road, in graphical form and checking for intersections that way, whilst also adding on the width of the road to account for this.
For a curved road you COULD do the same, but that could really complicate the mathematics.
You could also check using basic colliders, OnTriggerEnter would work, and if they do enter, stop them from entering, for example.
How are the roads placed? Does the user place them or is it more procedural?
The roads are placed procedurally, but checking the colliders wouldn’t work since I don’t generate geometry and collision until the very last step. The roads are generated by an L-system which recursively iterates through newly-proposed segments, checks them against a set of constraints (e.g. ‘don’t intersect pre-existing road segments, don’t extend over water’ etc), and if a proposed segment satisfies every constraint, it’s moved from the proposed list to the accepted list.
The check I’m trying to improve is one of the constraints- it basically gets handed the segment (e.g. the list of vector3 coords the proposed road section would occupy) and a list of already-accepted segments, then checks segment-by-segment to compare their vectors3.
The reason I can’t use triggers/collision checks is because they only exist in data until I’ve pruned the list down to the final set of segments that satisfy every rule, then it meshes and builds collision for the good segments and calls it a day.
In that case, what @mbaske said is pretty ideal. Limiting the list of which you iterate over could really save you time. I.E: For each point, only iterate over a point that is within a distance that is less than the size of the road.
If the roads are perfectly straight, you can just use the first and final positions to create one big line segment, and check that against the other big line segment, and simplify this immensely. If the roads allow for curves, there’s really only two ways to simplify it that I can think of:
Create a proxy object that “more or less” adheres to the same shape, but has less points to check against. You can do this by taking all consecutive segments that are straight, and making a new object that combines them for faster calculations. You can do something similar for the curves using math, using different curve types with faster algorithms but less granularity in the detail, but that’s beyond my ability to assist with.
Use a kind of binary search tree in order to narrow down the possible intersections before checking against specific intersections. Some research into K-D trees and binary space partitioning may be in order.
You can implement a really dead-simple pseudo-version of the second concept by creating an array[X, Y] (or Dictionary<int, Dictionary<int, List>>) and breaking your whole scene down into 500 meter “blocks” or something (just make sure the length of X and Y units is larger than the largest single segment length for a piece of road). As pieces of road are created, place them in each of the lists that they match to in physical space, so for instance with 500 meter blocks, something placed at 750.2, 125.3 would go to [1, 0] (be sure to place them in every blocks where they cross into). Then when checking for intersections, you only need to check against that specific block, because all others are too far away to possibly be intersecting.
For what @DonLoquacious was saying about the curves, finding the gradient at every +1 interval in x,y,z and integrating will find you the equation of the line at that point which you can then use to check for intersections, but personally I believe what you’re doing currently is most likely better than doing that.
I really appreciate the feedback guys, obviously math isn’t my strong suit and this was really helpful. I’ve gotten it more or less working checking the points, there’s still an occasional bit of weirdness, but I’m confident that it’s mostly edge cases that I can buff out in the ruleset. So thank you again!
