Review: Galaxy

Here we go again!

Now, I’ve reviewed a Magma Mobile game before. It wasn’t exactly positive. Galaxy, like many of their games follows the same formula with the medals. As I’ve written before I have a lot of issues with that. Galaxy, while poorly executed has an excellent concept and some very cool maths behind it. While it’s not worth playing for long, it is free (with ads) and if you’re so inclined might worth a quick look after reading the article.

Now I want to show you what is interesting about this game without you actually having to play it. So in this article I’m going to mostly go over one aspect of this game: the maths. Wait! Come back. It’s not the maths you’re used to at school. There’s no arithmetic, it’s easy and interesting. Honestly, really easy. Can you count? Can you tell odd from even? Great, you’ve got everything you need. If you can’t do those things you should probably sort that out and come back.

Eulerian graphs

Think back - at school did you ever try to do that puzzle where you have to draw a box with an x in the middle without your pencil leaving the page and without going over the same line twice? Did you ever wonder why it was impossible? I’ll tell you why later, but this is an example of a mathematics problem called a “Eulerian graph” problem.

Another example of an impossible “Eulerian graph” problem is the seven bridges problem. In this problem (pictured below) you can start wherever you like and you have to traverse each bridge exactly once. Go ahead give it a go. You can’t do it.

Image credit: Bogdan Giuşcă, taken from Wikipedia.
Who said image captions had to be fun?

So why is it impossible? Lets look at a single island and pretend it has an even number of bridges connected to it. Every time you enter that island, you must then leave by another bridge. So two bridges are done and there are still an even number of bridges left. This keeps going until the remaining bridges reaches zero and you have just left the island. So you cannot end here.

Now lets look at an island with an odd number of bridges. This time every time you enter and leave you are left with an odd number. This continues until there is only a single bridge remaining. Once you enter this for the last time, you cannot leave. So you must end here.

Now what about the island you start on? The island you start on changes whether that island has an odd or an even number of bridges. This is because you never had to enter that island. For example: if you started on an odd island, as soon as you move out there are an even number of bridges remaining.

So lets look at the possibilities for solvable puzzles. We know we need to end on an island with an odd number of bridges. So we can either start on an island with an odd number of bridges and end on a different island with an odd number of bridges (called a “Eulerian path”). Or we can start and end on the same island with an even number of bridges (called a “Eulerian cycle”). So for the puzzle to be solvable, there needs to be either zero or two islands with an odd number of bridges. If you’re wondering, you can’t have just one island with an odd number of bridges. Go ahead - try it!

So applying what we’ve just learnt, the puzzles are impossible because both the puzzles mentioned contain more than two sections with an odd number of connections. Infact every section contains an odd number of connections, thus they are impossible.

1... 2... 3 "Nope that's impossible."
Then walk away. You genius!

Now that’s neat and all, but that’s not the really cool part. It turns out the converse is also true: if there are zero or two sections with an odd number of connections, then the puzzle is definitely solvable. Not only is the puzzle definitely solvable, it is also easy to find the solution. I’m going to show you through what’s known as “Hierholzer's algorithm”.

First you need to choose your start and end points. Now draw a path between them, it can be any path that covers any number of connections, it doesn’t matter. Because everything you draw through has an even number of connections (and thus you must leave it) it is impossible to get stuck before you reach your goal. Once the path is drawn, the remaining sections will all have an even number of connections.

From here, you can look back at any section that has some remaining connections and repeat, treating it as a start and end point. From here you simply pretend that when you drew that initial path, you took a detour and then returned. Repeat this until complete. This is a little more difficult to understand, and might require you to sit back and think about it for a while. Hopefully I’ve explained it well enough.

Now I’ve shown you Hierholzer's algorithm simply to demonstrate the converse of the original hypothesis. In all truth, so long as you keep an eye on everything, trying to apply Hierholzer's algorithm to a possible puzzle is a massive overkill. As long as you start from the right point, it’s easy enough to just wing it. There are usually a massive number of solutions.

Galaxy

So what does this have to do with Galaxy and why do I like the concept? Well Galaxy requires you to find solutions to these Eulerian graphs, with some additional constraints. This is all set to drawing constellations in the night sky, which I think is quite beautiful.

Pop quiz: why haven't I won?
Can you see it?

I really like that it’s based off some simple maths. It’s maths that’s never taught in school and yet anyone can understand. It’s maths that you might even have been able to work out for yourself. Now ideally a puzzle game will show you something. Through it’s level design it will lead you to working out something interesting. Now think about having that as the pay off. Working out everything that you just read, guided by a puzzle game. It could be fantastic. They didn’t do that.

In Galaxy you can traverse three different types of line: required (solid line), optional (dotted line) and one-way (arrows). They’re all fairly self explanatory, I don’t know about you, but done right it actually sounds like it could be really interesting. Look back on the maths. Which optional paths should you use in a level? If you counted more than two stars with an odd number of connections, this is something you’d need to think about. How are one-way paths going to influence that?

Well, it could have been interesting but aside from the great idea, again next to no effort went into this game. There are currently 3200 computer generated levels, which doesn’t bode well for a slope of difficulty. Also being computer generated it doesn’t show off what is interesting about the game. But wait! It gets worse. Due to the way they have had the computer generate the levels, there’s little to no logic involved in solving the puzzles at all.

Prizes for guessing how the
top three stars are connected.

What they seem to have done is to draw a random path between randomly placed stars*. From here they have randomly made each connection on the path either required, optional or one-way (in the direction they went). It’s a simple algorithm, but as I’m sure you’ll notice means that the first half of the maths section in this article is enough to solve even the most complex levels of this game. Here’s how:

Step 1 - Pretend all optional connections are required.
Step 2 -  If available, start from a star with an odd number of connections.
Step 3 - Draw practically anything.

All they needed to do was to randomly add some extra optional connections at the end and the puzzle would have actually been challenging. Not that it isn't challenging. Most people don't know about the maths covered and will just flail about randomly until they start on the right star. Obviously if it takes a lot of time that means it's challenging. Right?

Of course the game doesn't guide them towards learning anything, if anything the inclusion of optional paths obfuscates it. So adding extra optional paths is a bad idea if you didn't want to put the effort it to making an interesting game. Really the whole thing is just a massive missed opportunity.

Now I’m going to have to be fair, and say they don’t add extra optional connections in the first hundred or so levels, and they might add them later. Unfortunately I’m not planning on playing any further. If you have (for whatever reason, my guess is taken hostage by a Magma Mobile employee) let me know!

It also has some problems with the controls and other stuff I mentioned in the opening paragraph. Like Connect ‘em, again I feel like I’ve put more thought into this review than they did with the whole game. This is despite most of the thinking for this being done by Euler, not me. In summary, if you want to test out some of the maths you’ve just learnt, it’s worth a quick look, otherwise you’re wasting your time.

*It seemed this way, however then I played time trial which automatically generates the levels. The more time you have left the harder (larger) the levels it generates. When you get above about 2 minutes, it starts taking upwards of 1 minute to generate the level (this comes out of your time). It should take well under a second. This leads me to believe they are doing something far dumber. This is my best guess at how they do it:
1. Generate a random set of connections.
2. Randomly set some to one-way.
3. Exhaustively search to check if it's possible. If not go back to 1.
4. Randomly set some connections to optional.

They must have an excellent marketing department.