Going great guns on a Prince of Persia port...

developing/porting a new game or gaming framework? post in here!
User avatar
Rich Talbot-Watkins
Posts: 2054
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: Starting a Prince of Persia port...

Post by Rich Talbot-Watkins »

I still feel like there should be no need for the double buffer. Even if the player plot is 140 scanlines, and the save/restore background 40 scanlines each, that still comes within the frame budget - so with raster timing so that you start the erase when the beam hits the screen block to restore gives you 312 scanlines to erase, plot the player, and plot the foreground. The flicker problem will always arise if there's too much time between erasing and replotting the player - I have no idea if this would require big code restructuring, but you should always be aiming for minimal time between those two.

I haven't considered other animated things going on so far (e.g. an opponent) or moving/falling scenery tiles. If no bounding boxes are overlapping, these could also be erased/replotted in quick succession, minimising the flicker some more. Overlapping moving graphics would be a tricky problem (would involve handling them as a single batch - erase all then replot all) but not impossible to do.

As long as the player looks nice, I personally wouldn't be offended by a bit of flicker elsewhere (we all played and enjoyed Chuckie Egg after all!).

So this is my suggestion I guess: secret option #3 - single buffered, rework the low-level rendering code. Not saying it's an easy option, but, until convinced otherwise, I wouldn't rule it out just yet. The advantage of PoP is that, for the most part, there's only one moving sprite, with entirely static scenery throughout. You could still avoid the foreground scenery overplot by treating pixel bit 3 as 'foreground' which the sprites don't overwrite - I'm presuming that'd save you another 40 scanlines too.
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

If there really is no way to make the code more compact and it really is only 2K you need, you could just shrink MODE 2 by a little instead of resorting to MODE 5? Shaving 32 pixels off the bottom would give you 2560 bytes. Or you could shave just 16 pixels and have 1280 bytes in each of main and shadow memory.

Alternatively, if I understand what you're up to properly, maybe you could use the whole of Hazel? You're not going to be double-buffering during disc accesses, so when you want to touch disc copy your code out of Hazel into the spare display buffer and re-initialise ADFS.

Of course, if you don't mind adding extra hardware such as a second processor, or a cartridge stuffed with RAM life becomes easy. Or, actually, more in the spirit of retro kit, ship the game as a sideways ROM that presents as one 16K bank but is actually much larger and pages bits of itself in and out as needed.
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

crj wrote:If there really is no way to make the code more compact and it really is only 2K you need, you could just shrink MODE 2 by a little instead of resorting to MODE 5? Shaving 32 pixels off the bottom would give you 2560 bytes. Or you could shave just 16 pixels and have 1280 bytes in each of main and shadow memory.
Unfortunately I need closer to 8K based on my estimations. There is around 2K sloshing about in the system but very hard to utilise as in small chunks spread across all the banks. It could be possible to shave a few columns off the left & right side of the screen to save a bit of RAM, although will add some complication to the clipping as the background plotting all assumes unclipped for speed (moving sprites would all be OK.) Ditto top & bottom - it's 192 lines across 3 corridors so 64 lines per corridor, so could shave a bit off the top/bottom or remap the data to be <64 lines.
crj wrote:Alternatively, if I understand what you're up to properly, maybe you could use the whole of Hazel? You're not going to be double-buffering during disc accesses, so when you want to touch disc copy your code out of Hazel into the spare display buffer and re-initialise ADFS.
It looks like on a Master pages &C000 & C100 of HAZEL contain the DFS catalog. As JGH noted page &C200 gets trashed by DFS during OSWORD &7F. It could be possible to use these 3x pages for data during level gameplay that isn't carried over between level load. Page &DF00 contains FS configuration so presuming (?) file loading will be unhappy if I trash this.
crj wrote:Of course, if you don't mind adding extra hardware such as a second processor, or a cartridge stuffed with RAM life becomes easy. Or, actually, more in the spirit of retro kit, ship the game as a sideways ROM that presents as one 16K bank but is actually much larger and pages bits of itself in and out as needed.
The C64 version did this, as I understand it. My goal is to create a single DFS floppy disc that runs on a vanilla BBC Master. I believe this is possible, just a question of feature tradeoff. :)
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

