Sunday, July 25, 2010

Three Laws of Robotics

  1. A robot may not injure a human being or, through inaction, allow a human being to come to harm.
  2. A robot must obey any orders given to it by human beings, except where such orders would conflict with the First Law.
  3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.

It's clear that droids in Paradroid violate the first two laws, but that doesn't mean that they have to violate the third law as well. After all, Elvex dreamt of world without the first two laws.

So... why would a droid with any brains rush straight into explosion it surely knows will harm it? The most common situation where you see that happening is when a high-speed droid (like 834) shoots a low level droid in front of it and then runs (or flies, 834 is an anti-grav droid) into the explosion, destroying itself. I see no reason for that, so the droid must stop. The fastest way for detecting this was to give every patrol route segment an unique number and update droid info when it leaves a waypoint. When droid is destroyed its type is changed to explosion, but most of other attributes remain. That means that when checking for future collisions I can discard most of the droids/explosions by checking the route number only. That still leaves collisions on or near waypoints, but I have to start somewhere (and I hope I can forget more exact check later ;)

There are 433 waypoint exit directions in total so it was more efficient to write a subroutine to enumerate all routes on fly than including them in the data. That routine is less than 130 bytes long, static data plus depacking code would be at least twice the size. I also needed one 256-byte table to be able to look up the route number fast; 32 waypoints with 8 possible directions form an 8-bit index into that table. I can update route number with "lda waypoint_num; asl; asl; asl; ora dir; tay; lda routes,y; sta droidRoute,x" (that happens only when droid leaves waypoint) and check for impending collisions with "lda droidRoute,x; cmp droidRoute,y" - only if routes match I need to check for the distance between two objects. Nice and fast, now I need to play some games to check if I can see the difference.

Later I can use the same data to check if another droid is in a security droid's way, and if that's the case the security droids may decide to destroy a low-level droid to serve a greater good - to protect the ship.

A robot will guard its own existence with lethal antipersonnel weaponry, because a robot is bloody expensive.
- David Langford

Sunday, July 18, 2010

Not dead yet, part 2

It may have taken two years, but here is the newest and greatest version!

Both original and Metal Edition graphics are now in the same executable, droids have slightly modified AI, high score saving should work with most common expansions (you may have to disable your disk speeder cartridge though) and there is a new frontend. Can you name all the games from where I borrowed something?

Some minor changes including but not limited to

  • orange/red alert increases enemy fire probability half/full ship
  • competition mode - same droids every time, has separate high score file
  • no pacifist bonus if disruptor used
  • droid centered on lift when deck changes - no more exit through wall

File update: two bugfixes to eliminate crash on startup (hopefully one of them does the trick), one minor visual fix and adding disruptor to firing statistics. No more easy accuracy bonus by using 711/742 only!

Friday, January 1, 2010

Crash Boom Bang!

Ever tried disrupting the last droid on ship to smithereens and entering lift when the explosion was still going on? Not? Good. That would have crashed the game right there. Very annoying, especially if you had just quadrupled your all time high score...

What are the changes of someone completing a ship and entering lift before deck is shut down? I don't know, but I managed to do so! Then I reproduced it on purpose to make sure there is a bug. Now I have to hunt it down.

Edit: Found it! It's the same bug which causes "pacifist takeover" (not shooting any droids - except with disruptor!) crash randomly at the same point. In Time is of the Essence I gave you the code for play are top split. In Irq_118() I use this to stabilize raster regardless of how many sprites are over the split:

lda $dc04 ; [1,15] ([2,15] if NTSC/Drean)
eor #$0f ; [14,0] ([13,0])
sta .j3+1
.j3 bpl *+2 ; jump into the delay code
; entering at offset 0 delays 16 cycles,
; entering at offset 14 delays 2 cycles
; OP_CMP_IMM is opcode for CMP #immediate (2 cycles),
; OP_CMP_ZP is opcode for COM $zeropage (3 cycles)
cmp #OP_CMP_ZP

Guess what happens if CIA timer underflows before the interrupt code is executed? It will jump randomly forward and CPU ends in la-la land. Unfortunately there is some code which needs to be run with interrupts disabled, and if top split is delayed because of it... BOOM!

