Fast Line Drawing

[peteym5]

I have been looking at many video games on the Atari 8-Bit that require line drawing and I made a game that requires Line Drawing. Here I am releasing several theories of how to speed things up. Now these routines are tailored specifically for Graphics 31 [15 without the window]. This is a favorite among many Atari programmers because it offers 4 screen colors at the highest resolution possible.They already use less CPU cycles compared to the OS line drawing routines because those are ROM based, have to work in different screen dimensions and bit depths. With Ram based routines, addresses, immediate numbers, and OP codes can be changed which we call Self Modifying Code.

 

It uses tables for every column and row on the screen. Quickly convert the the X position to which byte, get the address of each line, translate the 2 bit nibble. Makes it significantly faster than trying to multiple, add, subtract, use a series of LSRs, to get the screen memory position. Saves some CPU time. The other thing done was keep the X position in the X register, so it only needs to do INX or DEX, this gets modified if going left or right.

 

There are two sets of loops depending on if it is a wide slope or tall slope. Angles ratio less than, equal or greater than 1:1. I know I could do many more loops for even slope, vertical, or horizontal. But the games we intend to use them for use lines of all angles. Plus many programmers don't like to waist more RAM than what is necessary.

 

Slopes are tracked with a series of SEC, SBC, BCS, ADC, instructions. We will call it the slope math. For example on a wide slope, tracks go so many pixels Left, Right, before needing to go up or down one. Something I did was put a SEC before the beginning of the loop, and only reset it when going up or down one. Saves 2 CPU cycles.

 

Some of the more advance work I have done is 2 instances and 4 instance within the loop. Draw 2 or 4 parts of the line per each cycle of the loop. Cuts down the number of times needing to branch and do that slope math. For 2 instance, divide the length by 2. I discovered it takes less CPU to figure by starting in the middle of draw out to the ends. A second theory put to practice is start at one end + middle and clone the slope. 4 instance just divides the length by 4. One issue I am having is sometimes the 4 instance does leave gaps or doesn't slope perfectly.

 

One other advance theory I started to play with for the 'slope math' was do a DEC zero page instead of subtracting, and resetting when it reaches 0. But this does requires division and trying to do division in 6502 code can take up more CPU than what can be saved. I am trying to track down a short table driven division routine. Bottom line is I had trouble getting it to work.

 

I know a few probably want something for graphics 8 / 24 screens, 2 bit per pixel or VBXE. But I am just covering 15/31 for now because many like to see colorful games.

LineDraw.zip

[w1k]

we have MADS from 1.1.13

[+JAC!]

Nice idea of adding some minor "inaccurary" of the "divide by 2" to gain speed, really good for games. Could you add a list of the 10 different versions/stages and what special for them?

[peteym5]

Yeah sorry about that.

 

Line Draw 0 and 1 are basically the same routine, just using some different memory locations.

 

LineDraw2 is the first try at processing 2 points within the loop, starting at the center and going to sides. Needs 2 zero page locations to track the X coordinates.

 

LineDraw4 is the first try drawing 4 points within the loop. Needs 4 zero page locations to track the X coordinates.

 

LineDraw5 is a clone of 1, was playing with some different ideals.

 

LineDraw6 processes 2 points in the loop. Divides the line length by 2, cloning the slope from the center. X coordinate stays within the X register. The offset for the 2nd point is pre-calculated before the loop.

 

LineDraw8 processes 4 points in the loop. Divides the line length by 4, cloning the slope in 4 quarters. X coordinate stays within the X register. The offset for the 2nd, 3rd, and 4th point is pre-calculated before the loop.

 

You see LineDraw7 which was my attempt to use a single INC for the slope math, but ran into issues.

 

One of my thoughts is make another Star Wars arcade clone. Would probably disassemble the 2nd one done by Domark and hack it. The frame rate sucked and why did they use a graphics 7 [23] style mode. Replace the line drawing routines. Do the X-Wing graphics with some screen graphics, rectangle copy routine. I kinda like the color scheme of the Atari version. Add in a player / missile graphic sprite multiplexer and use the players for the enemy bullets like the Atari version. So my approach be somewhere between the 2 of them. However this is something I wouldn't do by myself. its certainly a group project.

 