Rich Talbot-Watkins wrote:I still feel like there should be no need for the double buffer. Even if the player plot is 140 scanlines, and the save/restore background 40 scanlines each, that still comes within the frame budget - so with raster timing so that you start the erase when the beam hits the screen block to restore gives you 312 scanlines to erase, plot the player, and plot the foreground. The flicker problem will always arise if there's too much time between erasing and replotting the player - I have no idea if this would require big code restructuring, but you should always be aiming for minimal time between those two.
I have no doubt that you're right - it should be possible to make the player flicker free with raster timing and other tricks (like foreground bit 3) but all my investigations and experiments feel like I'm fighting the original architecture of the code, which is set up to be double buffered. The moment I turned it on was like a revelation - once I'd done the hard graft of refactoring memory usage it just worked and is pleasingly rock solid. I know I'm being mean as I haven't shared it yet for everyone to judge for themselves but I'm finding it hard to go back to any flicker after getting this far! (I still have a bug with the buffer swapping implementation as occasionally there is a small bit of tearing.)
Rich Talbot-Watkins wrote:I haven't considered other animated things going on so far (e.g. an opponent) or moving/falling scenery tiles. If no bounding boxes are overlapping, these could also be erased/replotted in quick succession, minimising the flicker some more. Overlapping moving graphics would be a tricky problem (would involve handling them as a single batch - erase all then replot all) but not impossible to do.

As long as the player looks nice, I personally wouldn't be offended by a bit of flicker elsewhere (we all played and enjoyed Chuckie Egg after all!).
Yeah, the player is definitely the most important thing on the screen, which is why I'm also loathed to reduce the resolution of the sprites. The draw loop is already sorted and batched into passes to avoid the overlapping sprites problem (which will occur whenever the player has a sword fight with a guard) so the big low-level rendering change would be to split this up to do localised batches, i.e. erase and redraw everything (in layers) affected by the region surrounding each animated object in turn, combining the regions together for overlapping sprites. I will continue to ponder this possibility but looking at how much there is still to port I'm finding it hard to continue down that path, being honest.
Rich Talbot-Watkins wrote:So this is my suggestion I guess: secret option #3 - single buffered, rework the low-level rendering code. Not saying it's an easy option, but, until convinced otherwise, I wouldn't rule it out just yet. The advantage of PoP is that, for the most part, there's only one moving sprite, with entirely static scenery throughout. You could still avoid the foreground scenery overplot by treating pixel bit 3 as 'foreground' which the sprites don't overwrite - I'm presuming that'd save you another 40 scanlines too.
Definitely not easy. :wink: It might have been easier to start with the PC rendering engine, if it wasn't in C, as the Apple II version has many quirks that are a consequence of the strange artefact colour hi-res mode. For instance the foreground components are drawn twice with the second layer being ORA'd on top of the first to alter the pixel parity. This doesn't make sense for MODE 2 but trying to surgically alter that part of the code has resulted in various unintended rendering artifacts whenever I've messed with it.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

kieranhj wrote:all my investigations and experiments feel like I'm fighting the original architecture of the code, which is set up to be double buffered
OK. Having put on my 8-bit Acorn hacker hat and suggested tricks for scavenging more RAM from the Master, I'll now take it off and instead put on my computer sciencist hat...

I've not seen this code, but I assume that there's a large pool of sprites to plot, and a relatively small number of routines which do that plotting. I also assume that the amount of foreground is a small proportion of the toal screen area.

If both those conditions are true, you could get sneaky. When plotting a sprite, don't actually write the data to screen memory. Instead, have two instances of a data structure that is:
  • A linear buffer of blocks (screen address+size+mask+data) to be written to the screen
  • A binary min-heap of pointers to those blocks, sorted by screen address
For each frame, do the following:
  • Perform all your sprite writes into the this-frame structure
  • Wait for Vsync
  • Commit the this-frame structure to screen in screen-address order.
  • As you commit each block, save the data you overwrite as a block in the next-frame structure
  • Swap which structure you're using as this-frame and which as next-frame
That should be a (very) efficient way to get a mixture of removing the previous frame's sprites and applying this frame's sorted into a flicker-free order. And the resulting data structure would probably be a lot smaller than a second bank of screen memory.

