A new quiz puzzle game: Movie Triangles

Posted by jimblackler on Jan 13, 2011

i1

Movie Triangles is a puzzle game that combines a movie knowledge quiz with a tile puzzle. The objective is to fill a 16 or 25 piece grid with triangles containing movie and actor names. In the winning grid, all triangles with movies will border their starring actors.

The game includes a number of puzzles of varying difficulty and featuring movies from different eras.

itunesartwork

To play the game click here.

And if you want to know how the game was developed, read on.

Development

I’ve long thought that the network of relationships between Wikipedia articles is a fascinating area and ripe for adaptation into a game. I originally contemplated a game based on a hexagon grid where the player would position hexagons labeled with Wikipedia articles. The objective would be to place the hexagons next to those labeled with names of related articles.

However this idea lacked clear rules. It’s not clear to the player *why* the articles would be linked, so it would be unreasonable for the game to seek a right-or-wrong answer. So I looked for Wikipedia topics with clear formal links. I thought about players in sports teams, neighboring countries, musicians in bands, and other ideas.

However the stand-out candidate for this treatment is movies and the actors who star in them. There is a huge amount of data to be mined, both on movies and actors. The data is bilateral, actors link to movies in good quantity and vice versa. The topic is interesting for lots of people and relatively international. It’s a great topic for a game.

As I explored the idea and worked on prototype game grids it became clear that a hexagon structure with six connections per piece would prove unworkable. It would most likely be impossible to create working puzzles, because the demands of having to find six links per movie or actor. Triangles, with just three links (fewer for those at the edge) seemed much more feasible. So the design for Movie Triangles was born.

Scraper, Solver and Game.

The software for the game is divided into three parts, each of which passes data to the next component along.

Crawler/Scraper

The crawler/scraper is based on my Quizipedia scraper. Written in Java it downloads articles from Wikipedia onto my local PC. An SGML parser is used to load the article DOMs, and XPATH queries are used to pull out data, which is then loaded into a local MySQL database. Using a separate database helps solve problems caused by the large quantity of data (such as serialization) and allows the process to easily be interrupted and restarted.

The starting point for the crawl is an article on Wikipedia that is a central list of lists of movies elsewhere on Wikipedia. A ‘list of lists’. Crawling just a depth of two from that hub article appears to cast a net that includes virtually every movie article on the site.

Once the pages are loaded and processed they are scanned to see if they are movie articles that can be analyzed for inclusion into the database. Thanks to the diligent work of Wikipedia editors, movie articles consistently have a sidebar that contains structured data about the topic. For my purposes there are two pieces of data that are particularly useful. The first is the ‘Starring’ field that contains links to the starring actors of the movie. Since these contain Wikipedia URLs this provides disambiguation, solving a problem where actors who shared the same name could be confused. Similarly, inbound links to the movies are analysed. Also I use the anchor text from links to provide a cleaner, shorter name than is often provided by the article heading.

The other very useful field is ‘Release date(s)’ which can be processed with a regular expression to discover a release year number for the movie. This is useful data for the game to help players identify a movie more effectively than the movie name alone would.

It is also useful for verifying and article is actually about a movie. I have also observed that if an article has both ‘Starring’ and ‘Release date(s)’ fields in its information sidebar it is almost certainly an article about a movie rather than something else. This is a very effective filter to ensure a 99% clean data source.

It takes only about an hour of running the crawler before a database of about 12,000 movies and actors has been built up. Then the baton is passed to the game builder which begins the process of creating the game puzzle grids.

Builder

The builder is another Java application which loads the movie and actor data from the local SQL database into memory. It then attempts to construct completed, valid board positions, selecting from all the actor / movie combinations in the database. Firstly a single tile is ‘seeded’ with a particular movie. Then the algorithm attempts to find the valid board positions where the least famous movie or actor is as famous as possible.

The reasoning behind the fame requirement is to stop puzzles from being filled with highly obscure movies or actors. If the algorithm used any actor / movie combinations that made the grid fit, it is unlikely that the average player would be able to guess even 20% correctly. It is the nature of Wikipedia that it is highly extensive, but this extensiveness works against the aims of a trivia game.

What is needed is some way to score the fame of an article subject. When I developed Quizipedia I experimented with various signals such as the number of inbound links to the article. Eventually I discovered the surprising fact that the length of the article is closely correlated to how likely the average person is to have heard of the article topic. It is an artifact of the fact that the motivating factor for Wikipedia editors to work on an article is also correlated to the fame of the topic. Longer articles mean more famous topics. An relatively obscure actor is likely to have a short article.

The actual building algorithm is pretty involved so I won’t detail it in full. The short version is there is a recursive method that takes a position which, for each slot in the grid, has a set of any possible actor/movie that will fit into each slot (this is calculated with iterations of set operations beginning with the currently fixed slots). The slot with the fewest possibilities is selected, the tile is fixed with each possibility is in turn and the method re-invoked recursively until the best solution is found.

The builder also creates custom tile images for the game in custom PNG format, with the movie or actor text positioned to fit the triangle using the largest font possible.

Game

Having come up with the triangle grid idea, I needed to make the actual puzzle work as a computer game. I went through several iterations, testing on friends before coming up with the design you see today. One main question was how to tell the player if their guesses are correct or not. I wanted the player to be able to move the tiles around freely before submitting their guess. I implemented a ‘check grid’ button that would tell the player if they had it right. Having this only appear when the whole grid is filled helps keep the look simple and therefore inviting. Returning only the invalid tiles allows people to correct their grids and keeps the difficulty manageable. I record and report the number of times the check grid button is used by the player to reward players who found the solution on the first event. Combined with fixing the correct tiles and not allowing players to place tiles in locations already revealed as invalid, it should be possible to solve the grids by trial and error. This lowers frustration levels as players can usually finish grids with a number of attempts.

One game element that is controversial with my testers is the tile borders. Here I use a visual clue to show which positions tiles can be found in. This reduces dramatically (particularly with 16 piece puzzles) the number of slots a tile could potentially occupy. People sometimes say this feels like cheating. Certainly it does reduce the simplicity of the puzzle which is regrettable. However in tests I have found puzzles without this aid to be considerably more difficult, to the point of bafflement and frustration. The problem is you may know which actor starred in which movie, but there would still be a large number of tiles both could potentially occupy; maybe anywhere on the grid. If you have a 80% knowledge of the films and actors it can take several minutes of grinding through the possible orientations of the tiles to find the right one. I believe if I had published the puzzle in this way it would only appeal to an elite of puzzle and trivia solvers, who would have the time and inclination to spend the time to work through all the possibilities. Adding the borders means most of the time spent on the game is in thinking about the trivia content rather than wrestling with complex geometric logic. It also allows some interesting logical clues that let you fill in the gaps of your knowledge.

I wanted the game to present an inviting, clean layout to the player. The game always completes the corner grid pieces to invite the player to get started straight away; each corner piece has just one neighbour to find.

I am pretty happy with Movie Triangles. I hope you enjoy it too.