Think of any other game designs can benefit from my routines?

[phaeron]

I spent a lot of time analyzing the OS line draw routine, based on its interface and documented variables, when rewriting it from scratch for my own OS. It does have significant overhead from having to handle many graphics modes and not being able to use self-modifying code, but ultimately the reason why it is so slow is that it is based on a general putpixel(x,y) routine instead of incrementally stepping the plot parameters. Also, for some reason it maintains two 16-bit accumulators instead of one, and it unnecessarily uses variables in page two instead of making better use of ones in page zero. By avoiding these problems I managed to write a new line draw routine that is several times faster than the OS one in about the same amount of code space. Even so, needing to support 16-bit X coordinates for Gr.8 imposes a heavy cost which you were able to avoid.

[peteym5]

Something I was hoping to do by posting these routines online is to work with other programmers and see if we can come up with ways to make them run even faster or with less CPU cycle cost. I know this may bring some arcade game ports into reach on the 8-bit.

 

When I did Tempest Xtreem, we decided not to do that web zooming effect between the levels, but did the ship going down the web, getting smaller. Had a problem doing lane highlighting also. But I had been playing with the routine since then. A second version of Tempest is being considered and developed. Maybe have some extra graphics effects within it.

 

I also like the game OMEGA RACE. There is a Commodore Vic-20, 64, and an arcade game versions of it. Atari 8-bit can easily handle a similar type game at the Machine Language Level. Won't do it with all line drawing. I also played with Sprite multiplexer routines.

[Heaven/TQA]

pssst... Omega Race ist still on my VIC2A8 porting list

[Heaven/TQA]

but Omega Race does not have "vector" gfx or my memories fool me. Or do you mean "Black Hole" by Tom Griner?

[ilmenit]

I wonder if it would be fast enough for and adventure game with "vector" graphics like in Another World.

[peteym5]

but Omega Race does not have "vector" gfx or my memories fool me. Or do you mean "Black Hole" by Tom Griner?

 

I believe the Arcade version of Omega Race was vector graphics. But it does it with a lot of vertical and horizontal only lines. It may be better to do it with soft sprite and player / missile multiplexer routines also. Not sure what the screen resolution of the Vic-20 version was, but looks very close to 160 wide pixel mode. Could actually make it more colorful. But that depends on how faithful you want to be to the original game. I usually would have options at the title screen to be able to play Arcade or Enhanced modes. The Commodore 64 version uses 320x200 mode and probably be a more accurate model of porting to the Atari. However, my routines only work with 8 bit x coordinate system. I have not spent a lot of time playing with 320 wide pixel mode.

 

Does bring up another point. These routines can be modified to work with Atari wide screen modes of 192 pixel mode, wider if you want to use horizontal scrolling and set the address of each line.

[Heaven/TQA]

i think... A8 could help here:

 

[peteym5]

i think... A8 could help here:

 

http://www.youtube.com/watch?v=RaY_SjEHLDc

 

I certainly think it can do a game like that. With help from using Player / Missile graphics plus my line drawing routine, can keep animation at 30 frames / sec. Isn't there a similar game on the 2600 called Space War? Going to see if there is an Arcade game and if I have it in my MAME collection.

[sack-c0s]

