Sokoban(en.wikipedia.org)
en.wikipedia.org
Sokoban
https://en.wikipedia.org/wiki/Sokoban
6 comments
For the interested, proof that Sokoban is NP-hard.
https://www.archim.org.uk/eureka/archive/Eureka-54.pdf#page=...
https://www.archim.org.uk/eureka/archive/Eureka-54.pdf#page=...
Interesting...
Back in college when I was applying to places (I can't remember whether it was an internship or a full-time job), one place gave me an online challenge that from what I remember was basically identical to this game. They had provided a minimal API in JavaScript for interacting with the state, and I remember being embarrassed that the only solution I could come up with was brute force. I had forgotten about this until I saw the animation on the Wikipedia page just before reading this comment, but now I'm amused that my solution might have been optimal after all!
Back in college when I was applying to places (I can't remember whether it was an internship or a full-time job), one place gave me an online challenge that from what I remember was basically identical to this game. They had provided a minimal API in JavaScript for interacting with the state, and I remember being embarrassed that the only solution I could come up with was brute force. I had forgotten about this until I saw the animation on the Wikipedia page just before reading this comment, but now I'm amused that my solution might have been optimal after all!
It's a little worse than that (probably); it's also PSPACE-complete: https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-comp...
Any nethack players here? I love the sokoban levels, probably my favorite little sidequest.
Hey cool, I'm building a game inspired by Sokoban where you're tasked with destroying evidence and cleaning up any trace of crime - It's called Hazard Pay.
It started as a game jam entry for Ludum Dare, but after the great feedback I decided it was simple enough to go for a full release.
- https//smitner.studio/hazardpay
It started as a game jam entry for Ludum Dare, but after the great feedback I decided it was simple enough to go for a full release.
- https//smitner.studio/hazardpay
I remember playing Sokoban on Mac around 1994.
This version had something I never saw since then: when you clicked on a square, your character would move automatically to that square, provided there existed a path. This was VERY convenient and I miss it.
I'm guessing this only applied to open spaces? Seems like applying that to spaces occupied by blocks would often imply ambiguous push direction.
The algorithm wouldn't push any blocks, but just walk along the way to your destination, way faster than doing it by hand
Also see this video essay on Thinking Rabbit and Hiroyuki Imabayashi (the author of Sokoban):
https://www.youtube.com/watch?v=DvEfSP-sRXI
https://www.youtube.com/watch?v=DvEfSP-sRXI
If you're interested in trying to make your own variations on Sokoban-like games, PuzzleScript[1] is tailor-made for the task, with a fascinating declarative approach to describing game rules.
A Sokoban-like game can also be an excellent way to familiarize yourself with a new game engine or graphics toolkit. My own project, Decker, includes a very short Sokoban to demonstrate how one might make turn-based tile-oriented games.[2]
[0] https://www.hempuli.com/baba/
[1] https://www.puzzlescript.net
[2] http://beyondloom.com/decker/goofs/sokoban.html