The Southsider

I also do much of my initial coding on paper; at least the kernels and other complicated routines. I write stuff out longhand, though.

 

I think I think better when I do it that way; when I try to directly type a kernel into the computer, without notes, I tend to make (more) stupid mistakes.

Oh yeah. Paper and pen, though I'll sometimes bang stuff into NotePad or any other available text editor. Then for really tricky timing stuff I use a spreadsheet (1-2-3 or Excel) where each row is one CPU cycle. (Makes it easy to move stuff around.)

 

Right now I'm trying to restructure & optimize Leprechaun along with adding the scoring and giving movement options.

Hm... well I write everything on a computer. Actually, I think I even lost any handwriting skill already

 

The binary looks good. You didn't mention it in your post, Chris, but I assume you're aware of the vertical particle tearings?

 

Greetings,

Manueö

Juno4 does look really, really good. IMO, the HMOVE lines are not noticeable enough to worth worrying about.

 

On the other hand, do they look worse or better when everything is moving around?

The binary looks good. You didn't mention it in your post, Chris, but I assume you're aware of the vertical particle tearings?

Hmmm...just noticed that as well. Maybe not noticeable when they're moving?

Greetings,

Manueö

Name change? How do you pronounce that, anyway?

I type the more easy stuff directly into the computer, but when it gets complicated, I work a lot with paper (usually lying on the floor).

Ah - it is good to know that I am not the only one who still relies on pen and paper!

 

I am aware of the vertical tearing on the missiles, but I am not sure what to do about it There is only enough time within the kernel to draw either the grid lines, the repositioning lines, or the missiles. I made the missiles 2LK so that they don't disappear entirely, but this gives the tearing effect that you noticed. I am still hoping that this will not be very visible when the gridlines and missiles are moving in the actual game.

 

Chris

Juno4 does look really, really good. IMO, the HMOVE lines are not noticeable enough to worth worrying about.

On the other hand, do they look worse or better when everything is moving around?

 

Thanks - I haven't tried moving stuff around yet, but I am hoping that it will still look OK. The sprites will be flickering anyway, so I hope that the bars will go unnoticed.

 

Chris

Hi Chris!

 

I'm studying your source for some time now, and one thing I noticed is that you're creating an extra index of displayable sprites.

 

That seems to have advantages and disadvantages.

 

The advantage of course, inside the kernel you no longer need to check wether your sprite is displayable or not.

 

The disadvantage is that you loose cycles each time you need to access your data inside the kernel. You need extra RAM and a significant extra amount of time for creating the index.

 

One idea I had, was to store INVT, INVX, INVY immediately temporary, so that you only need to load once via index.

 

The second idea was that you not just DEC your INDEX, but *update* it. You just get the next INVS value and store that in INDEX.

 

That can either be via an extra counter, or by building your index table a little different:

 

Assume 4 sprites. Assume you want to draw 1, 4, 2 in that order.

Then create an index like

 

 

INVS = 1, 4, FF, FF, 2

 

Start with:

 

LDA INVS

STA INDEX

 

Then advance to the next sprite with:

LDX INDEX

BMI Done

LDA INVS,X

STA INDEX

Done

 

Still... I think doing without an index is always the better compromise. Especially in this case, when the Flickersort will have to swap all values anyway...

 

Hope you don't mind. Just food for thought to inspire you. Maybe it frees some cycles for the HMOVE or the particle thing

Hi Manuel,

 

Thanks for looking at my code - it is always useful to have an extra pair of eyes looking for optimisations. I hope my code didn't scar you too much, as things are rather messy in there at the moment I was originally planning to avoid the index by selecting the next sprite to display within the kernel (as you do in Colony 7). However, there were two main reasons that I decided against this:

1. The grid lines would have to avoid the lines where the next sprite is selected. You will have seen how difficult it was to do this already for the repositioning lines! Also, this would require more gaps between sprites, i.e. more flicker.
   
2. If I remember correctly from Colony 7, you are limited to 4 sprites in the same horizontal band. I though it would be difficult to ensure this in Juno First?
   

