# The game like Untangle / Planarity

After last 2 posts about geometry, I decided to explain, how to make a game like Untangle (solving planar graph by moving vertices).

## Idea of the game

Let's specify, what exactly we want to do and how we are going to do it.

### Where we get the graphs?

The game works with planar graphs (which can be drawn without line crossings). If we just make a random graph, it can be non-planar (for example, $K_{3,3}$ is not planar).

We can make the graphs manually, but first we must come up with some good ideas for graphs. Another option is to generate them with a computer.

We know, that triangulated graph is planar. In the last article about Voroi diagram we made an algorithm, which makes a Delaunay triagnulation of some points. So we can use it.

We should check edge crossings and draw a graph accordlingly to them. This checking can be used from the last article about Geometry.

So, we should do these things:

• generate random 2D points
• compute the triangulation (list of edges)
• throw out some edges to make the graph simpler
• shuffle vertices on random positions (I put them into a circle)
• let the user to move vertices, redraw the graph

## Extra features

We can add some nice graphics into our game, or some extra features. The game would be much more interesting and may be also joyful. I used techniques described above and created the game FlyTangle. If you like it and you have Google Chrome browser, you can install it as a Chrome app.

## Old comments (closed because of spam)

1. Ahmed said:

ah this is nice did you use Java or Flash which algorithm did you use
thanks
Ahmed

June 22nd, 2011
2. Ivan Kuckir said:

Hi, I used Flash, I used Fortune’s algorithm to compute a Voronoi diagram.

You can use the Voronoi diagram, or make a dual graph of it (Delaunay triangulation), which is also planar.

June 22nd, 2011
3. shaurya said:

simple yet brilliant! loved the game and it’s concept!

July 31st, 2011
4. kee said:

can you share the source file?

August 1st, 2011
5. Ivan Kuckir said:

thank you

My intent was to show some nice work and motivate users to do it themselves. All necessary information and codes are at this blog. I can send you all the source files in return for a small donation (panel at right).

August 1st, 2011
6. Graph type games | hamiltongreg said: