# TOO SLOW; TOO ERRONEOUS - HELP with Building a Procedural Road System Using the Voronoi Diagram.

This topic is 1271 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am trying to build a procedural road system using the Voronoi Diagram. I have included a diagram illustrating my method for building roads based on the Voronoi Diagram. In theory I have coded a way to accomplish this but will be super slow I guess.So I am wondering if anyone has any feedback or suggestions on any others methods to make the process more efficient. Thanks for help The idea of of my code and image are below :

//High level description

Create two list

InterestionsList (this only hold points and lines)

CreatedRoadList (this list hold the mesh or we can say this list hold the lines that already been created from InterestionsList)

loop through InterestionsList and every item in InterestionList create a intersection

get all the lines that are connected to that intersection

check has the lines been create if not then create the road and connect the road to the intersection

else just connect the road to the intersection

List<Interestion> InterestionsList;

void CreateInterestion(List<Interestion> inters , int connectedroad)
{
//build mesh
}

void buildroad(float startX , float startY , float EndX , float EndY)
{
// build mesh base on the input value
}

void ConnectInterstion(Mesh m , Lines line)
{
//connect intersection and the road base on the road dir and position
}

void Update()
{
for(int i= 0 ; i< i<InterestionsList.count(); i++)
{
InterestionsList[i].getPosition();
Lines[] lines = InterestionsList[i].getConnectLine();

CreateInterestion(InterestionsList[i].getPosition() , lines.count)
for(int i= 0 ; i< i<lines.count(); i++)
{
for(int j =0 ; j<CreatedRoadList.count(); j++ )
{
{
ConnectInterstion(m, Lines[i]);
break;
}
else
{
Mesh m = buildroad(Lines[i].Start.x, Lines[i].Start.y ,Lines[i].End.x,Lines[i].End.y);
ConnectInterstion(m, Lines[i]);
}
}
}

}
}
Edited by kitman20022002

##### Share on other sites

Look up algorithms which perform Voronoi tesselations of a field of points, and/or look up algorithms for a Delaunay tesselation and then take the mode of the produced graph (viz; replace polygons with vertices at their midpoints, and replace vertices with polygons which have a perimeter formed by connecting the new vertices created from their former adjacent vertices).

Looks like you have more intersections than specified points, so add some extra points to your data with random midpoint-displacement subdivision or something before feeding it to the tesselator.

##### Share on other sites

Some questions about it being "slow".

How many items do you have in each of your lists?

How many times are you going through your lists?

For your description, you've got "Loop through, and for each, and if it hasn't been created, take an action"  Beware of that kind of statement if you're looking for performance.

That looks like you've got a triple nested loop over the collections.  If you also have a large number of items in that loop, it will be very slow.  In computer science, a triple-nested loop like that would be called an O(n3) operation; the number of actions is the cube of the number of items. Consider if there were 10 items, that's a thousand actions.  If there were 100 items, that's a million actions.  If there were 1000 items, that's a billion actions.

Another concern is that making new objects is potentially a slow action, especially if your collection of items must grow many times.

These could be reviewed if you post a link to your actual code.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634088
• Total Posts
3015453
×