In the end, I decided that a separate index array was not too much of a disadvantage, and it makes the kernel a bit less complex. I always prefer to do things outside the kernel if possible. I haven't measured the cost in cycles yet, but there seems to be plenty of spare cycles remaining and I haven't started using the overscan region. Also, I suspect that it will be possible to combine the flicker sort and index creation, but I wanted to check that they worked properly first. Although the index requires more memory, this memory can be used for other things between frames (as the index is recreated on every frame), so this shouldn't be too much of a penalty either.

 

I like your suggestion for combining the index array and the index pointer - I would have never thought of that! At first I though this would require more memory, but then I saw the light I will try to implement this in the next version as it should save a few cycles and possibly allow me to avoid tearing on the missile sprites.

 

I'm not sure what you meant by the following. I don't see how you can load these immediately without using self modifying code, but I could be missing something?

 

One idea I had, was to store INVT, INVX, INVY immediately temporary, so that you only need to load once via index.

 

Many thanks for the suggestions!

 

Chris

Thanks for looking at my code - it is always useful to have an extra pair of eyes looking for optimisations.

 

It's an excellent way to *warm up* - so I'll be ready for C7 soon again

 

I hope my code didn't scar you too much, as things are rather messy in there at the moment

 

It's a whole lot more commented than most of my stuff, that surely helps. Also you do an incredible amount of accurate cycle counting, which looks a whole lot better than my usual try'n'error chaos

 

The grid lines would have to avoid the lines where the next sprite is selected. You will have seen how difficult it was to do this already for the repositioning lines! Also, this would require more gaps between sprites, i.e. more flicker.

 

That is true. It increases the virtual height of a sprite and you're forced to skip sprites that could've been drawn because they are detected too late, both of which increase the flicker. I improved this from Star Fire to C7.

 

In Star Fire I could test the next two sprites per 2LK iteration. In C7 it is granted that I find the next sprite within one single iteration. Of course C7 only tracks 5 objects at a time

 

If I remember correctly from Colony 7, you are limited to 4 sprites in the same horizontal band. I though it would be difficult to ensure this in Juno First?

 

No. I think you're mixing this up with either Leprechaun or one of Johns ideas he posted regarding Bobs Demon Attack experiments. My approach will secure equal distribution of on-time regardless of the number of sprites.

 

I haven't measured the cost in cycles yet, but there seems to be plenty of spare cycles remaining and I haven't started using the overscan region.

 

Like I told Bob, don't underestimate the object handler. It's an absolute killer task: Collision detection, movement, AI, spawning logic, etc. - for each object!

 

Also I'd estimate you'll need at least two more variables for each sprite. Hm... ok, then you'll also have to reduce the number of objects... always tricky to find the right balance

 

Also, I suspect that it will be possible to combine the flicker sort and index creation, but I wanted to check that they worked properly first.

 

That is a good idea!

 

I'm not sure what you meant by the following. I don't see how you can load these immediately without using self modifying code, but I could be missing something?

 

Oh, sorry, I should've given an example. I meant once you advance to the next sprite, you could possibly do something like this:

 

dec INDEX

ldy INDEX

ldx INVS,Y

lda INVY,X

sta TEMPY

lda INVX,X

sta TEMPX

lda INVT,X

sta TEMPT

 

So from then on you can access all data straight through TEMPY, TEMPX, TEMPT without having to deal with the index again until the next sprite is to be drawn.

I like your suggestion for combining the index array and the index pointer - I would have never thought of that! At first I though this would require more memory, but then I saw the light I will try to implement this in the next version as it should save a few cycles and possibly allow me to avoid tearing on the missile sprites.

 

It should use the same amount of RAM. I didn't tell you that in my example because I thought it might've been confusing, but of course INDEX may already be the first byte of INVS, as it doesn't matter if you overwrite it after the frst sprite is drawn.

 

Greetings,

Manuel

Like I told Bob, don't underestimate the object handler. It's an absolute killer task: Collision detection, movement, AI, spawning logic, etc. - for each object!