The commit routine would be the only thing that had to access screen memory. If you placed the structures in low memory, you could run most of the time with shadow memory in place, and code anywhere could add things to the this-frame structure.

If that basically worked but wasn't compact enough, you could finesse things:
  • Put the this-frame and next-frame heaps in the same block of memory, one ascending and the other descending.
  • Only store masks when necessary.
  • Directly refer to sprites rather than copying them into the buffer whenever they're suitably aligned and in appropriate memory.
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

crj wrote:OK. Having put on my 8-bit Acorn hacker hat and suggested tricks for scavenging more RAM from the Master, I'll now take it off and instead put on my computer sciencist hat...

I've not seen this code, but I assume that there's a large pool of sprites to plot, and a relatively small number of routines which do that plotting. I also assume that the amount of foreground is a small proportion of the toal screen area.

If both those conditions are true, you could get sneaky. When plotting a sprite, don't actually write the data to screen memory. Instead, have two instances of a data structure that is...
Hey crj, thank you for the suggestions. This is very interesting and could potentially lend itself to the way that PoP structures its drawing code anyway. Everything is placed into image (display) lists by the gameplay code as required then a separate rendering function (in a separate memory bank) performs the plot operations and is the only code that actually touches the screen memory. I will continue to ponder how this approach might fit in and help matters.

The challenge I have is that to reduce flicker I need to restore, store & plot the player (moving) sprites as quickly as possible, so in a localised manner, rather than doing everything in passes. To do this I would need to flag all plot operations that overlap the bounding box of the moving sprite - I do have the bounding information easily available. In order to keep the screen looking correct I still need to obey the plot operation order so - restore, wipes, background, store, moving (mid) sprites, foreground. This could be possible on a localised way but is more complicated (and lengthy) than just a restore, store, plot.

Lastly any overlapping moving sprites would have to be combined together into a single group - this happens regularly and I believe all the operations will take longer than a single frame to complete, bringing the flicker back.

E.g. player standing in front of a torch on the wall sword fighting a guard who is standing behind a pillar. (This happens on level 1.) The swords are both considered separate moving objects, believe it or not, so there would be 4x mid sprites all overlapping. To ensure all plotting happens correctly the order has to be: restore x4, plot background (torch frame), store + plot mid sprites left to right x4, plot foreground pillar.

The only way I see any of the single frame solutions coming close to working would be to not draw foreground sprites ever so would have to use the top-bit as foreground approach. I did investigate this previously but struggled to implement last time; I will take another look.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
tricky
Posts: 7713
Joined: Tue Jun 21, 2011 9:25 am
Contact:

Re: Starting a Prince of Persia port...

Post by tricky »

You and stardot got a mention on "The Retro Hour" podcast, they seemed very impressed that PoP could be done on a beeb and said that they should do more episodes on the beeb as it was such a big part of the UK retro computer history.
User avatar
sbadger
Posts: 499
Joined: Mon Mar 25, 2013 1:12 pm
Location: Farnham, Surrey
Contact:

Re: Starting a Prince of Persia port...

Post by sbadger »

tricky wrote:You and stardot got a mention on "The Retro Hour" podcast, they seemed very impressed that PoP could be done on a beeb and said that they should do more episodes on the beeb as it was such a big part of the UK retro computer history.
Not come across this before.. sounds good. What episode was the one you mention?
Thanks
So many projects, so little time...
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

kieranhj wrote:The challenge I have is that to reduce flicker I need to restore, store & plot the player (moving) sprites as quickly as possible, so in a localised manner, rather than doing everything in passes. To do this I would need to flag all plot operations that overlap the bounding box of the moving sprite
OK. Here's an alternative:

Allocate a bunch of 64-byte blocks. I'm not sure how many you'd need, but since you want to claw back 8Kbytes you'd probably be hoping to need less than about 10K's worth. The blocks must be at even addresses; putting them on 64-byte boundaries kinda makes sense, though. When I talk about a block address being "null", I mean the high byte is zero.

There are several kinds of block.

