FS#6625 - Sokoban Improvements

Attached to Project: Rockbox
Opened by absurdlyobfuscated (DrSpud) - Tuesday, 06 February 2007, 02:37 GMT
Task Type Patches
Category Games
Status Closed
Assigned To No-one
Operating System All players
Severity Low
Priority Normal
Reported Version
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


A large number of improvements and fixes to the game Sokoban:

- Support for levels that have the mover start on a goal ('+' character).
- New bitmaps for when the mover is on a goal, plus the brick texture was slightly reworked to look cleaner.
- The undo function has been mostly rewritten and uses one byte per undo (was 21 bytes/undo before). This allows for a nearly unlimited number of undos (5000) in the same amount of memory that about 260 could fit before (but only 5 were allocated, for some reason). Additionally, non-moving button presses no longer eat an undo slot.
- Redundant code for both the undo and player movement has been unified & modularized similar to  FS#5356 , but even more compactly (and I'd like to think it's more readable, too).
- Redo feature added.
- Keys remapped to accommodate redo, some switched around a little. Let me know if any of the key mappings don't make sense, as I'm not very familiar with most of the platforms and some of the mappings are a little weird.
- Button repeat enabled on platforms that support it. Don't know why it wasn't before, since it's so trivial.
- Level & move info cleaned up and moved to bottom of screen for targets with unaccommodating screen dimensions. Sansa & Gigabeat targets now display correctly, as should any future targets.
- Skipping of the help text screen via any button press now possible.
- 'Pushes' counter for targets with a big enough screen.
- 'Level Completed' screen that shows moves & pushes.
- Error messages fixed: they now display for 2 seconds instead of 0.
This task depends upon

Closed by  Zakk Roberts (midkay)
Tuesday, 13 February 2007, 06:48 GMT
Reason for closing:  Accepted
Additional comments about closing:  Committed, thanks a lot for your work! :)
Comment by Paul Louden (darkkone) - Tuesday, 06 February 2007, 15:50 GMT
My assumption would be that 5 undos were allocated as a matter of challenge: Don't mess up, or if you do, catch it 5 steps or less from when you did.

If you need more than that, there's a good chance you'd be better off just restarting the level, right?
Comment by absurdlyobfuscated (DrSpud) - Tuesday, 06 February 2007, 17:24 GMT
I guess I just saw an opportunity to optimize memory usage, and never really thought of the way it affects the difficulty. I suppose there are some levels where more undos would help without really making it easier - level 60, for example, where it takes 1300+ moves and most is just back-and-forth repetitiveness. It really sucks to realize you messed up 6 moves back and have to do over a thousand moves again to beat a level. Here's a random thought: what if the number of undos were based on the size (or complexity) of a level? Or just have a small, constant number to keep it challenging - if that's what we really want (of course redo would have to go, but I'm fine with that). I say around 25, 10 minimum; 5 is just too few.
Comment by Paul Louden (darkkone) - Tuesday, 06 February 2007, 17:51 GMT
Here's a 'crazy' idea: A dynamic sized undo buffer. (Well, the buffer wouldn't be dynamic, really, but the amount you had access to would be.)

At the beginning of a level you have 1. Every 10th move adds one. So, more complex levels automatically give you more available undos the further you are into the level. (As well, if you REALLY wanted to, you could wobble back and forth to increase them, I suppose, but for purposes of increasing the number you could only count actual pushes as opposed to steps, perhaps).

Just a concept, but it'd allow the number of undos to scale with the complexity of the level without having to predetermine a number for each level.
Comment by Zakk Roberts (midkay) - Tuesday, 06 February 2007, 18:51 GMT
Nice work on this patch, Sean, quite a list of worthwhile improvements and additions. :)

As for the undo limit issue.. I think unlimited (or merely memory-limiting) undos is the best system after looking at all the options (at least all the options I see). Limiting the number of undos to a constant level can be a pain on the levels that require over a thousand moves, basing the number of undos on the level is painful and has to be done manually, basing it on the number of moves can be exploited.... You can already skip levels, so if one really wants to use unlimited undos to "cheat" and make it easier on themselves, they can already just make it real easy and skip the level. I think unlimited is the best.
Comment by absurdlyobfuscated (DrSpud) - Wednesday, 07 February 2007, 06:09 GMT
I'm starting to agree more with Zakk about the undos. Unlimited undos effectively eliminate any frustration from having to completely restart complicated levels and makes the game more enjoyable and fun, which is what we most certainly want. Besides, most other Sokoban games for platforms that aren't memory limited have unlimited undo and redo.

