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

Started by
1 comment, last by frob 8 years, 8 months ago
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;  
List<CreatedRoad> CreatedRoadList;

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)
{
   Road road = new Road();
   //connect intersection and the road base on the road dir and position 
    CreatedRoadList.Add(road);
}

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++ )
       {
          if(lines.ID == CreatedRoadList[i].ID)
          {
             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]);
          }
       }
    }
    
  }
}
Advertisement

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.

RIP GameDev.net: launched 2 unusably-broken forum engines in as many years, and now has ceased operating as a forum at all, happy to remain naught but an advertising platform with an attached social media presense, headed by a staff who by their own admission have no idea what their userbase wants or expects.Here's to the good times; shame they exist in the past.

Some questions about it being "slow".

First, if possible, please give link to the actual source code.

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.

This topic is closed to new replies.

Advertisement