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)

6 Comments

  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:

    [...] Graph type games Share this:TwitterFacebookGoogleLike this:Like Loading… [...]

    March 28th, 2014