Trying to solve a Sokoban level with brute force
- January 22, 2009 by Emanuele Feronato
- Filed under Game design, Php | 13 Comments
Before you even think this script will solve a Sokoban level, I must warn you: this script won’t solve a sokoban level, it won’t even recognize whether a level is solved or not.
This script, part of an old project I am going to bring to life again, will just make Sokoban wander around the maze eventually pushing crates here and there, according to Sokoban’s rules.
Feel free to add some backtracking to make it more interesting, but I have to say coding a Sokoban solver could be a nightmare.
If you want to see another Sokoban script (this time to play the game), read Javascript Sokoban game script.
Sokoban levels are shown and created this way:
# = wall
$ = crate
. = place
* = crate in place
@ = man
+ = man in place
And now the script…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 | <?php function echo_map($map,$width){ $rows = strlen($map)/$width; for($x=0;$x<$rows;$x++){ for($y=0;$y<$width;$y++){ $pos = $y+$x*$width; if($map{$pos}==" "){ $return .= " "; } else{ $return .= $map{$pos}; } } $return .= "<br>"; } return("<div style = \"font:normal 18px lucida console\">".$return."</div>"); } function is_solved($map){ return(!strpos($map,"$")); } function is_empty($map,$pos){ return(($map{$pos}==" ")or($map{$pos}==".")); } function is_crate($map,$pos){ return(($map{$pos}=="$")or($map{$pos}=="*")); } function get_player_pos($map){ return(strpos($map,"@")+strpos($map,"+")); } function echo_possible_directions($map,$width){ $player_pos = get_player_pos($map); if (is_empty($map,$player_pos-1) or (is_crate($map,$player_pos-1) and is_empty($map,$player_pos-2))){ $return .= "L"; } if (is_empty($map,$player_pos+1) or (is_crate($map,$player_pos+1) and is_empty($map,$player_pos+2))){ $return .= "R"; } if (is_empty($map,$player_pos-$width) or (is_crate($map,$player_pos-$width) and is_empty($map,$player_pos-2*$width))){ $return .= "U"; } if (is_empty($map,$player_pos+$width) or (is_crate($map,$player_pos+$width) and is_empty($map,$player_pos+2*$width))){ $return .= "D"; } return($return); } function move($map,$width,$dir){ $player_pos = get_player_pos($map); if($dir=="L"){ if($map{$player_pos}=="@"){ $map{$player_pos} = " "; } else{ $map{$player_pos} = "."; } if (!is_empty($map,$player_pos-1)){ if($map{$player_pos-1}=="$"){ if($map{$player_pos-2}==" "){ $map{$player_pos-2}="$"; $map{$player_pos-1}=" "; } else{ $map{$player_pos-2}="*"; $map{$player_pos-1}=" "; } } else{ if($map{$player_pos-2}==" "){ $map{$player_pos-2}="$"; $map{$player_pos-1}="."; } else{ $map{$player_pos-2}="*"; $map{$player_pos-1}="."; } } } if($map{$player_pos-1}==" "){ $map{$player_pos-1}="@"; } else{ $map{$player_pos-1}="+"; } } if($dir=="R"){ if($map{$player_pos}=="@"){ $map{$player_pos} = " "; } else{ $map{$player_pos} = "."; } if (!is_empty($map,$player_pos+1)){ if($map{$player_pos+1}=="$"){ if($map{$player_pos+2}==" "){ $map{$player_pos+2}="$"; $map{$player_pos+1}=" "; } else{ $map{$player_pos+2}="*"; $map{$player_pos+1}=" "; } } else{ if($map{$player_pos+2}==" "){ $map{$player_pos+2}="$"; $map{$player_pos+1}="."; } else{ $map{$player_pos+2}="*"; $map{$player_pos+1}="."; } } } if($map{$player_pos+1}==" "){ $map{$player_pos+1}="@"; } else{ $map{$player_pos+1}="+"; } } if($dir=="U"){ if($map{$player_pos}=="@"){ $map{$player_pos} = " "; } else{ $map{$player_pos} = "."; } if (!is_empty($map,$player_pos-$width)){ if($map{$player_pos-$width}=="$"){ if($map{$player_pos-2*$width}==" "){ $map{$player_pos-2*$width}="$"; $map{$player_pos-$width}=" "; } else{ $map{$player_pos-2*$width}="*"; $map{$player_pos-$width}=" "; } } else{ if($map{$player_pos-2*$width}==" "){ $map{$player_pos-2*$width}="$"; $map{$player_pos-$width}="."; } else{ $map{$player_pos-2*$width}="*"; $map{$player_pos-$width}="."; } } } if($map{$player_pos-$width}==" "){ $map{$player_pos-$width}="@"; } else{ $map{$player_pos-$width}="+"; } } if($dir=="D"){ if($map{$player_pos}=="@"){ $map{$player_pos} = " "; } else{ $map{$player_pos} = "."; } if (!is_empty($map,$player_pos+$width)){ if($map{$player_pos+$width}=="$"){ if($map{$player_pos+2*$width}==" "){ $map{$player_pos+2*$width}="$"; $map{$player_pos+$width}=" "; } else{ $map{$player_pos+2*$width}="*"; $map{$player_pos+$width}=" "; } } else{ if($map{$player_pos+2*$width}==" "){ $map{$player_pos+2*$width}="$"; $map{$player_pos+$width}="."; } else{ $map{$player_pos+2*$width}="*"; $map{$player_pos-$width}="."; } } } if($map{$player_pos+$width}==" "){ $map{$player_pos+$width}="@"; } else{ $map{$player_pos+$width}="+"; } } return($map); } /* # = wall $ = crate . = place * = crate in place @ = man + = man in place */ $width = 8; $map = " ### #.# # #######$ $.##. $@#######$# #.# ### "; for($x=1;$x<=100;$x++){ echo echo_map($map,$width); $possible = echo_possible_directions($map,$width); echo "Possible directions: $possible"; $new_dir = $possible{rand(0,strlen($possible)-1)}; echo " - going ".$new_dir; $map = move($map,$width,$new_dir); if(is_solved($map)){ echo "<h1>S</h1>"; } } ?> |
And this is the result:
Feel free to do something interesting with the script…
13 Responses
Leave a Reply
TUTORIAL SERIES:
- Una guida completa al gioco del poker online e una selezione dei migliori casino online.
- casino online
- migliori casino online
- BlackJack online
- casinò online




