Jump to content
  • Advertisement
Sign in to follow this  
kitman20022002

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

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

If you intended to correct an error in the post then please contact us.

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;  
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]);
          }
       }
    }
    
  }
}
Edited by kitman20022002

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!