The solution? I can use software semaphore to protect shared resources and avoif disabling interrupts. Nice and clean solution, but why should I do that when I can kludge around the problem by waiting for raster position after the split before disabling IRQ... "bit $d012; bpl *-3; sei" fixes the bug.

Wednesday, December 30, 2009

NTSC Blues

Why didn't anyone remind me that it would be nice if the new front-end worked on NTSC as well...

Answers on a postcard, please.

Sunday, July 6, 2008

Time is of the Essence

After reading about Mike Dailly's raster split trouble I decided to write a bit about how the top split is done in Paradroid Redux.

There are three things to do when playing area begins:

  • change background color
  • start character display
  • start sprite display
The first one is just $d021 change, other two require a bit of trickery.

To mask vertically scrolling characters one would usually use illegal graphics mode (Extended Color Mode comined with Bit Map Mode and/or Multi Color Mode) or sprites. The first method produces black pixels so it isn't usable unless background is black, and the second one is unusable if sprites need to cross the split.

So, it's time for some font trickery. Raster interrupt several lines above the split changes to blank font, and then the actual split interrupt changes $D018 to display correct character data. This means "wasting" $0800 bytes for the blank font, but half of that memory is used as temporary buffer elsewhere so actual cost of clean split is one kilobyte.

Clipping sprites cleanly requires trickery as well as there is no way to start sprite display from the middle of graphic data. One way to achieve clipping is clearing top of sprite graphics if it overflows top split, but that would waste time both when clearing the memory and when running extra animator/digit generator rounds to restore top of sprite when more of it gets shown. Another way to achieve clipping is to put sprite at non-visible x-coordinate and then change them at the correct line. However, there is no time to change multiple registers in time.

Guess what? $D018 comes to rescue once again. There is an extra screen where the sprite pointers point to blank sprites. When the time comes, split interrupt doesn't only change font (bits 1-3 of $D018) but also displayed screen (bits 4-7 of $D018). Nice and easy solution but it requires a blank screen, another one kilobyte wasted. No, not really - there is no reason why one half of the blank font couldn't be used for blank screen. What that means is that sprite clipping is practically free as there is no extra memory required and $D018 needs to be written anyway for character blanking.

There is one problem with the screen change though. While VIC-II reads font data and sprite pointers & sprite data every line, character pointers (screen data) are only read on every eighth line. This means that while sprite and font changes are immediate, screen change affects display 0-7 lines later. To overcome this the top line of playing area is copied onto blank screen so character pointers are correct when $D018 is changed.

As blank screen is located inside blank font this copying creates yet another problem. Blank font isn't that blank any more. The topmost line is at SCREEN + $140, which means that chars $28-$2c aren't blank and will produce garbage if they appear on the topmost line. The easiest way to avoid that is to not use those chars inside playing area at all, so that's what is done. The same problem happens because of blank sprite pointers at SCREEN + $3F8, char $7F. That one is unused as well.

And what does all this has to do with timing problems Mike mentioned?

VIC-II doesn't have time to fetch sprite data when CPU is not using memory bus, so it has to stop CPU momentarily whenever sprites are active. Just how many cycles VIC-II steals from CPU depends on which sprites are active, and this causes a timing hell as you have to change registers when C64 is inside the side border area to avoid flicker. With $D021 change you have all the side border (23 cycles) to change it, but $D018 is trickier. Sprite data is fetched very early, the first three sprites get their data read at the end of previous line. This means that if $D018 write is late sprites will stay blank for one extra line.

To get register writes done at the very beginning of side border area the game uses CIA timer to stabilize raster timing. During game init CIA1 timer A is started, running through 63-65 cycles depending on VIC-II version. This means that $DC04 is always synchronized with current display X position. IRQ only needs to read $DC04 and skip that many cycles.

Did I forget bad lines? Every eight line VIC-II needs to read character pointers and that's not possible without stopping CPU for most of the raster line. This means that there is absolutely no time for anything unnecessary. In the case the split happens on a bad line the game triggers raster IRQ two lines above split, prepares next interrupt at the correct line and then preloads $D018/$D021 values and executes two-cycle instructions until IRQ happens. That guarantees minimum interrupt latency. When raster interrupt happens it will just write those two registers, clean up the stack (this second interrupt pushed status register and return address into stack) and jumps into the common code.