… been solved yet. but i can!
First off, I appologize if this offends you, but are you a boy or a girl?
I ask only because First i thought you were a guy, because your name is Emanuele. But then you got your new logo and it looks like you are a girl. So i figured, “i guess Emanuele could be a girls name”. Now i see at the bottom of this post, “the geek has spoken… share HIS words”. This causes confusion for me.
It really doesnt matter, i just want clarification. Either way, Great post. Love your work. Look forward to seeing more of your work
lol… Alex.
Alex, after this post ( http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/ ) not even the regulars are sure anymore.
:P
What use is this script?
lol, he is a guy, the logo is a bit misleading but read this post:
http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/
The first thing I would do with this script is breaking out of the loop once is_solved() returns true.
It is not a big optimization but the script wouldn’t print many useless iterations of the map.
i think, gilrs will never be interested with these kind of things :) this answer at half for the question i guess :)
oh, and thanks a lot for good posts Emauele … i’m yure fan !
Good job. Now you are just a step away from an evolutionary algorythm for generating Sokoban puzzles by the thousands.
Anyone know how I can contact Emanuele? I think someone may be trying to steal Emanuele’s games and put them under their own name.
Whoop, nevermind. Its not there anymore so I assume they did the right thing and removed it.
Looks good :)
First the Soduku and now this. Keep up all these “classic” engines. I really am interested in learning how to make these type of common well used generic engines.