Introduction

Recent geometric investigation of the Ocean Seal Diagram reminds me of another “Wisdom Maze” that I just haven’t had sufficient time to analyze lately. Last year Square-Enix released a 2DHD remake of Star Ocean: The Second Story, one of my favorite PlayStation games. It’s a role playing game about relationships and personal affinities, skills development, and exploration of the far reaches of the universe. The new “R” version follows an earlier remake “Second Evolution”. Again in its third outing, the game sold tens of thousands of copies at market, at least. Although nostalgia is certainly a motive, perhaps there’s also something new for young students to learn, now that some of the original players have grown up to become mathematicians and finite-state programmers.
At some point toward the end of Star Ocean 2, you can win the help of a Psynard, an alien animal, which your party of characters can ride around the world map, while trying to save the world from the forces of evil. Once you have obtained the Psynard, and you’re flying around energy Nede, there’s a set of temples you need to visit. Most of them have puzzles that need to be solved. One of them is quite complicated, and worth detailed investigation, the Field of Wisdom maze.
The first time I solved “Field of Wisdom” on a Playstation 1, I didn’t know about computational complexity of video games, and I didn’t know about multi-state mazes. With my teenage “beginner’s mind” (初心, to borrow a Suzuki phrase), it’s likely that I just wandered around, trying to remember what directions I had already tried, and what directions could possibly lead to a new game state. This random walk strategy can be effective given enough time, but using graph theoretic methods, we can now do much better at optimizing solutions. Here we will show how to use computer programming to find the minimal solution. We also find a completist solution including all treasure acquisitions, which improves upon the gamefaqs recommendation by about 15-20%.

Data import

