The first major algorithm problem is how to generate loops. Here is what I came up with.
The algorithm in summary is as follows.
Choose a starting point, giving preference to hexes with fewer free edges. Initially this will pick the rim corners.
Make an outward leg, again selecting hexes with fewer free edges. This will tend to hug the rim.
At each step use A* search to make sure there is a way back home.
After reaching the desired path length, use the A* search to head for home and close the loop.
The final result looks like this.
At this point I found a major bug. Occasionally it looks like this.
Why? It turns out that this implementation of the A* algorithm has no protection against paths that cross themselves.
Think about the Fedex algorithm: assuming trucks that drive on the right, Fedex found that it is cheaper to make three right turns rather than one left. If you set up a movement cost based on that rule it will generate paths that cross and break this implementation of the algorithm. Back to the drawing board!
I want to explore two things about this fascinating game: how it generates loops and how the game might be made even better. To do that, first I need a basic clone of the game.
The platform I know best is Unity, with code in C#. Earlier games such as Polygamo and Puzzlang provide a solid foundation, but they are based on a rectangular grid. Hexagonal grids are obviously quite different. You can fake a hex grid by pretending it’s rectangular and offsetting every alternate row, but the code gets messy fast. I know, I tried!
Unity provides an excellent platform for writing simple puzzle games. It’s really easy to attach bits of code to game objects and the code is simple and straightforward. Even better, the compiler code has been updated to the latest version so all the cute features of C# 4.x now work.
Hex Grid Library
The definitive reference for using hex grids in games is this article on Red Blob Games. It provides code in C#, which can be used as a starting point. First I tried each of the hex grid libraries referenced in the article, but I found that variously that they were:
very basic, lacking key features and particularly any kind of search algorithm
tightly coupled to Unity in ways that ruled out my kind of model-view
broken, just did not work at all.
So I decided it was time to just take the Red Blob code and get it working. I added a number of utility routines and two major pieces of functionality.
Path searching based on red-blob again. This includes A* search, which requires a Priority Queue: there is a nice one open-sourced by Microsoft.
Generic grid generation: hexagon, rectangle, parallelogram, triangle, etc. instead of the hard-coded loops provided by Red Blob.
It seems simple enough, but writing any kind of game requires attention to lots of detail. I decided to go with a 2D game using UI components like panels and sprites. So I need:
Assets: sprites for the grid, loops and buttons
Palette: to make nice colours
Font: the game is minimalist, but it still has some text
Animations: stuff needs to move!
Sound and Music can come later.
After wrestling too long with the Unity Animation system, I gave up and decided to go with a Tween library. I chose LeanTween, but there are others. And this is what it looks like, running in the Unity editor.
Creating the loops, now that’s the subject of another post!
LOOP is an elegant puzzle game based on paths through a hex grid. You start with a scrambled grid, swap pairs of hexes and when you finish all the loops link up in perfect harmony (see image).
No tutorial, but 100 individual puzzles introduce the key mechanic and the two special devices. Clicking on a hex highlights its border; clicking on another then gracefully swaps them over. One device is a simple arc inside a circle, which is fixed in location but changes colour when clicked. The other has three arcs inside a circle of arrows and is also fixed in location but rotates when clicked.
The maximum size of grid is a hexagon with four hexes to a side, sometimes a bit moth-eaten (see picture). The earlier puzzles often have a smaller grid, and some have holes in them. There are puzzles wth paths of just one colour, while others may use six or more. Sometimes the paths are tightly packed, using all sides of the hexes, sometimes they are quite sparse.
Finally there is a puzzle generator. The puzzles are less varied than the individual levels, but the supply appears unlimited. It’s a lovely puzzle with hours of enjoyment, and I highly recommend it to any puzzle aficionado. You can get it on Steam or direct from http://loopthegame.com/.
But of course the question I want to address here is: how does that generator work? And could it be even better? We might have to build a clone to do that.
Update release 18d17 of Puzzlang is now available on Github. This release fixes a few bugs and implements support for cursor games and text objects. The release is here. See the release notes for more information. Screenshot here:
This release of Puzzlang implements a pattern language compatible with PuzzleScript. The release includes a Puzzlang games engine, a Unity player and a selection of games.
The Puzzlang engine compiles and executes games scripts. It is nearly feature complete with PuzzleScript, and has a few extensions. The Unity player is quite basic, compared to what Unity can achieve, but it can play games and it too has a few enhancements. The games are selected from the PuzzleScript demos, and show the range of what now works.
PuzzleScript is a fascinating language for writing puzzle games, particular those of the block-pushing variety. It has a strong following, with hundreds of games written in it to various levels of quality. It is particular well-suited to prototyping a game (of a suitable genre) prior to turning it into a commercial quality distributable game. Full credit to Stephen Lavelle, whose many other creations may be found at increpare.
The aim of the Puzzlang project is to implement the PuzzleScript language using modern compiler tools, to put it on a firm footing from which it can be developed further. One reason is to target different platforms, such as Unity or mobile devices. Another is to improve the visual appearance, with higher resolution images and text. And there is the possibility of adding new features such as mouse support and new genres of puzzles based on the same pattern matching ideas.
Polygamo is a language compiler and general player for abstract games and puzzles. You can read more about it here.
The aim of Polygamo is to allow a human to play any general games and puzzles as long as there is a Game Description Language to describe them and a device to play them on.
The initial release is a Unity player with an implementation of the ZRF language. The project includes a games library, responsible for parsing the game description and providing the logic to play the game, an AI based on MCTS, a player for Unity, and a few sample games. This is just the first release, to get some feedback and gauge interest. More will follow.
This is open source software and it is free, in both senses. You are free to download it, free to use it or modify it and free to create games with it, at no charge. If you pass Polygamo or your games on to others you have to do so in exactly the same way: open source, free to use, free to modify and at no charge. For more details see Licence.
You can download Polygamo from Github here. You can submit issues there, or contact me through this web site.