A free block is not currently in use. It simply contains a pointer to the next free block. (If the pointer is null, it's the last free block.)

A revert block represents a 32-byte fragment of screen memory which will need to be reverted to the background image during the next update. The first 32 bytes are the background data; the second 32 bytes are unused

A modify block represents a 32-byte fragment of screen memory which is to be changed. The first 32 bytes are the background data; the second 32 the data to be put there

A tree block represents a kilobyte of screen memory. It contains 32 entries, one for each 32 bytes of that kilobyte. (32*32=1024, of course.) The entry is:
  • Null: no block for this 32 bytes
  • Odd address: addr & ~1 is a revert block
  • Even address: a modify block
At the root, have a dedicated 60-byte structure. For each kilobyte of screen memory, have a count and an address. The count is the number of revert and/or modify blocks in that kilobyte, and address is a tree block if, and only if count>0. If count=0, the address is null.

So. You're preparing the next frame. If you want a byte to be written to screen memory at address addr next frame, do something like:

Code: Select all

ByteAddr getAddressOf(ScreenAddr addr) {
  k = addr>>1024; // Kilobyte
  f = (addr>>5)&0x1F; // Fragment
  b = addr & 0x1F; // Byte within fragment

  tBlock = rootNode[k].tBlock;
  if (!tBlock) {
    tBlock = getFreeBlock();
    fillWithZeros(tNode);
    rootNode[k].tNode = tNode;
    rootNode[k].count = 0;
  }

  mBlock = tBlock[f];
  if (!mBlock) {
    mBlock = getFreeBlock();
    ++rootNode[k].count;
    copyScreenToBackground(mBlock,k,f);
    mBlock ^= 1;
  }

  if (mBlock&1) {
    mBlock |= 1;
    copyBackgroundToForeground(mBlock);
    tBlock[f] = mBlock;
  }

  return mBlock[b];
}

Block getFreeBlock() {
  assert(first_free); // Otherwise, we're out of memory!
  result = first_free;
  free_head = result.next_free;
}
This could obviously be optimised when writing consecutive bytes by keeping hold of mBlock and tBlock and skipping a lot of checks. The amount of state you need to hold is small, so you could comfortably simultaneously keep state for writing to several adjacent rows of screen memory if that helped with sprite plotting. (NB: Every row would step into a new modify block simultaneously, but they'd step into new tree blocks at different positions.)

Having prepared a frame:

Code: Select all

function frameToScreen() {
  waitForVsync();
  for (k=0; k<20; ++k) {
    if (tBlock = rootNode[k].tBlock) {
      for (f=0; f<32; ++f) {
        if (block = tBlock[f]) {
          if (block&1) {
            rBlock = block & ~1;
            copyBackgroundToScreen(rBlock, k, f);
            releaseBlock(rBlock);
            tBlock[f] = NULL;
            if (--rootNode[k].count==0) {
              releaseBlock(tBlock);
              rootNode[k] = NULL;
            }
          } else {
            mBlock = block;
            copyForegroundToScreen(mBlock, k, f);
            mBlock |= 1;
          }
        }
      }
    }
  }
}

function releaseBlock(block) {
  block.next_free = first_free;
  first_free = block;
}
Note I've no idea if that can be represented efficiently enough in 6502 assembler, but I'm not seeing anything inherently tricky for an 8-bit CPU to do.
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

Note, incidentally, that this is almost equivalent to triple-buffering. At any given moment, you have access to what's on screen, the background without any foreground sprites, and what's going to be on screen next frame.
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

Hey all, quick update after ABUG. I promised to upload the latest WIP with double buffering so please enjoy the attached ssd or try:

https://bitshifters.github.io/jsbeeb/?d ... del=Master

I am still mulling over the rendering and memory options, so active code work has slowed to a crawl at the moment, but thank you to everyone particularly crj & RTW for their suggestions, input and helpful thought-provocation!

My gut instinct is that I do need / want to stick with double buffering the screen, I just need to find enough memory to do so. Tricky had a good suggestion at ABUG which I am exploring gently:

Separate the player sprites into 1bpp planes and only use 2 colours. A "large" one at the original sprite dimensions for the white pixels (~50% size give or take byte padding) and a second "small" one that is offset for the skin tone (currently magenta) pixels. Most of the time it's only the player's face & arms that require these pixels and it is a much smaller area. He is wearing "socks" it looks like but these could be removed or made black (transparent) during asset clean up. Given that the player sprites take up ~30K, provided the "small" sprite set takes up closer to 25% the total budget would give me ~7.5K back.

Obviously this complicates the sprite plot routine somewhat but this is very familiar territory for me to experiment with compared with completely rearchitecting the rendering loop to store everything in various alternative approaches to the second screen buffer. I will let you know the outcome of my ponderings.

Just to note - we verified at ABUG that the double-buffered POP will work on real Master hardware but it is only compatible with DFS because of my trampling of HAZEL RAM. It does not work with DataCentre et al. You will need to use an emulator or a real floppy!
Attachments
pop-beeb-level1-double-buffer.zip
Level 1 now with double buffered screen
(52.01 KiB) Downloaded 126 times
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
paulb
Posts: 1774
Joined: Mon Jan 20, 2014 9:02 pm
Contact:

Re: Starting a Prince of Persia port...

Post by paulb »

kieranhj wrote:Separate the player sprites into 1bpp planes and only use 2 colours. A "large" one at the original sprite dimensions for the white pixels (~50% size give or take byte padding) and a second "small" one that is offset for the skin tone (currently magenta) pixels.
This reminds me of the technique people would use, perhaps not that much in practice, when trying to get mileage out of character plotting using VDU 5. To get multicolour sprites, one would layer them in such a way. Obviously, no-one would do this as a form of optimisation, though, and most people seriously wanting to write a game would soon find themselves writing their own sprite routines, anyway.
User avatar
trixster
Posts: 1175
Joined: Wed May 06, 2015 12:45 pm
Location: York
Contact:

Re: Starting a Prince of Persia port...

Post by trixster »

This is just great! I can't wait to try it. Now I just need to work out how to get my datacentre to export to a floppy disk :lol:
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

trixster wrote:This is just great! I can't wait to try it. Now I just need to work out how to get my datacentre to export to a floppy disk :lol:
Easy! *IMPORT -D0 filename.ssd
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
pau1ie
Posts: 720
Joined: Thu May 10, 2012 10:48 pm
Location: Bedford
Contact:

Re: Starting a Prince of Persia port...

Post by pau1ie »

sbadger wrote:
tricky wrote:You and stardot got a mention on "The Retro Hour" podcast, they seemed very impressed that PoP could be done on a beeb and said that they should do more episodes on the beeb as it was such a big part of the UK retro computer history.
Not come across this before.. sounds good. What episode was the one you mention?
Thanks
Episode 95
User avatar
BigEd
Posts: 6277
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Starting a Prince of Persia port...

Post by BigEd »

(segment starts about 19min in)
User avatar
danielj
Posts: 9906
Joined: Thu Oct 02, 2008 5:51 pm
Location: Manchester
Contact:

Re: Starting a Prince of Persia port...

Post by danielj »

There seems to be some misapprehension that PoP was 16 bit first :)
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

Thanks for the podcast link - I love Romeo Knight's Amiga mod music! I've tweeted the guys so will see if they follow up.

I've been pondering the player sprite compression a bit more and decided to throw it open to you folks for suggestions (I may regret this :wink:)

It feels like it must be possible to get these compressed from 2bpp quite easily but there are some parameters to the challenge:

Code: Select all

All sprite widths multiple of 4 pixels
Worst case is 32 pixels wide = 8 bytes @ 2bpp
Tallest sprite is 57 pixels high
Largest single sprite is 287 bytes (28 x 41 pixels = 7 x 41 bytes)
Currently 2bpp = 4 colours (black/mask, white, orange, blue) but could be reduced to just white + orange + mask
Sprites have to be plotted at pixel alignment in MODE 2
Sprite plot requires a row of pixel data at a time
Sprite plot supports mirroring so ideally want to decode from either end (or can flip direction of stack read)
Sprite plot requires starting from any row due to clipping against top of screen
So my initial naive approach to use RLE spans of pixels didn't yield any significant savings. I also tried encoding the left/right hand black pixel lengths in one byte then the colour pixels as 2bpp but this yields no more than 10% saving across the whole set. I think the challenge is that compressing just a scanline at a time means there really aren't that many bytes to remove - most of them are only 3 - 4 bytes across - it's the height of the sprites that really adds up!

So let me know your crazy ideas, I will continue to try different approaches as well. I can also post the half-height sprites as pngs - not so bad looking after I improved the sampling used from the original Apple II data...
Attachments
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Player sprites MODE 5 res
Last edited by kieranhj on Wed Nov 22, 2017 7:13 pm, edited 1 time in total.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
Rich Talbot-Watkins
Posts: 2054
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: Starting a Prince of Persia port...

Post by Rich Talbot-Watkins »

Do you plot at any horizontal alignment, or is it always byte aligned? If the former, you could plot column-wise and run-length encode runs of zeroes in a given byte column. Top/bottom clipping would have to be handled specially, but that's normally a good idea anyway.

That looks like it would save quite a bit, given the sprite defs, but if you need to plot at any pixel position, you still need to store the sprite row at a time, so that wouldn't work.
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

Yes, sorry I should have added that to the requirements! All player sprites must be plotted pixel aligned and are pixel clipped against the left & right hand edge of the screen.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

Random thought: it looks like some of those sprites are part of animation sequences where there is one specific sprite they can follow?

If so, there might be mileage in taking the difference between consecutive sprites and run-length encoding that?
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

Hey folks, thought I would give you a quick lunchtime update. I have spent more time than is natural (or reasonable) thinking about compressing these flipping player sprites!

Because the player sprites only use two colours (white + orange) plus black (mask) there are MODE 5 pixel combinations that are invalid / unused (anything with a 4th colour.) I took a quick look at the pixel combinations that are used (and their frequency) and it ended up <68 across all four banks. It would only be a small amount of error to drop a couple of the least frequently used and get this down to 64 pixel bytes, which could be encoded as 6 bits. So we would have 4 pixels in 6 bits = 1.5bpp. In theory my 25% saving! (Not worrying about decode complexity.)

Unfortunately, in practice because we have to round up to 8 bits per byte the saving was substantially less - about 10% overall. Back to the drawing board. Turns out that the majority of player frames are 3 bytes wide = 21 pixels on Apple II = 12 pixels on Beeb. In order to make any meaningful saving (whilst keeping my horizontal data arrangement) these would have to all be crunched to 2 bytes / 12 pixels = 16 bits / 12 pixels = 1.3333bpp. Ouch! An approach I came up with was to use 4 bits to represent 3 pixels = 1x attribute bit + 3x pixel bits where the attribute defines whether the pixels are white or orange. The results don't look too bad and result in an overall saving of ~23%

I wasn't thrilled with having attributes (doesn't look very Beeb) and the art restrictions are a bit yucky (one colour per 3 pixels #-o) so before implementation I decided to chat to Dethmunk offline about the options. The good news is that he's agreed to redraw the sprites but we also decided that the simplest scheme was probably the best, so reduce the vertical resolution by half but keep the full 2bpp so we'll have an extra colour to help make up for it. I'll figure out a hack to keep the sword at original resolution because this does look a bit too crap.

In summary:
  • Tricky's 2x bit planes approach
    Potential saving ~= 4K
    Pros: keep original full resolution without data loss
    Cons: new 1bpp plot routine required, increased plot complexity (2 pass), slower plotting as have to overdraw, some authoring restrictions (orange in top half only)
    Highest quality, smallest saving

    "Attribute" mode
    Potential saving ~= 7K
    Pros: keep vertical & horizontal resolution
    Cons: some loss of data in horizontal resolution, fiddly authoring restrictions (white/orange in 3 pixel groups), new attribute plot routine required, artefacts not very beeb-like
    Medium quality, medium saving

    "Half height" sprites
    Potential saving ~= 14K
    Pros: keep existing plot routine, could have faster plotting (two scanlines together), full 3 colours available, square pixels, keep horizontal resolution
    Cons: reduced vertical resolution, looks very chunky, not competitive with other 8-bit versions?
    Lowest quality, highest saving
This is all still predicated on requiring double-buffering and that the only place to save sufficient memory is with the player sprites, of course. :)