Agreed: And beware software collision (which, of course, is somewhat necessary for accurate collision handling when there is flickering)! Bounds-checking takes forever!

Bounds-checking takes forever!

 

Does it? I would think that if a list of objects sorted by Y size is available, it would only be necessary to check objects with overlapping Y coordinates (which should be fairly straightforward). Also, if no object is more than eight pixels wide, something like:

  tya  ; Assume one coordinate is held in Y
 sbc xcoords,x  ; Carry should be known (adjust next instruction if not set)
 adc #$07
 adc #$F0 ; Carry clear if collision

should indicate if the two x coordinates are within 7 of each other. If not, more detailed checking is not necessary. The code expects carry set, and leaves it set if there's no collision.

I remain unconvinced. You have to plan for the worst-case scenario; it is no good to say, "my display only rolls 5% of the time!"

Well, for one is a list of objects sorted with Flickersort never really sorted, and then it'd also depend on wether the actual bullets are done with the multiplexing engine as well or rather with particles.

 

Also, even this small snippet is 200 cycles already for 20 objects.

Thanks for all the comments. This is the first time that I have done sprite flickering, so it is good to hear from those with experience. You have now almost convinced me to remove the index, but there is one remaining issue that I am unsure about. Looking at the Colony 7 code, it appears that the selection of the next sprite to display is performed by the following code:

 

STA WSYNC
DEX
CMP ypos,X		 ; Check if sprite starts now
BCS Continue
DEX
CMP ypos,X		 ; Check if sprite starts now
BCS Continue
DEX
CMP ypos,X		 ; Check if sprite starts now
BCS Continue
DEX
CMP ypos,X		 ; Check if sprite starts now
BCS Continue
DEX
CMP ypos,X		 ; Check if sprite starts now
BCS Continue
DEX
Continue
TXA
BPL XFine
LDX #$00
XFine

 

The problem I see here is that this can only cope with 6 sprites within the same horizontal region? For example, if you have 8 sprites in the same region followed by some sprites in a lower region. The first pass through this code will select the first sprite from this list, and the second pass through will select the sixth sprite from the list (by default). However, as this region will have already been displayed on the screen, the sprites in the lower region will not be displayed, or am I misunderstanding the code?

 

Another issue that I am having with the flickersort routine concerns the movement of sprites. In Juno First, the sprites wrap-around so that when a sprite disappears off the top of the screen it reappears at the bottom (and vice versa). The problem with flickersort is that it assumes the sprites are roughly ordered within the list. However, this will not be the case when a sprite wraps around the screen, and it may take many passes through the flickersort code before the sprite is moved back to the correct position again. Putting the sprite directly in the correct position could require shifting all of the other sprites within the list (worst case), which doesn't seem like a good solution. Therefore, I think the only solution is to use a circular buffer, with a movable pointer to the beginning of the list, though this will porbably mean that I can only have a maximum of 16 sprites or the calculations will get awkward? Has anyone found a better solution to this problem?

 

Thanks,

Chris

Looking at the Colony 7 code, it appears that the selection of the next sprite to display is performed by the following code

 

Yup, that's it. It's a very brute force approach as I have a very special case here, with the engine only tracking 6 objects.

 

The problem I see here is that this can only cope with 6 sprites within the same horizontal region? For example, if you have 8 sprites in the same region followed by some sprites in a lower region. The first pass through this code will select the first sprite from this list, and the second pass through will select the sixth sprite from the list (by default). However, as this region will have already been displayed on the screen, the sprites in the lower region will not be displayed, or am I misunderstanding the code?

 

Well, in this special case, you're absolutely right. (Only difference is that the first pass is already done outside the kernel.)

 

But some things to consider:

 

- Is 6 sprites in a row really a desired state of the game engine? It should be absolute worst case, and you'll rather want to avoid that by movement schemes / AI.

