Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Glad you find it interesting!

I'm familiar with PuzzleScript, though I haven't tried to make something with it myself. If someone were to make a state space visualizer for PuzzleScript, I'd certainly find it interesting too!

But I'm not sure it's viable. Consider a very simple 5 x 5 room with a character and two pushable crates. There's 25 walkable tiles that the character and each crate can be on, so that's 25 * 25 * 25 = 15625 states. Divide by two (the factorial of 2) if the crates are interchangeable, but that's still over 7000 states for a really simple puzzle. Most PuzzleScript levels have more walkable tiles and more interactive elements. A 6 x 6 tiles room with a character and 3 crates would be 36 * 36 * 36 * 36 / 6 = 279936 states. It grows exponentially and most PuzzleScript levels probably have millions or billions of states, if not even more.

It's intractable to calculate such a large state space. There's a reason PuzzleGraph represent rooms as abstract nodes instead of supporting tile based levels.

Now, there was some researcher who found a way to reduce the state space for classic Sokoban, but the method was quite complex and also quite tailored to the specific rules of Sokoban. I'm not sure it generalizes to the extreme flexibility of PuzzleScript. In any case it would be a highly complex research problem to solve, if it's possible. If someone attempts it, good luck to them!

Do you have a link to that research? It sounds very interesting!

(+1)

Unfortunately I can't find the research paper I referred to (I read it many years ago) but if you search on Google Scholar for 'sokoban "state space"' there are a lot of papers covering the topic in various ways.