I have spent a long time looking at this so feel I need to move forward with the port again. I still have to figure out how to use the freed up RAM as SWRAM banks are less convenient than SHADOW memory for this particular use case. I will give you an update when I get somewhere.

Here is a comparison of the various approaches:
  • 1. Apple II original sprites
    2. MODE 5 sprites
    3. "Attribute" sprites (autoconverted to prefer white)
    4. "Attribute" sprites (prefer orange - could still be artist tweaked)
    5. MODE 5 half vertical resolution
Different compression schemes for player sprites
Different compression schemes for player sprites
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
Matt Godbolt
Posts: 255
Joined: Mon Jul 31, 2006 11:02 am
Location: Chicago
Contact:

Re: Starting a Prince of Persia port...

Post by Matt Godbolt »

Just a flyby content-free post to say how much I'm enjoying reading this thread! Keep up the great work everyone!
crj
Posts: 858
Joined: Thu May 02, 2013 5:58 pm
Contact:

Re: Starting a Prince of Persia port...

Post by crj »

kieranhj wrote:Unfortunately, in practice because we have to round up to 8 bits per byte[...]
I don't see any reason that would necessarily be true? Other schemes might be a bit fiddly, but they're certainly possible.

And there's no rule that says you can't have data pertaining to more than one sprite in the same byte.
User avatar
sbadger
Posts: 499
Joined: Mon Mar 25, 2013 1:12 pm
Location: Farnham, Surrey
Contact:

