Ice tiles where introduced to the Pokémon franchise in the Gold/Silver games. The player must navigate from start to finish by sliding across the ice. Gameplay is shown in the animation below (source).

Most of the ice maps featured in the games are relatively easy to solve. In this article we investigate some basic properties of ice maps, and look at how we can generate maps that are more difficult than those encountered in-game.

Generating maps and solving them

We generate a random binary matrix \(M\) representing tiles. Then we color all tiles along the four edges black, but leave one white tile on both the bottom and top row. The white tile at the bottom is the starting position, and the white tile at the top is the goal position. The player slides along the white ice tiles, and must navigate from the start to the goal.

A map \(M\) can be represented by a directed graph \(G\), where:

• A node represents a tile where the player stops moving and must make a new choice.
• A directed edge represents an option for movement between tiles.

The figure above shows a map \(M\), its directed graph \(G\), and the directed graph embedded in the map. Here we do not show an outgoing edge from the goal node. Notice that many maps \(M\) can have the same graph \(G\), and that not every graph \(G\) can be represented by a matrix \(M\). We will therefore generate matrices and transform them to graphs, instead of working in graph-space directly.

Weak and strong solvability

After investigating some randomly generated maps, we can establish some notions of solvability:

• If there is no way to reach the goal, the map is said to be unsolvable.
• If the goal can be reached, but it’s possible to get stuck in a loop if the wrong decision is made at some point, we call the map weakly solvable.
• If the goal can be reached, and it’s not possible to get stuck in a loop in the process, we call the map strongly solvable.

Notice that we define weakly and strongly solvable as disjoint concepts. A strongly solvable map is not weakly solvable, and vice versa. These properties are illustrated by example in the figure below.

Reversibility

In the previous section, all three maps shown in the figure have the property that at some point there is no going back to the start tile. A player would, eventually, be unable to go back to his starting position at the bottom of the map.

We say that a map is reversible if a solution concept holds in reverse, i.e., both from start to goal, and from goal to start. Conditioned on weak or strong solvability, we can find examples of both reversible and non-reversible maps. All four cases are shown in the figure below, and the reader is encouraged to verify the properties.

Strongly connected components

To investigate the solution concepts further, we partition the graph \(G\) into its strongly connected components (SCC). In a directed graph, two nodes belong in the same strongly connected component if we can reach one from the other (and vice versa) by traveling along directed edges.

In some directed graphs every node is reachable from every other node, in which case there is only one strongly connected component (the entire graph). An example of such a graph is \(a \leftrightarrow b \leftrightarrow c\). The only strongly connected component is \(\{a, b, c\}\).

In other graphs, such as \(a \rightarrow b \leftrightarrow c\), there is no way to go back to \(a\) once we reach \(b\). The strongly connected components of this graph are \(\{a\}\) and \(\{b, c\}\). If we collapse the strongly connected components into meta-nodes, we form the condensation of a graph. The condensation of \(a \rightarrow b \leftrightarrow c\) is \(\{a\} \rightarrow \{b, c\}\), and the condensation of a graph is always a directed acyclic graph (DAG). See Wikipedia for more information.

The figure below shows a reversible, weakly solvable map. The nodes are colored by their strongly connected components, and the condensation of the graph \(G\) is also depicted.

A map is weakly solvable if and only if: (a) there is a path from the start node to the goal node, and (b) there is a node in the condensation of \(G\) without outgoing edges, but the goal node is not in this strongly connected component. A node without outgoing edges is called a sink.

The map above is reversible and weakly solvable. There is clearly a path from the start node to the goal node, and the blue node in the condensation of \(G\) is a sink. However, the goal node is not in the sink meta-node – so the map is weakly solvable.

Below is a map that is weakly solvable, but not reversible. The condensation of \(G\) is more interesting than above, but notice that the blue node in the condensation of \(G\) is without outgoing edges, and the goal node is not in this strongly connected component (it’s in the orange SCC). Therefore, the map is weakly solvable.

The map below is strongly solvable. A map is strongly solvable if and only if: (a) there is a path from the start node to the goal node, and (b) there is a single sink node in the condensation of \(G\), and the goal node is in this strongly connected component. (By construction of \(G\) the start node must be in the a source of the condensation of \(G\), and there is only one source in the condensation of \(G\).)