For a representation of the Field of Wisdom, we claim academic fair-use, and start with the PNG image found on gamefaqs:
In[]:=
wisdomMaze=
;
Aside from the odd icons for the doors and treasure, this is really just an ArrayPlot. Numerical data can be extracted by ImagePartition:
In[]:=
Grid[Map[Show[#,ImageSize->5]&,​​squareData=ImagePartition[​​ImageTake[ImageCrop[wisdomMaze],{3,-3},{4,-2}],​​{20,20}],{2}],Spacings->{0.1,-.4}]
Out[]=
As with the previous SNES extraction problem, we will need a few steps to get clean data, but fortunately for us, this top-down data is much easier to work with. First, we roughly binarize the map:
In[]:=
ArrayPlot[​​roughSpace=Map[If[Mean[Mean[#][[1;;3]]]<.2,1,0]&,​​squareData,{2}],PlotRangePadding->None]
Out[]=
Next we fix places where chest and door icons have caused erroneous values:
In[]:=
ArrayPlot[space=Plus[roughSpace,​​Normal[SparseArray[Thread[{​​(*fixchests*)​​{4,3},{4,5},{3,4},​​{14,4},{14,6},{15,5},​​{19,15},{18,14},​​{2,21},{3,22},​​{5,40},​​{16,35},{17,34},​​{18,43},{19,42},​​(*fixdoors*)​​{17,20},​​{17,29},​​{10,25},{10,24},​​{15,25},{15,24}​​}->1],Dimensions@roughSpace]]​​],PlotRangePadding->None]
Out[]=
Finally, we programmatically add in the teleporters in orange and red, and manually color the doors, switches, and treasures in purple, blue and green, respectively:
ArrayPlot[​​decorated=Plus[​​space,​​Map[Which[​​And[Mean[#][[1]]>.7,​​Mean[#][[2]]<.7],2,​​And[Mean[#][[2]]>.7,​​Mean[#][[3]]<.7],3,​​True,0]&,​​squareData,{2}],​​SparseArray[Join[​​Thread[{​​{4,4},{3,21},{14,5},{19,14},​​{19,43},{17,35},{5,39}​​}->4],​​Thread[{​​{17,37},{15,37}​​}->-3],​​Thread[{​​{12,21},{15,22},{16,25},​​{14,27},{11,28},{9,24}​​}->5],​​Thread[{​​{18,20},{18,29},{11,25}​​}->6]],​​Dimensions@space]],​​ColorRules->$MapColors,​​PlotRangePadding->None]
Out[]=
This involves a bit of tedious data entry, but we end up with a very nice data object. We can go on to explore its states adjacency graph, and then ask a few specific analysis questions about optimal traversals.

Maze graphs

Rather than working with an integer matrix, we extract coordinate pairs into an association keyed by the different integer values appearing in the matrix:
In[]:=
locations=Association[#->Map[Times[Reverse[#],{1,-1}]&,​​Position[decorated,#]]&/@Range[0,6]];
From this transformed data, we can create a NearestNeigborGraph which is essentially identical to the ArrayPlot from the previous section:
In[]:=
nng=NearestNeighborGraph[​​Catenate[Values[KeyDrop[locations,1]]],​​VertexStyle->Catenate[KeyValueMap[​​Thread[#2->Directive[ReplaceAll[#1,$MapColors],​​EdgeForm[Gray]]]&,KeyDrop[locations,1]]],​​VertexSize->1/2,EdgeStyle->Gray]
Out[]=
Extra edges show in part how the Red and Yellow teleporters work to connect all disconnected components of the graph (other than the central platform):
However, this is not an exactly correct picture of the maze, because the maze explorer must alternate between yellow and red teleporters when jumping around the map. To be clear, this maze only differs from the MoMath maze in NYC in it’s particular shape and in having a two-color cycle, rather than three. Other than that, it is also what’s called a “multi-state” maze.
The goal of the maze is to visit all the blue locations, activate the crystal switches, then complete the level by moving forward to the central platform. The maze is entered and exited through purple locations, which are connected by a second room with three doors. Extra benefits can be gained by visiting optional green locations, including 2x Faerie Elixir and 3x Fruit Syrup for restoring health and magic points.
To get a more accurate representation of the maze, we split it into two levels, with either red or yellow switches active:
Additionally, we’ve deleted active teleporters, leaving only the bi-directional edges. If we condense disconnected components of the above graphs to single vertices, then each teleporter is a directed edge, and we can obtained a unified, coarse-grained states adjacency graph:
From this graph, we trim orphaned states, and the extra room as both a “Start” and “End” vertex:
The resulting graph has 58 vertices and 95 edges:
Our next task is to write an algorithm for traversing this graph while visiting some but not all of the green and blue vertices, starting and ending at the purple vertices.

Multiway analysis

Before diving into the solution, let’s first discuss the algorithmic theory. The graph connectivity problem and the shortest path problem are polynomial time algorithms, whereas the Hamiltonian path problem is non-polynomial. In the game, we are asked to solve a maze while visiting a set of crystals placed at certain energetic locations within the maze. Assuming the problem is solveable, it’s complexity must fall somewhere between finding a path and finding a Hamiltonian path. Only a few special vertices need to be visited, and in this case we will allow the path to backtrack to previously visited vertices if necessary.
In the combinatorial games post, we explored Hamiltonian paths in terms of MultiwayDeletionsGraph, which does a good job of illustrating how choices made by a pathfinding algorithm can lead unpredictably to dead ends. Those dead ends are solely a function of disallowing backtracking. When backtracking is allowed, finding any path that visits every vertex requires only polynomial time. The shortest path algorithm runs in polynomial time, and it needs to be run, at most, only once for every vertex other than the start. This is why the game is not too difficult for teenagers, and also part of the reason why it has sold millions of copies world wide.
As far as I know, there is no System` algorithm in Mathematica, which automatically traverses a graph from start to finish, while visiting a special set of vertices, much less an algorithm that would do so in a verifiable-minimum number of steps. A branch-and-bound algorithm could do pretty well at finding minimal solutions in non-polynomial time. I would guess that such an algorithm’s space complexity would be polynomial, but I haven’t proven that yet. The question is relevant to Erik Demaine’s video game theory, especially if we impose an energy-draining mechanism, in which only finitely many teleportations are allowed per attempted traversal.
Algorithm design and complexity issues may become important later. For now, let’s get back to finding a minimal solution for activating the switches only. Each switch occurs once on the red-active or yellow-active levels, which are not physically separate, thus their graph vertices need to be grouped together:
A very simple, brute force iterator can enumerate all possibilities without needing branch-and-bound logic. At every step, the end of an accumulated path is pointed along a shortest path to every remaining unvisited vertex,
and the shortest paths are joined to the end of the input path. The FixedPointGraph of the one-to-many iterator yields a directed acyclic graph rather than a tree:
The reason for confluence is that sometimes a fortuitous choice can be made where visiting one distant key vertex also accidentally visits a nearer key vertex. This search graph must contain the shortest path because the shortest path is just an ordering of key vertices joined by the shortest paths between them. Meanwhile, the iterator is guaranteed to search through all the possible orderings of key vertices.
No surprise, we find log-linear branching ratios, and about 500 end-conditions:
The shortest path involves about 20 teleportations:
It makes one turn around the circular form, and has to backtrack down one dead end:
Upon closer investigation, we can see that it starts at one entrance and ends at the other:
If anyone can find a better solution than this, I must have made a mistake. Probably the analysis is correct, and this is the minimal solution. Feel free to leave questions or comments about that below.
Now we can do exactly the same thing by also requiring visitation of all the green “treasure” vertices:
Unfortunately, the branching ratios become large enough to prohibit the calculation of an entire search graph. A smart branch-and-bound algorithm could possibly solve the completionist problem more definitely, but for now we don’t have such refined capabilities. Instead, we limit ourselves to branching at most three times per vertex:
The minimum-found solution has fewer then 50 steps:
While this is not proven to be the minimal-possible, it may be. Indeed, it already involves 15-20% fewer teleportations than the solution given by gamefaqs. In this outing there are many backtracks and turn-arounds, with one vertex even visited three times:
As above, the solution can be depicted as ArrayPlot frames, and composed into a movie:
If anyone can find a better solution, or prove that no better solution exists, please leave a comment explaining your results and methods. Thanks, have fun, and make sure to share the elixirs with your friends!

styles and code

CITE THIS NOTEBOOK

Solving Star Ocean's "Field of Wisdom"​
by Brad Klee​
Wolfram Community, STAFF PICKS, August 29, 2024
​https://community.wolfram.com/groups/-/m/t/3260648