Jump to content
IGNORED

Sokoban


Andrew Davie

Recommended Posts

I tried really really hard to make the 9-row version work, but it proved impossible for the NTSC version due to timing issues. The tile engine uses "spare time" in the middle of the screen to do various tasks on a multitasking/timeshare basis. It requires a minimum amount of time *somewhere* to do some of those longer tasks. This is usually found in the vertical blank or overscan period. However, when I switch to 9 character rows, that reduces bot the vertical blank and the overscan and - unfortunately - the maximum timeslice "availability" reduces too. Just below the limit required for the tile engine "tricky bits". So, although PAL can handle 9 character rows just fine - NTSC can't quite. So, I've reverted to 8 lines for both. Alas.

This version is now format-switchable via the RIGHT DIFFICULTY SWITCH.  A is NTSC and B is PAL, I think. Additionally, the left difficulty will toggle between PAL50 and PAL60 if PAL is chosen with the right switch.  

Source code is included for this build.

Oh, I've added another 34 levels - these are getting hard. To make it easy to get to them, they are currently the first 34 levels of the game, and then it starts at the earlier levels (easy-on-up). Remember, to restart a level, hit RESET, and to skip to the next level, hit SELECT.

The move counter is working again.

Interesting with this game I don't really need a "game over" screen/sequence... because you never die. 

 

sokoboo_SOURCE_20190806.zip sokoboo_20190806.bin

  • Like 6
Link to comment
Share on other sites

5 minutes ago, Nathan Strum said:

Wondering if you could make a paint program out of this...

Yes, pretty easily. But it's not using the tile engine for the title screen, just a bitmap buffer and colour changes on a per-line basis.

Edit: actually it's a buffer in ROM, but it would be straightforward to switch it to a RAM buffer.
 

Edited by Andrew Davie
Link to comment
Share on other sites

2 hours ago, Andrew Davie said:

So little love/feedback.

Downloaded the latest ROM and can confirm the following on actual hardware:

 

  • The counter is working
  • Format-switchable also works.  For PAL, I get the expected screen role, since I have an NTSC console
  • Upon startup (NTSC format), the screen role still persists.  Not sure if this was supposed to be corrected with this release, so I thought I should mention it.     

Thanks for the updated ROM.:thumbsup:  Those new levels are hard.

Link to comment
Share on other sites

5 hours ago, Andrew Davie said:

So little love/feedback.

I like it.

It's harder than it looks though. I found this on Wikipedia:

 

Sokoban can be studied using the theory of computational complexity. The problem of solving Sokoban puzzles has been proven to be NP-hard.[6][7] Further work showed that it was significantly more difficult than NP problems; it is PSPACE-complete.[8] This is also interesting for artificial intelligence researchers, because solving Sokoban can be compared to the automated planning that needs to be done by a robot that moves boxes in a warehouse.

Sokoban is difficult not only due to its branching factor (which is comparable to chess), but also its enormous search tree depth; some levels can be extended indefinitely, with each iteration requiring an exponentially growing number of moves and pushes.[9] Skilled human players rely mostly on heuristics; they are usually able to quickly discard futile or redundant lines of play, and recognize patterns and subgoals, drastically cutting down on the amount of search.

Some Sokoban puzzles can be solved automatically by using a single-agent search algorithm, such as IDA*, enhanced by several techniques which make use of domain-specific knowledge.[10] This is the method used by Rolling Stone,[11] a Sokoban solver developed by the University of Alberta GAMES Group. The more complex Sokoban levels are, however, out of reach even for the best automated solvers.[12]

Link to comment
Share on other sites

So, I'm toying with the idea of having a functional 3-row "board" on the title screen, where there's a man and boxes and walls.... a specially designed "level" for selecting and starting the game. I have it nominally working, but I'm not quite sure if I'm going to keep it. Under the board would be a level selection ("LEVEL 99") type thing. And to start the game you'd probably push a box onto a green "start" button. Something like that. Not sure yet, but here's the concept... sure is colourful...
 

Screen Shot 2019-08-07 at 9.52.05 pm.png

  • Like 1
Link to comment
Share on other sites

On 8/6/2019 at 8:38 AM, Andrew Davie said:

This version is now format-switchable via the RIGHT DIFFICULTY SWITCH.  A is NTSC and B is PAL, I think. Additionally, the left difficulty will toggle between PAL50 and PAL60 if PAL is chosen with the right switch.  

Figured it might we worth mentioning that when playing this version on a Harmony Encore cartridge, the title screen works great and looks good.  However, once the fire button is pressed the game crashes.

 

 

Link to comment
Share on other sites

2 minutes ago, chad5200 said:

Figured it might we worth mentioning that when playing this version on a Harmony Encore cartridge, the title screen works great and looks good.  However, once the fire button is pressed the game crashes.

 

 


It seems that the Harmony Encore does not correctly implement the 3E bankswitching scheme.
I have no other explanation for why the game does not work on that hardware.
Thanks for the repot.

Link to comment
Share on other sites

8 hours ago, Andrew Davie said:

So, I'm toying with the idea of having a functional 3-row "board" on the title screen, where there's a man and boxes and walls.... a specially designed "level" for selecting and starting the game. I have it nominally working, but I'm not quite sure if I'm going to keep it. Under the board would be a level selection ("LEVEL 99") type thing. And to start the game you'd probably push a box onto a green "start" button. Something like that. Not sure yet, but here's the concept... sure is colourful...
 

Screen Shot 2019-08-07 at 9.52.05 pm.png

I would love a level selection/start screen.  This sounds really cool.:thumbsup:  Can't wait to see "the man". 

Link to comment
Share on other sites

19 hours ago, hizzy said:

Do you think you'll implement an actual character to push the boxes around? Sokoboo needs a mascot!

 

18 hours ago, Andrew Davie said:

 

Yes, that's the plan. There are some sample frames shown earlier in this thread.

 

I asked Andrew for a "sprite sheet" of sorts so that I can get started on that for him. It's a quirk of the way that I work, I need to be able to visualize the constraints/parameters that I am working under before I can optimize.

  • Like 1
Link to comment
Share on other sites

Can't stop fiddling. There are things I'm doing in the background but not ready yet. So, more title screen procrastinating.
I need to get the following working...

1) take-back

2) 'low score table' for each screen

3) selection of screen to play

4) indication if you beat the low score for a screen

5) savekey functionality

6) man animations

7) sounds, music updates

8 ) add more levels. Aiming for 256...?
9) end of level pizzaz


 

Screen Shot 2019-08-09 at 1.39.51 am.png

  • Like 3
Link to comment
Share on other sites

Here's a (hopefully) clean binary with the levels in the correct order. I thought I'd release this before embarking on the changes mentioned above.
I did find a few bugs related to character positions in RAM banks, and overflows... I don't think it caused crashes in any binaries I released, but it did cause crashes when I moved code around, and I couldn't understand why. Now fixed, so that's one less mystery.

sokoboo_20190809.bin

  • Like 2
  • Thanks 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...