New changes:
- Number of undos is now dynamic - 4k to 32k based on how much is plugin memory is left over.
- Keys for X5 fixed. According to , simultaneous button presses on the X5 don't work. Redo & level repeat had to be cut, but you can now change levels.
- Some minor cleanup.
Comment by Zakk Roberts (midkay) - Wednesday, 07 February 2007, 23:19 GMT
Is this about ready to be committed? :)
Comment by absurdlyobfuscated (DrSpud) - Thursday, 08 February 2007, 03:36 GMT
I think it's ready. It's been well tested on most platforms (sim only except for h140) and it's clean & functional. I can't think of anything more to add that it really needs. I guess the question is, do the real devs around here think it's ready? Everyone agree with the other changes, not just the undo? Any other thoughts on the changes in button config?
Comment by Zakk Roberts (midkay) - Friday, 09 February 2007, 04:14 GMT
Everything else seems great and uncontroversial, so as long as you don't have an update/addition to this planned/in progress, it seems ready for commit. :)

I probably won't get to that tonight... if I don't, then it'll be Friday night.
Comment by absurdlyobfuscated (DrSpud) - Friday, 09 February 2007, 07:57 GMT
I guess I would have removed the comment on line 190 that doesn't make sense anymore, but I wasn't planning anything else. I did have a few ideas - for example, dynamic display size where small levels would use a large magnify & vice versa, simple or even advanced deadlock detection, saving/replaying solutions, move animations, and some others - but I know they'd be _way_ outside the scope of the project ;)
Comment by Zakk Roberts (midkay) - Friday, 09 February 2007, 09:26 GMT
Haha. Those all sound like they'd be very cool things to see in Sokoban. If you're up for it, they're all definitely very welcome!

I'm just off to bed now. Tomorrow I'll commit this. :)
Comment by absurdlyobfuscated (DrSpud) - Saturday, 10 February 2007, 18:44 GMT
Hmm, maybe saving solutions/progress wouldn't be unreasonable. I could have it save the current level's progress when exiting, like sudoku does. Perhaps it could support normal text format levels too (In the meantime, I have a program that converts text levels to Rockbox format, it's on my website: ). I think most of the others would qualify as feature creep, though. Regardless, any future additions will be in a new task.

I did find one bug caused by code cleanup that broke the '+' character support. Now I think it's good :)
Comment by Zakk Roberts (midkay) - Tuesday, 13 February 2007, 01:37 GMT
Hey Sean.

Sorry it's taking me so long to get this in SVN. I won't try to convince you it's not my fault, I did delay for a few days. But I went into VMware to commit last night, and Rockbox won't compile at all (not this patch's fault..). I might need to reinstall it.

I'm re-downloading it (VMware image) and giving it another shot. If I still can't compile, I'll just commit it later tonight without having tested it - I'm sure you've done this yourself. :)
Comment by absurdlyobfuscated (DrSpud) - Tuesday, 13 February 2007, 05:10 GMT
I can vouch for it, sure, but you'd certainly want to try it out so you can see all the changes first-hand. I've run into the same problem as you before - I've had to run the configure script again, run a 'make clean', or in some cases, delete my source files & checkout again just to get it to compile.

Don't worry about it whatever happens, it's not like this patch is very urgent or anything. And I found a bug I missed before, too, so it's not a bad thing that it wasn't committed right away.

Also, I've made some progress on supporting normal text-format and RLE levels. It'll be a while, but it will let even the most memory limited (archos) players cache all the levels at once. More features are planned, like saving/resuming progress/solutions. I'd like to hear any suggestions anyone has about them.
Comment by Zakk Roberts (midkay) - Tuesday, 13 February 2007, 06:30 GMT
That's great. Llorean was kind enough to point out that the VMware image was just updated because gcc 4.0.2 was no longer supported for some reason. Just updated, this will be in SVN in around 20 minutes. :)

Sounds good about what you're working on, looking forward to future developments. Saving progress when you quit automatically and maybe giving the option to resume when you start the plugin again sounds like a nice feature. Don't forget about the forums if you're looking for input/opinions, many are happy to oblige there. :)