Re: Starting a Prince of Persia port...

Post by sbadger »

my tuppence the MODE5 halfhight is a non-starter. Too high a cost on sprite quality
So many projects, so little time...
User avatar
tricky
Posts: 7713
Joined: Tue Jun 21, 2011 9:25 am
Contact:

Re: Starting a Prince of Persia port...

Post by tricky »

Did you try having a lut for scan lines?
Maybe have 0 for not indexed, followed by the usual data or indexed for the most common 255 scan lines?
I may try some other methods later.
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

tricky wrote:Did you try having a lut for scan lines?
Maybe have 0 for not indexed, followed by the usual data or indexed for the most common 255 scan lines?
I may try some other methods later.
That could be very interesting for the most common 3 byte wide case. Worth running the numbers for sure.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
kieranhj
Posts: 1103
Joined: Sat Sep 19, 2015 11:11 pm
Location: Farnham, Surrey, UK
Contact:

Re: Starting a Prince of Persia port...

Post by kieranhj »

sbadger wrote:my tuppence the MODE5 halfhight is a non-starter. Too high a cost on sprite quality
:D Too late now!

I’ve put this on a compile switch for a while to test out. I might post a build to see what people reckon.

The more I think about it though, the more scaleable it seems for now anyway. I can control which sprite banks are half height and will eventually need to be able to specify this on a per frame basis for the sword. This means depending on the overall RAM available at the end I can put the critical frames back up to full res and leave less frequently used / less important frames as half res, eg drinking a potion.
Bitshifters Collective | Retro Code & Demos for BBC Micro & Acorn computers | https://bitshifters.github.io/
User avatar
sbadger
Posts: 499
Joined: Mon Mar 25, 2013 1:12 pm
Location: Farnham, Surrey
Contact:

