New game - FISP

[davidn]

It must be the time of year for miracles - I've just released something, and further, something that isn't a platform game. It's a smaller project, though - it's called FISP, and three of the letters stand for Impossible Sliding Puzzles.


Good luck.

This was a quick project born as a result of Professor Layton 2's final stages, where you're put through a variety of absolutely sadistic puzzles, a couple of which involve sliding awkwardly-shaped pieces around a board. When I gave up on being able to do them, I didn't turn to a walkthrough, and instead - being who I am - wrote a solver to find the solution for me. And a couple of months later, I realized that this was the perfect tool with which to construct my own horrific challenges.

And I remembered about it last week and finally stuck a full game together around it. Go in, slide things around, get in a rage, spread the pain around on Facebook and help me get some advertising revenue.

Comments

[ravenworks.livejournal.com]

It's only just now finally struck me that I would have no idea how to even start writing a solver for these! Even if you just brute force it, it seems like the possibility space would explode hopelessly after just a few moves... I mean, six pieces, four directions, and let's say the solution takes 20 moves; (6x4)^20 = 4,019,988,717,840,603,673,710,821,376 possible outcomes, that's an awful lot even for a computer... What kind of approach did you take..?

[davidn]

Wow, this reply window's changed. That'll take some getting used to. Anyway, let's see how long this lasts once I've got started.

My approach to writing solvers has basically been recycled ever since I did a senior honours project involving solving games of Solitaire - it builds up a tree of possible states, checking on each new possibility to see if the state has the goal piece in the goal squares.

When a state is added to the tree, a set of candidate states is added to a stack - states that it's possible to get to directly from that state by moving a piece one square in any direction. States in which pieces are now overlapping, or hitting walls, are immediately discarded, and states that the program has reached before are also removed by checking a hash map of previously visited states. It keeps going deeper until it can't make any more valid moves that don't take it back to a state it's gone into before, then goes back to the deepest state that still has possible moves (this is the curtailment of the possible outcomes).

And if/when you find a state that has the goal piece on the goal squares, you just ascend back through the tree to find the route that it took to get there. It's not the most efficient thing in the world, but it works at this scale (you could do something like prioritize states that come from moving the goal piece or freeing up spaces around it or something, but I didn't bother).

[ravenworks.livejournal.com]

Shoot, I didn't think about discarding/merging identical states! That makes WAY more sense... it's still an enormous number of possibilities, but that would cut it down to something manageable... Very smart :)

[(Anonymous)]

Depth-first search on the state graph? Not breadth-first plus heuristics?

(Sorry, I couldn't resist.)

[davidn]

I do have a heuristic - it's "pick among these at random"!

[(Anonymous)]

But not breadth-first? o.o

[davidn]

Well, as I have to generate all possible states on examining a state before selecting one to then expand, in some measure it's breadth-first - it doesn't immediately dive down into a state before it has its list of possibilities. Though to make it truly breadth-first, it would have to expand all the possibilities at one level before then moving on to the next, and with the next state being selected at random, that wouldn't bring much benefit.

If it could select the most likely-looking state across all the paths it's generated each time, though... aaagh. Don't drag me back into writing this ;)

[(Anonymous)]

Well, it doesn't have to generate all possible states first, since it could choose to generate them in arbitrary order, presumably, depending on how much “randomness” you depend on. But AsYouKnow, breadth-first searches are guaranteed to find the shortest path in terms of steps, though they can be heavier in temporaries (which I suppose is sometimes fatal in cases like this; I haven't seriously done this in ages). And then there's the rest of the tweaks one can make to graph search algorithms…

*ahem*

[davidn]

Right, so - I just changed the stack to a queue on a whim, and now the 20,000-move struggle of the final puzzle has just been solved in 27. So... slightly more efficient than I had thought (I'd thought the branching factor would have made it hopeless, despite my pruning of duplicates).

[(Anonymous)]

There's not a whole lot of branching given that the pieces are pretty densely packed in the space; at a given time there's often only a few that can move. It's not like computer Go.

And you always “merge duplicates”; that's what makes it a graph of states rather than a graph of refcells of states.

Bwahahahaha!

(Er, ahem.)

[xaq.livejournal.com]

After solving the first 2 my brain already feels about ready to go into nuclear meltdown.

I'll accept this as retribution for what I accidentally did to you with Story of the Blanks.

[kjorteo]

I like that you got him to play Story of the Blanks, and I can't even get him to watch Lesson Zero! Congratulations, I think.

[xaq.livejournal.com]

Never underestimate the power of Relax-O-Vision. (Or the insatiable curiosity it can spark, I guess.) :]

[kjorteo]

WHY

WHY WOULD YOU DO THIS TO ME

[davidn]

I'm not sure whether I should attempt to pass the blame, but you... sort of... inadvertently planted the seed for this!

[kjorteo]

Oh.

I'm so sorry.

[rakarr.livejournal.com]

Yep, that's that decided, I'm not going near this!
... until curiosity gets the better of me, thus validating the "killed the cat" saying a thousand times over.

[tamakun.livejournal.com]

Great, now I'm wondering if there's a way to create a sliding-tile puzzle where one of the pieces has a "hinge", to allow it to work its way around corners.

And with that, I'm severely causing aneurysms just trying to create that in a puzzle mechanic.

[tamakun.livejournal.com]

How do you even come up with puzzles like this? Do you lay them out with the knowledge that they're somehow solvable, or do you place the pieces in an aesthetically pleasing way and let your solver program see if they're possible?

[davidn]

Yes, the computer does the real work - what I did with the solver was feed it layouts that looked sufficiently intimidating to me, and then include them if it could solve them with a reasonable amount of trouble.