Below is a larger example. The condensation of \(G\) is a chain, but the goal node is not in the last SCC in the chain – so the map is not strongly solvable (it’s weakly solvable and reversible).

In the Pokémon games, all maps are strongly solvable and reversible. A map is strongly solvable and reversible if and only if the condensation of \(G\) is a single node, in other words: \(G\) has a single strongly connected component.

Sidenode: Strongly and weakly solvable in reverse directions? Earlier we said that a map is reversible “if a solution concept holds in reverse, i.e., both from start to goal, and from goal to start”. Can a map be weakly solvable in one direction, yet strongly solvable in another? The answer is no. Let’s denote the start node by \(s\) and goal node by \(t\). A map is solvable (either weakly or strongly) if there exists a path from \(s\) to \(t\).

Assume that a map is weakly solvable in the forward direction and solvable in the reverse direction, i.e., there exists a path back from \(t\) to \(s\). Since there is a path from \(s\) to \(t\) and a path from \(t\) to \(s\), both \(s\) and \(t\) must be in the same SCC. Weak solvability in the forward direction requires a sink SCC which neither \(s\) nor \(t\) are part of. Strong solvability in the reverse direction requires either a sink SCC which \(s\) must be a part of. We cannot have both.

Assume that a map is strongly solvable in the forward direction and solvable in the reverse direction. Then \(s\) and \(t\) must be in the same SCC. Strong solvability requires that there be at most one sink, and that \(t\) must be in this sink. Therefore there is only one SCC, which both \(s\) and \(t\) are in, and the map must be strongly reversible in the reverse direction.

To summarize: a map that is weakly (strongly) solvable in the forward direction is either unsolvable or weakly (strongly) solvable in the reverse. If there is a path from \(t\) to \(s\) (the reverse direction), then it is weakly (strongly) solvable in the reverse direction.

Difficulty

Assume now that maps are strongly solvable and reversible, just like in Pokémon. To find a solution, we must find a path from the start node to the goal node. This can be accomplished by Dijkstra’s shortest path algorithm.

Depending how we weight the edges, we find the shortest path with respect to distance traveled across the ice, or the shortest path with respect to the number of stops required. As shown in the figure below, the solutions can differ.

To make a map hard we can increase the size. Larger maps will generally be harder to solve than smaller ones. But given a reasonably small size, how can we quantify the difficulty?

To find difficult maps, we can look for maps where the shortest possible solution path is as long as possible. The figure below shows two maps, one with a short solution path and one where the shortest solution path is long.

Another slightly more involved approach is to look at the number of choices a player must make. Some paths can be long, but very guided – at each step there are few options. If there are many possible branches (opportunities to get lost in the map) along the shortest solution path, then the map ought to be hard in some sense.

We can combine these two measure of difficulty, i.e.:

• The shortest solution path should be long
• There should be many number of branching options along the solution path

Then we can look for maps where both of these measures are high, using for instance the Pareto set. Some hard maps by this combined measure of difficulty is shown in the figure below. These are all strongly solvable and reversible, but difficulty is measured in the forward direction.

I have not found any definite measure of difficulty. The approaches outlined above seem to work reasonably well, but I am sure one could think of more clever approaches.

Generating maps

The maps were generated by independently assigning tiles to black. When maps are of the sizes shown in this article, setting the probability of black to around \(20 \%\) often results in maps that are strongly solvable and reversible. The strategy is naive: random maps and simply generated and evaluated. My naive Python code spends 10 seconds generating and evaluating ten thousand maps of size \(12 \times 12\), out of which \(62\) were strongly solvable and reversible. Not too bad.

Summary

Pokémon-style ice maps can be represented as directed graphs. We investigated three properties of maps, which we named weak solvability, strong solvability and reversibility. A constructive way to classify maps is obtained by investigating the condensation of the underlying graph.

We can find difficult maps by investigating the length of the solution path and the number of possible branchings along the solution path, but this measure of difficulty is a bit naive. It’s surprisingly easy to generate strongly solvable and reversible maps, since a sizable portion of randomly generated maps have these properties.

Appendix: Some larger examples

Here is a large, strongly solvable and reversible map.

Here is a large, weakly solvable and non-reversible map. The orange SCC is a “trap” that a player can never leave.