- Home /
Directed Graph: Extract Cycles and Dead ends
Here is the situation:
I am using a number of vertices to build a road network. Most vertices point towards another (root) vertex - except the first vertex. A vertex can only point to one other vertex. A vertex may be the root of multiple vertices, but at no time one has knowledge of how many vertices are pointing to itself.
Now I need to find unique cycles in that graph to get enclosing polygons, which I then use to place buildings. However I also need to get the dead ends of this graph, since a polygon edge may be cut by one or more dead ends, or nearby dead ends could be used to form a cycle.
Could you give me any advice to tackle this problem, please. Especially if there is existing code for Unity to speed up development. Any help would be appreciated.
Answer by Owen-Reynolds · May 08, 2013 at 02:11 PM
Sounds more like just a straight algorithm problem -- nothing to do with Unity. Some comments:
Is there an underlying grid? Most graph algorithms don't care about the space in-between verts (the concept of the area inside loop ABC doesn't even make sense, often.) Might be easier to draw the lines on the grid; maybe mark dead-ends special, and then run something to find connected areas of that grid (find an empty space, recursively find all connected free spots.)
Graphs on 2D surfaces are, I believe, called "flat" graphs, if you do a search. Also, technically, if a vert can only point to one other, the edge only goes that way, so there are no cycles. Traditional graph code assumes you point to everyone who points to you (this is if you search for flat graph algorithms.)
[edit]
If the graph really generates well-formed N-gons (no internal dead-ends, or crossing edges,) you could try this: consider each edge has two sides, and each side may be facing an N-gon. Might have a separate edge list to make it easier.
Pick any edge and one end to start. If you look from start to end of that edge, your right side is the possible N-gon (so when you start at the other end, you're checking the other side.) Follow edges around until you get back. To do that, go to the end vert of the current edge and search the edge list. For each, transform to local coords of the current edge (vector from start to end) and find the angle. Closest to 180 w/o going over wins. That's the next edge that bends around to "your" right. Repeat for that new edge from that vert.
If you get back to the start, list all those verts as an N-gon and mark them. Otherwise just mark them. Quit when you have them all marked (each side of each edge.)
I think that would work. Running time is fast -- O(n). Might be an assignment in 3rd-year algorithms class at a good school. Then you have the problem of seeing what size building will fit in them.
I've attached an image to show what I am looking at.
It shows an enclosed area on the right, which will be used for the placement of buildings. The area on the left is open and should be closed using the closest distance between the two nearby vertices that are dead ends.
The network is generated by starting at some origin and then randomly picking points around at an ever increasing radius. At no point I can predict the creation of polygons, however I can use the generated points to track which points form a polygon. At least manually.
The points are not ordered in any way. Therefore I think I need an alogrithm which reads all vertices and their targets or edges in this case and returns all cycles and dead ends in lists. I need directed graphs later on, so it is crucial for me to find those polygons and then change the vertices in a polygon to establish some form of a circular list.
I know there are resources and codes snippets in C#, but more often I find them to be too difficult to adapt for Unity due to third party compatibility issues. That's why imo this topic got something to do with Unity.
I will look into flat graphs now.
RE: "adapt [C# code] for Unity":
Step one you're just going to be moving a lot of data around, in pure C#, which Unity can do exactly the same as anyone else. If your reference code is running graphics commands while it finds loops, that may be a sign it's just bad code (unless on purpose "draw as you go," which you can delete.) Graph theory is a pretty well-known totally public area.
Once you have the data, in Unity it's just a matter of how to draw a line from A to B.
What if a dead-end sticks into a loop (flip the lower-right one)? Can edges cross (not at verts?) Do long bendy areas count (like on the left)? Does your method sometimes make stuff where no buildings can be placed? I'd be tempted to scrap the path-maker and redo it to meet some rules (mark out spots for 5 buildings, pre-make two connected N/S and E/W paths, draw paths on the rest.)
Otherwise use the grid method. It won't give polygons, but maybe you don't need them. You can have a lot of very small grid cells and it will still run pretty fast (sine it only goes once.)
The algorithm I am using draws for debugging purposes only.
To answer your questions and comments:
I would like to have road networks that don't follow a grid-like structure, because I want cities to look organic and fit the scenario of my game. So grids that resemble typical NA cities are out of the question.
Edges do not cross other edges. Every edge is created by connecting the closest possible two vertices, hence an "intersection" is based on an existing vertex that got two other vertices pointing at it. The overview might show an illusion of an intersection, tho.
As such and by nature of the algorithm vertices may establish polygons as it progresses. Note: Semi-closed polygons only occur at the outer rim of the city. If the polygon is too small, I'll use it for something else, so the size of the polygons is not that important. The chance for a polygon to be too small for buildings is very slim.
Your answer
Follow this Question
Related Questions
Multiple Cars not working 1 Answer
Distribute terrain in zones 3 Answers
Cycle things with one key 1 Answer
Align content in GraphView Node 1 Answer
Find angle between two gameobjects? 1 Answer