Nothing explains code better than source, so here it is. Only relevant parts are shown, and for clarity I've removed all assembly directives which were there to make sure branches don't span page boundaries (which would add one cycle to the branch).

       IRQ at line 95, prepare for split
lda #$10
ora _vScroll
sta $d011
cmp #$16
bne .057
; special case for bad line

lda #<Irq_116
sta $fffe
lda _d018+1
sta _d018b+1
lda _d021+1
sta _d021b+1
lda #116
bne .x1 ; jmp
; normal case
.057 lda #<Irq_118
sta $fffe
lda #118
.x1 sta $d012
; this one used when ($d011 & 7) = 6, stuffs
; d018/d021 as fast as possible at raster 118
Irq_116 pha
sty .yr+1
lda #<Irq_118b
sta $fffe
lda #>Irq_118b
sta $ffff
lda #118
sta $d012
inc $d019
; 118/15 = 7.8 so this one is executed 8 times
sbc #15
bcs *-2 ; 8*5-1=39 cycles
; preload registers and execute 2-cycle
; instuctions until next IRQ happens
_d018b lda #scr_GAME
_d021b ldy #0
repeat 16
cli ; 32 cycles wasted
; now is the time to write registers, we always enter
; via interrupt as the above code never runs this far
sta $d018
sty $d021
; clean up stack and continue normal IRQ code
pla ; flags
pla ; PC lo
pla ; PC hi, always != 0
bne .irq0 ; jmp
; normal case, use timer value to stabilize
; raster regardless of sprites over the split
sty .yr+1
lda $dc04 ; [1,15] ([2,15] if NTSC/Drean)
eor #$0f ; [14,0] ([13,0])
sta .j3+1
.j3 bpl *+2 ; jump into the delay code
; entering at offset 0 delays 16 cycles,
; entering at offset 14 delays 2 cycles
; OP_CMP_IMM is opcode for CMP #immediate (2 cycles),
; OP_CMP_ZP is opcode for COM $zeropage (3 cycles)
cmp #OP_CMP_ZP
_d021 ldy #0
_d018 lda #scr_GAME
sta $d018
sty $d021
; continue with interrupt
.irq0 ...

Monday, June 23, 2008

Have a nice summer solstice(ish)

To honor the sun I give you a new release - or two releases actually.

My plan was to build an unified version with both graphic sets held in memory all the time, but that didn't happen due lack of memory. Too bad, having different graphics on different decks would have given some more variety to the game.

I did manage to fit all necessary data into memory, but as I had to
EOR fonts together there was no way to swap between them without temporary 2 KB buffer. You really can't unpack LZ data and EOR it simultaneously, which took me way too long to realize.

While it would have been possible to do the EOR in two passes with the 1 KB buffer I do have, I didn't bother with that as I would have to drop dual graphics as soon as I need the memory back anyway.

Oh, I did fix one single pixel bug in the hires font too :)

Edit: I also added single pixel bug into Metal Edition - when you clear deck the first time, there may be extra pixel in the background star. That one is gone as soon as you move a bit vertically, so I won't do another build just to fix it.

Sunday, April 20, 2008

Not quite dead yet

Here is little something for you who fear that the project is dead. Not much have changed though:
  • Subgame should now take 10 seconds regardless whether you're playing on C64 or C128. That's still slightly longer than original, but way better than 12 seconds.

  • Game should finally be Drean 64 compatible. I thought I put the code for this into the game 18 months ago, but apparently I didn't. Well, who's going to send me a Drean 64/128 so I can actually test it?

  • Most likely there are some other changes too, it was six weeks ago when I last touched the source. The only reason I did it now was to fix the download link.
Note: if you for some reason want to archive every single release, then do yourself a favor. Don't use build number as filename part! It was never meant for that. Instead, parse it as BB-DDMMYY where BB is daily build count, DD is day of month, MM is month and YY is year. Then reorder these as YYMMDDBB and when using that as part of filename you get chronologically sorted list.

Edit: Drean compatibility is now confirmed, thanks to the_woz. Check out his blog, especially Drean-specific entries.