Re: Starting a Prince of Persia port...

Post by sbadger »

kieranhj wrote:
sbadger wrote:my tuppence the MODE5 halfhight is a non-starter. Too high a cost on sprite quality
:D Too late now!

I’ve put this on a compile switch for a while to test out. I might post a build to see what people reckon.

The more I think about it though, the more scaleable it seems for now anyway. I can control which sprite banks are half height and will eventually need to be able to specify this on a per frame basis for the sword. This means depending on the overall RAM available at the end I can put the critical frames back up to full res and leave less frequently used / less important frames as half res, eg drinking a potion.
I guess if you can apply it to only in-motion sprites and leave stationary ones full res it might be a good compromise?.
So many projects, so little time...
User avatar
Rich Talbot-Watkins
Posts: 2054
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: Starting a Prince of Persia port...

Post by Rich Talbot-Watkins »

My €0.02 - PoP is all about the character sprite and animation. It was pretty much the USP back in the day. It seems like a heinous crime to halve the vertical resolution (particularly since the horizontal resolution has already been compromised!). Have you thought about making different compromises, e.g. to the scenery graphics instead? Or indeed is there some way to compress those (particularly since they don't need to be plotted as part of the animation cycle if you use the pixel bit 3 as foreground flag thing). Would that claw back enough?
Post Reply

Return to “new projects in development: games”