Since the last blog post, I finished up revisions on the other areas in the game and sent out a test build to a few people. Still not done getting feedback from that, but overall the game seems to at least be improving. So that’s good news.
Needless to say, there’s quite a number of things that I could write about. But since automated puzzle generation/solving seems to be a pet topic of mine lately for the devlog. I thought I might cover a little bit of how I adapted the automated solver to work for the “snake puzzles.”
There are two main types of panels in the game, if categorized based on how you interact with them. Those are the “toggle” panels, which you click on, and the “snake” panels, which you walk around on. I mostly refer to the snake panels as “walking” panels, but the name still sticks around in the code from the early development days when you weren’t walking on them.
In any case, because of the nature of the input method for the walking puzzles, the same brute force method of finding all possible solutions doesn’t really work.
Admittedly, there is probably a much smarter way of doing things than what I chose to do, but since I don’t want to spend too much time on the auto solver unless I really have to, I chose to simply take the approach of feeding the output of the current solver into a separate “pruning pass.” This works well enough, because all the solutions which are walk-able are really just a subset of the solutions that are possible using the click-to-toggle mechanics.
I chose to essentially take the output of the brute force solver and feed it through two rejection passes. One is a broad (and hopefully fast) rejection pass, which will never reject valid solutions, but will still leave some impossible solutions un-rejected.
The above grid represents a 3×5 solution state that we might be checking to see if it could be done by walking. I didn’t draw any symbols on the panel because it would be irrelevant as that part of solution validation is already done by this point.
So we take this panel and feed it into our first rejection pass. This broad and hopefully fast pass simply checks to see if all of the walked tiles (those would be the ones in white in the above image) are part of the same area. Since as the player can only step on tiles which are adjacent to ones they have already stepped on, this is a guaranteed property of all valid solutions.
Obviously, we can see that there are several different white regions, so this solution is not valid. But the question you might have in your mind is how I would go about that in code? Well, since I already have a function to find all the tiles in a given area, I simply look across the panel until I find a single white tile, call the function to find all the tiles in that area, and then I compare the count of tiles found to the total number of white tiles in the solution state. If they’re equal, then we pass it on to the next pass.
If not, we reject the solution as invalid.
int whiteTileCount = 0;
bool isValidSolution = false;
foreach(bool b in currentState)
{
if(b) whiteTileCount++;
}
for(int x = 0; x < width; x++)
{
for(int y = 0; y < height; y++)
{
if(currentState[x+width*y] && !lockedTiles[x+width*y]) //We only want to look at the area of white tiles
{
ArrayList checkedTiles = new ArrayList();
int num_same_tiles = 0;
FindAllTilesInArea(x, y, ref checkedTiles, ref num_same_tiles, true);
if(num_same_tiles == whiteTileCount)
{
//Could be possible, so we do further testing, we
//want to OR the values here, because if any spot
//on the panel allows the solution to be drawn,
//it's valid
isValidSolution = isValidSolution | IsSolutionDrawableFrom(x, y, tempState.Clone() as bool[]);
}
else
{
//We found a disconnected white area, this in and
//of itself will exclude this solution from being
//possible on a snake panel
isValidSolution = false;
goto EndOfThisSolution;
}
}
}
So, we've rejected the previous state and now we will move on to another potential solution state (pictured above). This one passes the first test, as all of the white tiles are connected into one area. So that means it it will get passed on to the second phase.
In this phase, we walk through the panel, tile by tile, from all available starting points (the example panel starts in the bottom left), and we mark off each tile as we go through it. When we reach a branch, we follow out one of the branches until we have eaten all of the tiles. If we do not eat all the tiles by following a branch, that means there is a dead end in the panel and it is not walk-able.
Below is a visualization of this approach.
The code to do this is somewhat more complex than the first pass, and involves a recursive function:
public bool IsSolutionDrawableFrom(int x, int y, bool[] testState)
{
testState[x+width*y] = false;
bool returnVal = false;
if(x > 0 && testState[(x-1)+width*y]) returnVal = returnVal | IsSolutionDrawableFrom(x-1, y, testState.Clone() as bool[]);
if(x 0 && testState[x+width*(y-1)]) returnVal = returnVal | IsSolutionDrawableFrom(x, y-1, testState.Clone() as bool[]);
if(y < height-1 && testState[x+width*(y+1)]) returnVal = returnVal | IsSolutionDrawableFrom(x, y+1, testState.Clone() as bool[]);
if(returnVal) return true;
foreach(bool b in testState)
{
//if we reach this point, we've hit a dead end somewhere, this
//means if find a lit tile that's disconnected from somewhere we
//could walk to, then this solution must be untenable;
if(b) return false;
}
return true;
}
That's pretty much it for it this week. Perhaps next week I'll discuss a spoilery meta-puzzle thing I've been working on lately. Although if you'd follow the development live on twitch, you'd already know about that!
Taiji 