- supercat posted some very tricky improvement of the code somewhere, resolving the worst case somewhat, so it might be able to perform 7, 8 or more checks in the same time. (I'd estimate in the end your engine will be able to run 8-12 sprites at max, depending on the time your object handler consumes)

- After some 4,5,6 skips you could check wether you already found a displayable sprite - and if not, you run a second iteration of the scanning code.

 

Another issue that I am having with the flickersort routine concerns the movement of sprites. In Juno First, the sprites wrap-around so that when a sprite disappears off the top of the screen it reappears at the bottom (and vice versa). The problem with flickersort is that it assumes the sprites are roughly ordered within the list. However, this will not be the case when a sprite wraps around the screen, and it may take many passes through the flickersort code before the sprite is moved back to the correct position again. Putting the sprite directly in the correct position could require shifting all of the other sprites within the list (worst case), which doesn't seem like a good solution. Therefore, I think the only solution is to use a circular buffer, with a movable pointer to the beginning of the list, though this will porbably mean that I can only have a maximum of 16 sprites or the calculations will get awkward? Has anyone found a better solution to this problem?

 

The two options you found sound both very good to me.

 

I sort of have a third in Star Fire, but I'm not sure if/how it's applicable here:

 

Since the absolute vertical region is a lot bigger than the visual region, I always spawn ships in *behind* the player. So by the time you manage to scroll them into the visible area, they've already been sorted into place

The problem I see here is that this can only cope with 6 sprites within the same horizontal region? For example, if you have 8 sprites in the same region followed by some sprites in a lower region. The first pass through this code will select the first sprite from this list, and the second pass through will select the sixth sprite from the list (by default). However, as this region will have already been displayed on the screen, the sprites in the lower region will not be displayed, or am I misunderstanding the code?

An alternative is what I did in my Metroid kernel (source is on [stella], here's the relevant snip):

   tya
  ldx EnemyIndex
  cmp EnemyY,X;+9   30
  beq AssignEnemyKernel;+2   32 (33)
  bcs EnemyIndexOk1;+2   34
  dex
  bpl EnemyIndexOk2;+4   38
  inx
  nop		;+4   42
ReturnFromEnemyIndexOk1
  stx EnemyIndex;+3   45

I don't have an entire scanline to devote to setting up the index for the next sprite (as I'm also drawing an asym playfield every other line and P0 every line), so I do it on the fly.

Y here is the scanline counter.

 

The problem here is that I can only adjust my index by one in every pass through the loop, so bunched up sprites might not flicker appropriately. But, on the other hand, it works for any number of sprites and doesn't require a free scanline.

 

EDIT:

Another issue that I am having with the flickersort routine concerns the movement of sprites. In Juno First, the sprites wrap-around so that when a sprite disappears off the top of the screen it reappears at the bottom (and vice versa). The problem with flickersort is that it assumes the sprites are roughly ordered within the list. However, this will not be the case when a sprite wraps around the screen, and it may take many passes through the flickersort code before the sprite is moved back to the correct position again. Putting the sprite directly in the correct position could require shifting all of the other sprites within the list (worst case), which doesn't seem like a good solution.

Just remembered that I dealt with a similar problem in my two-sprite multiplex efforts.

 

My partial solution was this:

I had a sprite list of 20 items.

Generally, the whole thing wasn't filled. The open spots were marked as "open" by having a Y value of zero or 255 (neither of which would display on the screen and which wouldn't interfere, when sorting, with visible sprites).

So then, when I added a sprite to the top of the screen I looked first for an open slot in the sprite list that had a Y value of 255, since that would be presorted to the top of the list. If I added a sprite to the bottom of the list I looked first for an open slot with a Y value of zero, since that would be presorted to the bottom of the list.

 

When a sprite was removed from the display, I changed its Y value to either zero or 255, alternating.

 

That make sense? Because I had so many objects, and so much flicker, already, it was hard to tell if it made any kind of improvement to the flicker, though I think it did.

 

So, for your case, if there is an "open" slot at the bottom of your sprite list when a sprite goes off the top of the screen, you could reassign it to the that open slot. This won't work if all the slots are full, obviously.