Jump to content

The Southsider

  • entries
    81
  • comments
    767
  • views
    135,961

Programming on Paper

Sign in to follow this  
cd-w

546 views

I have always preferred programming on paper for some reason. I think this is because I didn't have a computer at home when I first learned to program. The only computer available to me for a long time was in my school, and its usage was strictly controlled and very limited. As a result, I used to write out my programs by hand in exercise books, and spend my precious computer time typing-in these listings and attempting to debug them. At the end of the session, I would print out what I had done and then spend the time away from the computer working out the bugs. These programs seldom worked, but they were a great learning experience.

 

This is still the way that I prefer to work, though I don't generally write out the initial program listings by hand anymore. Instead, I type up a rough version of the code directly onto the computer, and print out a copy that I then study for optimisations and bugs. I think the main problem that I have with programming directly onto the computer is that you only get to see a small part of the code at once. With paper, you can spread out all of the different parts on your desk and get a real picture of how it all fits together. There are various IDEs and folding editors that attempt to address this problem, but I prefer to use a standard text editor (xemacs) and printer paper.

 

The best kind of paper listings were the old fanfold kind, where each listing was essentially a continuous sheet of paper. You could spead it out on the floor and follow the control flow up and down the paper. When I first started at University, the lab had an old chain printer which printed out listings on 160-column fanfold paper. Actually I think it was a dot-matrix printer, but it was still called a chain printer as this is what it had replaced. This printer was managed by a supervisor who would put each listing into a pidgeon hole for later collection. The advantage of the 160 column format was that you had a huge amount of space next to your listings in which to make notes, draw diagrams, and document your code. Unfortunately this printer and the supervisor were replaced by a laser printer around 10 years ago now. I still think that I would be a better programmer if I had this printer, but these days I make do with 2-up laser printed listings.

 

post-3154-1087269301_thumb.jpg

 

The point of this nostalgic trip is that for the last week or so I have been carrying around a listing of my Juno First kernel. Every time I have had a few spare minutes, usually on the bus or train, I have taken out the latest listing and started tightening the code. Occasionally I will spot a neat trick, or solve a difficult timing problem, which generally causes a big smile to appear on my face, and probably causes those around to question my sanity! At times like this my girlfriend usually makes comments about geeks and the reason they have trouble finding women :)

 

Anyway, I think that the Juno First Kernel is now nearly complete, though obviously this is just the first step of the game itself. The latest version is attached to this message (the source code is in the ZIP archive). This code fixes many of the bugs in the previous version, and includes a variant of Manuels flickersort routine for displaying multiple sprites within the same horizontal region. The flicker will be much less noticable in the actual game as the sprites will be moving and should only occasionally overlap. Also, it will look better on an actual TV (use the phosphor option in Z26 or Stella to see this). The alien sprites do not move yet, but this is my next task. I still haven't come up with a solution to the HMOVE problem outlined previously, though I might just live with the lines as they are not too distracting. Overall I am very pleased with the way that the game is turning out so far ...

 

Chris

Sign in to follow this  


20 Comments


Recommended Comments

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

 

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.

Share this comment


Link to comment

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.

Share this comment


Link to comment

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

 

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ö

Share this comment


Link to comment

Juno4 does look really, really good. :thumbsup: 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?

Share this comment


Link to comment
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? :thumbsup:

Share this comment


Link to comment

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).

Share this comment


Link to comment

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 :thumbsup: 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

Share this comment


Link to comment

Juno4 does look really, really good. :thumbsup: 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

Share this comment


Link to comment

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... 8)

 

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

Share this comment


Link to comment

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 :thumbsup: 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 8) 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

Share this comment


Link to comment
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 :D

 

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

 

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 8)

 

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 :D

 

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 :thumbsup:

 

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.

Share this comment


Link to comment
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 :thumbsup: 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

Share this comment


Link to comment
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!

Share this comment


Link to comment
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.

Share this comment


Link to comment

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!"

Share this comment


Link to comment

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.

Share this comment


Link to comment

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

Share this comment


Link to comment
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 :thumbsup:

Share this comment


Link to comment
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.

Share this comment


Link to comment
Guest
Add a comment...

×   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...