The C64-land trick is to acknowledge that drawing out the vector objects is slow and separate out what is happening into rotations (which need the object redrawing) and translation (where you can more or less just move what you've already drawn).

You have the main loop going flat-out trying to rotate and render the objects as fast as it realistically can to sprites and have an interrupt routine that moves them on the screen so even if the object update isn't really 25 or 50FPS it gives the illusion that the framerate is higher than it really is and keeps it smooth for the player/viewer.

 

Might be a bit trickier on the Atari with the PMG sprite setup, but maybe there's some way of making it work in a usable way?

[kenjennings]

but Omega Race does not have "vector" gfx or my memories fool me. Or do you mean "Black Hole" by Tom Griner?

 

If this is the Omega Race we're talking about -> http://www.youtube.com/watch?v=cDfSOU-ZaHI

Yes, the original arcade version used a vector display.

This was a favorite back in the day. I liked that it used a rotary optical encoder (like the Tempest spinner) for control of the ship orientation.

[peteym5]

For Omega Race I would consider using a Player Multiplexer routine for the moving stuff. A simple Line drawing Routine for Screen Lines. Missiles for Bullets. Soft Sprites for those Triangle Minds. Trying to do the whole game with Soft Sprites may bog the game speed down. I know my routine does not work in 320 pixel mode. The Coleco Version is more colorful.

[Heaven/TQA]

Pete... why should softsprite make it slow as the VIC20 version runs at top speed?

[Heaven/TQA]

[Heaven/TQA]

take VIC-core code. patch the softsprite routines and bang... game ready

[peteym5]

I always think in terms of doing animation within a single VBI cycle. Sometimes doing multiple large software sprites usually exceeds the time we have within one VBI. I have successfully tested Player / Missile multiplexers that can handle 20 sprites, at around 20x8. Does it within the time the scan line goes from the last Display List line and the top of the playfield on the next frame. However I was simulating the scoreboard at the top of the screen so it was not a full 192 pixels tall. Display Line is 2 Antic 3 lines, 2 pixel gap, then 23 Antic 4 Lines. DLI on every line for to change player positions, color, and width. Typical playfield. Using a bitmapped screen, can have DLIs maybe every 6 pixels to reduce flickering.

 

Would need to disassemble the VIC-20 core code first. If I am not mistaken, the VIC-20 did not have a direct bitmapp mode. Had to be set up in software with a 256 16x8 characters and alter a custom character set. Uses 4K RAM. Similar to using Graph2Font, Know that the VIC-20 does not do an equivalent of DLIs. Know the 64 does Raster Interrupts. Remember it shrank the screen width to 20 characters (160 pixels) by 12 characters (192 pxels). But the Atari 8 bit has it in the Operating System with 4 colors + Player / Missile Graphics. Can make good port with extras.

 

When I ported Venture, I gave it options to play a Standard Arcade / Coleco or an Enhanced More Challenging Mode. Maybe can do it with Omega Race also.

[snicklin]

I did some line drawing algorithms on the pc a few years ago. How do you handle screen clipping?

 

If you are only handling items under a certain size, can some precalculating be done?

 

[peteym5]

I basically ignored screen clipping to take advantage of more speed. It is optimized for games that keeps everything on the screen. It is table driven that reduce CPU cycles to convert the x, y position to screen byte / bits.

 

I had some thoughts about adapting to for OVERSCAN mode with HSCROLL active for games that requires it. Know that it goes to 48byte per line and need to multiple LMS in the display lines due to Antic 4K boundry. If you want something other than 40/48, would need a LMS on every Display List Line.

[potatohead]

IMHO, soft sprites make a lot of sense for this one. At times, depending on player skill, there are a lot of enemy death events and shots happening! This would exceed the hardware sprite capability without a multiplexer and honestly a straight up bitmap ends up better looking and playing when that's true. Flicker city in many cases, or a very complex sorter needed.

 

Personally, I would prefer to see it done in 320 pixel mode, using the PM graphics as color "overlays" in the old school vector style, not for actual objects as the resolution differences kind of break things. Would be super cool to see it interlaced, running at 25-30 FPS, just so the resolution of things gets cranked way up, because that is the appeal of this one. I know this seems wrong, because that 50 / 60 fps is always the "smooth" goal, but really some of the appeal of this one is the choppy movement and delicate balance of resources that drive it. I'm not sure the original exceeded 25 / 30 FPS motion. Sharp line art make the thing, not color.

 

I am not sure the driving controller has enough resolution to work, but it could. The original had at least 16 angular positions. Driving controller has 8... Maybe mouse type acceleration would help with this, or maybe the resolution of the driving controller is just fine... however it works, a rotary controller makes great sense. Joystick / pad kind of ports work, but a lot of the cool game interaction is lost.

 

Player gets a lot of concurrent shots! I think the max is 6 or 8, something like that. Using the missiles would limit this part of the game. Once the initial "get a feel for it" three levels are complete, all those shots are really needed!

 

Couple of optimizations I can think of:

 

There are only a few shapes, meaning they can all be pre-rotated and shifted in advance. Use a lot of RAM, as the game itself has little in terms of bells and whistles. Limit the number of rotation states for the active enemies.

 

Omega Race does not move everything per frame. A shot is small, and a dedicated routine for processing those would allow for prioritizing player movement, active enemy movement and shots above other things.

 

The original had kind of chunky shot movement. I'm not sure whether or not that was due to the shots moving near the display refresh rate or not... but, reducing shot move precision during high soft sprite demand times would not get noticed and would feel authentic.

 

"Ripple draw" the non-aggressive enemies and triangle mines. These can get updated as time permits and again in most cases won't be noticed as the action is elsewhere. By "ripple draw" I mean update positions as time permits to augment that shuffling seen in the drones.

 

Coarse, forgiving collisions in favor of the player. The original did this. it's a little obvious on the early levels, but kind of warranted given how intense the later ones really are.

 

Dedicated routines to highlight boundary collisions as the original did. The horizontal ones are easy, just blast a few bytes. The vertical ones would be great candidates for a quick P/M overlay, The thicker pixel would add emphasis to this similar to the "blooming" seen in the CRT of the original on the same condition. Since horizontal ones are quick, just thicken it a little on highlight by drawing two lines, deffo do this in interlace mode so that the flicker won't be seen on the static boundary lines.

 

Top priority is player ship, second is active enemies, then shots, in terms of per frame updates and motion precision. Honestly, if this were to slow down gracefully when the game gets really intense, it would be kind of awesome like we see in "star raiders" from time to time, or another example is "defender" when hitting the box shaped things that drop the little mines causes a pretty severe slow down that good players learn to exploit... I don't recall the original doing this, but... anyway.

 

The passive enemies can just get their positions updated every frame, but drawing them happens when there is time. They will jump about a little during high action times, but again that's closer to the original motion than not. They kind of shuffle along, and maybe that's good to enforce anyway. Just cap this to X per frame and call it good.

 

If it's in interlaced mode, or maybe even if it's not, having two sets of shapes, one every pixel and another one drawn with pixels missing, gets the two grey scales needed to emphasize the active things, which are shots, player, and active enemy. On PAL, this will work nicely. On NTSC, somebody will need to turn the color down, or run S-video, etc...

 

Unless the line draw is really fast, I think soft sprites win easily due to the setup and line case selection being very high overhead compared to all the short line vectors this game has in it's visuals. There aren't any big shapes other than the borders...

[peteym5]

If OMEGA race was going to done in 160x192 mode with player/missile. I Would use players for the ship and the shooting enemy, that fast moving flciker enemy, and explosions. Do those slower moving circles with soft sprites since they don't have to be updated every frame. So it would not need a player/missile multiplexer to handle more than 8 sprites. Would doubt we will be running into more than 4 sprites on one line in that case. The borders can be done with seperate vertical / horizontal only linedraw routines.

 

But if we do 320x200 mode, could do it all in soft sprites. Only have to do 3 enemy types that need to be pre shifted horizontally. Minds just need to be drawn once. Should do the ship with line drawing since there is only one, trying to have each ship angle and 8 shifts could eat up lots of memory. Need to leave room for programming, screen, sound, etc.

 

If we want to put the game on a cartridge and sell it. Might need 32K one with bank switching abilities. Probably can put all the soft sprite sources in 8K one bank, program code, title screens, sounds others. I had experience with bank switching carts and know its better to organize data in the banks so you don't have to do massive bank switching that slows things down.

[Rybags]

Easiest way to do clipping IMO would be to just use LMS and space out the scanlines such that overdraw won't be visible. Then it's a simple case of bounds check for the extreme RHS condition.

 

Additional to that, 64 byte rather than 40 byte spacing can sometimes allow time saving for some other screen operations as the calculations become easier.

[kenjennings]

.. I am not sure the driving controller has enough resolution to work, but it could. The original had at least 16 angular positions. Driving controller has 8... Maybe mouse type acceleration would help with this, or maybe the resolution of the driving controller is just fine... however it works, a rotary controller makes great sense. Joystick / pad kind of ports work, but a lot of the cool game interaction is lost. ...

 

The driving controller should work fine for direction. the controller doesn't indicate angular positions. It indicates relative direction of rotation, so it could be used to rotate through 16 discrete directions, or 180.

 

The problem with the controller is that it has only one button. The game needs a thrust and a fire button.