1-1 time with 9:33 is impossible
fastest i can get is 9:36 nonstop with your (bisqwit) replay.
Same here, I've only got to reproduce the exact record with the same strat in 2 stages or so... I'm wondering if it is due to key-pressed configuration... (Since I keep pressing 1 button, intead of tabbing it)
Also, is it takes the same time to move Up/Down & Left/Right, same with pushing a box? Because in some stages, you can do either & aparently looks the same...
Peter Box has been updated today.
It has some new timings now (unintentionally), and some instructions (see the "Game details" page), and a kick feature by the request of Samurai Goroh!
Also, the highscore saving bugs should have been resolved.
The trick behind seemingly impossible times is to use mouse navigation. Point&click where you want Peter to walk to and he'll walk there, a tiny bit faster than if you navigated using keyboard.
But it's risky, because he sometimes confuses the route. He will confuse it in predictable situations though, so it doesn't depend on luck.
The kick move can also be used to improve times in a few levels. Kick is difficult to do perfectly, because you need to wait exactly 0.5 seconds before moving, or the kick is cancelled.
Nice add you got there Bisqwit, the kick feature does reduce lots of time & it makes harder to find the best strat. I wonder how long will it take to see all the levels mastered with this strats :)
BTW, you forgot to mention that you kick with K, though is kind of obvious...
Like an account, you mean? Hehe, I think I'll be really hard for him, but that would be a little useful, because you could the the movie records from any computer, but you can play any level, so I guess this won't happen...
I can't get this game to work. I'm using Firefox 1.0.6, and everything shows up (instructions, details, and records) except after clicking Game, I get a blank window, and the timer runs.
Any ideas?
<Swordless> Go hug a tree, you vegetarian (I bet you really are one)
On 1-2, 1-3, and 1-5, BisqBot has solutions in fewer moves than what mere mortals have achieved. Are the BisqBot numbers accurate, are we not being clever enough?
I remember one of my programming teachers telling us about writing a Sokoban solver. And also that it ran out of diskspace while solving a particularly large puzzle, even though it only followed legal branches and had lots of methods for realizing when a move made completion impossible and stopping. Is yours better? Optimization is a favourite topic of mine.
I remember one of my programming teachers telling us about writing a Sokoban solver. And also that it ran out of diskspace while solving a particularly large puzzle, even though it only followed legal branches and had lots of methods for realizing when a move made completion impossible and stopping. Is yours better? Optimization is a favourite topic of mine.
I have applied lots of optimizations to my puzzle solver, and so far the bottleneck is the memory amount. Generally speaking, if the solving process takes longer than 4 minutes, the program will run out of memory and it'll only do 2 minutes worth of work in the next 10 hours when the OS is busy swapping the program's data in/out.
In terms of different states, the crawling speed is reached approximately when the number of simultaneously active states is approaching ~1.2M and number of analyzed positions is around ~9000k. (*)
The complexity of the program is defined by the maximum number of different possible positions the blocks may be on the level.
For a level with 7 blocks and little room of maneuvering, the solving is rather straightforward and takes only a few seconds, but for a level with 14 blocks such as 2-5, 1024 MB of RAM is too little.
The "BisqBot's corner" page in the game lists all levels that could be solved with the program with my current hardware.
Levels that are not listed there, usually contain too many movable blocks.
I believe 4-1 would be the next one to be solved, if I could compress the program's memory usage even further.
samurai goroh wrote:
Hi there Bisqwit, there are some levels in which the record time is just +0.03 secs from the theorical record, why does it has that difference? Is it just time presition?
0.03 seconds (1 frame) is all it takes for Peter to change his facing once.
The optimal solution apparently changes the facing one time less than the most accomplished player.
With mouse navigation, you can avoid most of the facing delays.
samurai goroh wrote:
Also, why not releasing those videos? The strat should be the same, wouln't?
As explained on the "BisqBot's corner" page, the videos are kept unreleased in order to not spoil the sport.
My original plan was to reveal the movies when a record has been made that runs the same route as BisqBot, but I haven't implemented this yet (and often, some alternative routes are equally fast).
samurai goroh wrote:
PS: Can you do something about the blunder repetition, it's annoying & you lose like 3 secs. I liked more when the text just appeared.
It's deliberately annoying. In the first versions, you could abort the animation by undoing, but currently it's not possible to do that. I might re-enable it later.
samurai goroh wrote:
Also, it doesn't reconize a blunder if you kick the box...
It does, but because of the graphical challenge to represent the blunder when the box moves a long way, it's not displayed.
------
(*) Technical stuff:
Analyzed positions are stored in a hash map, where the key is a N-byte array (state of level; N=number of blocks+1) and the value is an unsigned integer (best time so far to reach this state, or 0 if the state is not worth revisiting).
In C++, it's defined as __gnu_cxx::hash_map<CompressedLevelState,unsigned>.
When forming the CompressedLevelState, the array is sorted. The order of the blocks in the level does not matter.
Active states are stored in a hash map, where the key the level state (contains LevelWidth*LevelHeight*3 bits plus some caching variables) and the value is the history of moves to reach that position.
In C++, it's defined as __gnu_cxx::hash_map<LevelState,History>.
The history consists of an unsigned value denoting the cost in time to reach that situation, and an array of moves along with some caching variables.
New move candidates are found by
- trying to kick/push to every direction where applicable.
- trying to walk into every possible reachable location that is beside some block (using a Djikstra algorithm).
If the previous move was a "walk" move, only "kick/push" moves will be tried. If the "kick/push" move appears to be a blunder, it will be discarded.
After the forming of each candidate move, the resulting state of the level is examined against the Analyzed positions map:
- if the state has been marked dead, the move will be discarded.
- if the state has been reached before with smaller cost, the move will be discarded.
Otherwise, the cost will be saved in the Analyzed positions map and the move will be saved as a new active state for the next pass.
The hash of the level state is formed by first forming a CompressedLevelState (the N byte array where N = blocks+1) and then adding/xorring together the bytes in the array. The hash is only needed for speed. The "+1" in the "N" is there for the position of the player.
The moves in the history buffer are stored in a specially created linked list: when the list is copied, nothing is actually copied - instead a new branch is started. Therefore all the different states actually form a tree where every leaf leads to the single root.
The internal representation of the tree is a linked list with only a "prev" node, no "next" node. There is never need to locate sibling nodes. Reference-counting is applied to prevent leaking memory.
Nice to hear you got it working!
Thanks, but nope, I ripped all levels and graphics from the DOS Peterbox game, which itself seems to rip many levels from the original Sokoban game.
I was trying to see if I got 7.70 secs by calculating the moves with maths with the Game Details info, so here's what I got for the 1st level (1-1):
Left, Left, Left, Up, Up, Push Left, Down, Left, Push Up, Right, Up, Push Up, Left, Up, Push Right, Down, Right, Push Right, Up, Right, Push Down, Left, Down, Push Down, Right, Down, Push Left.
0.20 + 0.20 + 0.20 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 + 0.20 + 0.20 + 0.45 = 7.40 secs
So, where does the + 0.30 secs come from?
Now, calculating using the info where the record is displayed:
Moves: 27 --> (27-8)(0.2) = 3.8
Pushes: 8 --> (8)(0.05 + 0.40) = 3.6
Total --> 3.8 + 3.6 = 7.40 secs
So, what am I missing here? (If turning supposed to be 0 using mouse & kick wasn't used...)
Correction:
> Left, left, left, up, up, turn left, grab, push,
> down, left, turn up, grab, push,
> right, up, grab, push,
> left, up, turn left, grab, push,
> down, right, grab, push,
> up, right, turn down, grab, push,
> left, down, grab, push,
> right, down, turn left, grab, push.
You have 19 walks, 8 grabs, 8 pushes and 5 facing changes.
Walk is 0.2 seconds (6 frames), grab is 0.05 seconds (2 frames), push is 0.4 seconds (12 frames), facing change is 1 frame.
Therefore, 19*6+8*2+8*12+5*1 frames, that is 231 frames.
The game is rendered at 30 fps, therefore your time is 7.70 seconds - which is BisqBot's time.
[Edit]
So why is BoltR's timing different?
Apparently because there's a lag of 1 frame in checking whether the game is completed - a lag which BisqBot doesn't have!
I think I have to fix it!
If there's not a timing bug, BisqBot must be using a subtly different path that requires one less keyboard turn. That is, it's able to approach one more of the pushes head on than we do. Of course, this is impossible on 1-4, but on 1-4 it's possible we just haven't come off the first kick perfectly yet.
Maybe BisqBot doesn't penalize itself for keyboard turns prior to pushes where it's facing the wrong direction initially.
So why is BoltR's timing different?
Apparently because there's a lag of 1 frame in checking whether the game is completed - a lag which BisqBot doesn't have!
I think I have to fix it!
Allright, this problem has been fixed, and all human records have been updated to remove this 1 frame.
So why is BoltR's timing different?
Apparently because there's a lag of 1 frame in checking whether the game is completed - a lag which BisqBot doesn't have!
I think I have to fix it!
Allright, this problem has been fixed, and all human records have been updated to remove this 1 frame.
So, does this means that the frame check will be discounted or that if a new record is gotten you will take out that frame?
Why can't I save my record on level 7-3, I get the next message:
Record not saved! Timer was 0.
You made it with a version that was no longer supported by the serverside submission receiver.
If you still have it open, try again... I temporarily enabled the old timer code.
Hehe, I love puzzle games in general, & really like this one with all the additions it has now :)
Bisqwit wrote:
You made it with a version that was no longer supported by the serverside submission receiver.
If you still have it open, try again... I temporarily enabled the old timer code.
Well, my brother turned off the Comp, but I remember the strat I used, so I can do it again (& will...)
I have updated the game again...
It should now work a little smoother. There was some lag in responsiveness since kicks were implemented.
It should also now detect a much wider range of blunders than before.
Timings or such were not changed.
Edit: Blunder "R" timing was slightly shortened.
What does the "Record saved! Good movie, but it can still be improved by more than xx secs" message means? Does the strat I used wasn't good, meaning there is a better strat or where my moves just to slow & I could had saved some time if they where perfect?
BTW, I got this message in level 4-4 if that's relevant...
PS: Does kicked blocks move faster or was my strat better this time, because I saved like 20 secs...
