My new project is a Sokoban game. For those of you who don't know Sokoban, it's a game where the goal is to push blocks/crates into the goal positions. Pulling is not allowed. It becomes difficult because space is tight. These puzzles often seem simple, but can be very difficult.
So far I've implemented:
1. 4 levels, each loadable from txt files. New levels can easily be added. (2 of the levels have been stolen from the internet)
2. Possibility to save the current game to file, and to load it at a later time
3. Up to 10 undos, in case you fuck it up.
5. Background music which can be turned on and off. (that's why the zip file is so big). The music was downloaded from http://www.lucasheil.com/songs
6. A separate start menu screen
What I want to implement, but might be very difficult:
1. A check for when it has become impossible to finish the level
2. A solver
3. More levels (this one is easy)
Sokoban
Sokoban
- Attachments
-
- Sokoban zipped.7z
- (7.92 MiB) Downloaded 415 times
Re: Sokoban
There was a sokoban clone on the PC-Engine (Turbo Grafx 16) called BoxyBoy. Played that one quite a bit when I was a little sprat. 
Very nice work uglypie, I'm impressed.
Your code is very readable as well; I had no problem following it and seeing how you implemented certain features.
If you're serious about creating a solver (unwinnable condition checker is also essentially a solver), I recommend this book: AI: A Modern Approach. The first few chapters should enable you to make a decent solver.
Very nice work uglypie, I'm impressed.
Your code is very readable as well; I had no problem following it and seeing how you implemented certain features.If you're serious about creating a solver (unwinnable condition checker is also essentially a solver), I recommend this book: AI: A Modern Approach. The first few chapters should enable you to make a decent solver.
Chili
Re: Sokoban
Thanks chili! I'm glad to hear you could understand my code. It's not easy to know when it's only ever me who's reading it 
I had a look into Sokoban solvers, and it seems to be a pretty difficult problem. I might check out that book later on (but it has to be worth the shipping time over to Norway). First I'm gonna try implementing a deadlock search for a subsection of the playing board. Maybe I can expand that search, or at least use it in a general solver.
I had a look into Sokoban solvers, and it seems to be a pretty difficult problem. I might check out that book later on (but it has to be worth the shipping time over to Norway). First I'm gonna try implementing a deadlock search for a subsection of the playing board. Maybe I can expand that search, or at least use it in a general solver.
Re: Sokoban
Yeah, Sokoban can be pretty difficult if you're looking for an optimum solution and you have a large field with a lot of boxes. But if you just want a solution and your puzzles are of a reasonable size, then a simple best-first search algorithm with something like a manhattan-distance cost function should do the trick. Add in a hash table for pruning identical subtrees and a simple algorithm to detect obvious deadlock board positions and you should be gold.
If you wait long enough I'm going to cover this stuff in a tutorial someday, but I don't think you're that patient.
Who knows, I might even use Sokoban as the test case when teaching search.
As for the book, get the electronic version. I have it on my iPhone and I read it on the train to and from work.
If you wait long enough I'm going to cover this stuff in a tutorial someday, but I don't think you're that patient.
Who knows, I might even use Sokoban as the test case when teaching search.As for the book, get the electronic version. I have it on my iPhone and I read it on the train to and from work.
Chili
Re: Sokoban
Thanks for the tips chili! I've implemented the search now, using the procedure you described.
If you press enter while playing the game, the solver starts. When it is finished, the blue bear shows you the solution. It solves at least the 5 first levels within a reasonable time, but for the rest it probably needs a lot longer to solve (and a lot of memory). In addition to this, it doesn't find the optimal solution (that would take much longer), so you'll want to scream at the blue bear when he shows you his solution.
I've also added 90 more puzzles that are taken from the XSokoban game (the original), and fixed a few bugs. For example the ctrl-z function is much more intuitive now. I also turned off the music.
Here's the details of the implementation:
It's basically a depth first search, with four possible moves at each iteration of the search. I execute the move which creates the shortest total distance from each block to its closest goal first, and then the other three in order. For each block moved, I check if it got stuck. This is done by checking a precomputed matrix of "unsafe" positions, such as corners. It also checks for a few other obvious deadlocks, like four blocks clumped together, and 2 blocks clumped together at a wall.
At each search depth (search depth corresponds to number of moves), I check if the current state of the board has been seen before. This is done by using an unordered_set, which is a hash table. I hash a board by overlaying the block positions and player position to a precomputed table of random values, and xor these values. If a board has been seen before, the search in the current part of the tree is stopped. If the board hasn't been seen before, it is added to the hash table.
To save the solution, I use a list of boards. The current board which is being searched in is added to the list. If it turns out the search failed in this board, the board is removed from the list. To get the solution, i.e the boards that led to the solution, I can just pop the front of the list until it is empty.
It got quite complicated, and the code is probably quite unreadable. Especially the custom hashing function. I had to use a custom function because a vector of vectors can't be hashed by anything in the standard library.
If you press enter while playing the game, the solver starts. When it is finished, the blue bear shows you the solution. It solves at least the 5 first levels within a reasonable time, but for the rest it probably needs a lot longer to solve (and a lot of memory). In addition to this, it doesn't find the optimal solution (that would take much longer), so you'll want to scream at the blue bear when he shows you his solution.
I've also added 90 more puzzles that are taken from the XSokoban game (the original), and fixed a few bugs. For example the ctrl-z function is much more intuitive now. I also turned off the music.
Here's the details of the implementation:
It's basically a depth first search, with four possible moves at each iteration of the search. I execute the move which creates the shortest total distance from each block to its closest goal first, and then the other three in order. For each block moved, I check if it got stuck. This is done by checking a precomputed matrix of "unsafe" positions, such as corners. It also checks for a few other obvious deadlocks, like four blocks clumped together, and 2 blocks clumped together at a wall.
At each search depth (search depth corresponds to number of moves), I check if the current state of the board has been seen before. This is done by using an unordered_set, which is a hash table. I hash a board by overlaying the block positions and player position to a precomputed table of random values, and xor these values. If a board has been seen before, the search in the current part of the tree is stopped. If the board hasn't been seen before, it is added to the hash table.
To save the solution, I use a list of boards. The current board which is being searched in is added to the list. If it turns out the search failed in this board, the board is removed from the list. To get the solution, i.e the boards that led to the solution, I can just pop the front of the list until it is empty.
It got quite complicated, and the code is probably quite unreadable. Especially the custom hashing function. I had to use a custom function because a vector of vectors can't be hashed by anything in the standard library.
- Attachments
-
- Sokobak Zipped.7z
- (135.81 KiB) Downloaded 429 times
Re: Sokoban
The blue bear is on drugs!
This is pretty damn impressive stuff bro, I'm surprised you whipped it up this fast. I was just going to bed when I saw this post, so I had to download it and take a peek. I'll look at it in more depth tomorrow.
This is pretty damn impressive stuff bro, I'm surprised you whipped it up this fast. I was just going to bed when I saw this post, so I had to download it and take a peek.
I'll look at it in more depth tomorrow.Chili
Re: Sokoban
Wow! That was really cool.
I'll have to take a better look tomorrow as well, but at a quick glance that solving script looks a lot cleaner and shorter that what I expected it to be.
There's one thing though, don't now if its just my crappy computer but the solver seems to go on an endless loop at level 3, if you without moving try to solve it.
I'll have to take a better look tomorrow as well, but at a quick glance that solving script looks a lot cleaner and shorter that what I expected it to be.
There's one thing though, don't now if its just my crappy computer but the solver seems to go on an endless loop at level 3, if you without moving try to solve it.
ʕ •ᴥ•ʔ
Re: Sokoban
Hmm, I think I spy Zorbrist in your transposition table bro. Definately the way to go. I like the way you precompute unsafe locations for boxes on the map. Nice optimization there. All in all I found your implementation pretty easy to follow and understand.
Definately the way to go. I like the way you precompute unsafe locations for boxes on the map. Nice optimization there. All in all I found your implementation pretty easy to follow and understand.Chili
Re: Sokoban
Thanks chili and LuX 
It solves level 3 as well, but it takes a couple of minutes. It should theoretically solve all of the levels, but that could take days and weeks, and a lot of memory. The time it takes to find a solution depends a lot on the max depth of the search. The solution with shortest depth corresponds to the optimal solution, but this might take a long time to find. In level 4, if you don't set a max depth, it solves it within a few seconds, but the solution is really crappy. Bottom line is, the implementation works, but could be heavily optimized in a lot of places. I don't think I'm gonna bother with that though. The fun part was just getting it to work
I want to move on to a more challenging game, perhaps with some animations and stuff, but I haven't come up with any ideas yet. Perhaps it would be a good idea to watch some more tutorials first
It solves level 3 as well, but it takes a couple of minutes. It should theoretically solve all of the levels, but that could take days and weeks, and a lot of memory. The time it takes to find a solution depends a lot on the max depth of the search. The solution with shortest depth corresponds to the optimal solution, but this might take a long time to find. In level 4, if you don't set a max depth, it solves it within a few seconds, but the solution is really crappy. Bottom line is, the implementation works, but could be heavily optimized in a lot of places. I don't think I'm gonna bother with that though. The fun part was just getting it to work
I want to move on to a more challenging game, perhaps with some animations and stuff, but I haven't come up with any ideas yet. Perhaps it would be a good idea to watch some more tutorials first
Re: Sokoban
like your program, too. There is the class "Sprite" for loading images in your program and it's very useful. Can i use it in my programs ?? And have you any idea for a source code that could resize an image, because when the program hasn't got the right width and height, it can't draw the images :/