OK, here are a few pointers to get super fast sprite plotters:

1. Fiddle with the cache. On SA's (And probably other computers), the VRAM isn't set to be cacheable by default. This is because if it was cacheable, then you'd end up with blocks of screen memory which might not get written to the VRAM for a long time, resulting in them being missing/out of date when the VIDC sends them to the monitor. However if screen banking is used, then you could write some code to make the VRAM cacheable, then just flush the right part of the cache whenever you're about to switch screen banks. Don't ask me how to do this though - I've never tried it. If you do ask nicely enough though, I may write a small module to do the cache fiddling automatically.
2. Compressed sprites. These are what gave FastSpr its speed, by cutting down on the amount of sprite/screen data being loaded. I have written my own compressed 24bit sprite drawer, but since I haven't written a sprite converter the code is untested. I can give you a copy if you want, but don't expect it to work/be legible.
3. Cut down on the amount of drawing being done. For example if you are going to be drawing a map made up of squares (Or can split the screen up into a grid), then it's quite easy to work out which squares have changed since the screen bank you are writing to was last drawn. Then you only have to redraw what's in those squares, thus cutting down on up to about 90% of the drawing. This gives a major speed boost if your engine can support it (e.g. an RTS with pixel-perfect scrolling would find it very hard, while a block-scrolling one would find it very easy). Just make sure to keep two copies of the 'redraw list' - one for each screen bank. Modern PC games (e.g. The Sims) still use this technique, so it must be good . In the case of a pixel-perfect scroller (Or the WIMP, since the technique is essentially the same), you can copy blocks of screen from one bank to the other in order to scroll around - copy the main part of the image which is unchanged (But at a different location), then redraw the bits round the edge.
4. Something I've just thought of, but might not be the best idea. If you're working with lots of layered objects (Preferably sprites which are unmasked), then you could build up a list of line sections to be redrawn, like a 3D renderer might do. That way you can work out which areas are behing solid objects before you go writing them to screen, and so cut down on the number of times each screen pixel is rewritten by a sprite appearing ontop of it. I've got no idea whether there are any 2D games that use this, but it is a good technique for 3D games.

* The end of a line, possibly also including how many pixels to skip at the start of the next line
* A mask section, where the number of pixels to skip would be given
* A colour section

The colour section would be the most complex part - e.g. whether it's a single pixel of colour and then how many times to repeat it, or more complex where you can have multiple pixels repeated (Or just multiple pixels drawn once).

You could also add a lookup table for finding the start of each row of the sprite, for when sprites are clipped off the top (Or right) of the screen. I've got no idea how useful this is though.

If you can find a copy of FastSpr, then you might be able to reverse-engineer the plotter/sprites a bit to work out the file format it uses.

However compressing 32K sprites is a different matter, due to the increased number of colours. You might be able to find a way of seperating the drawing information from the sprite itself - e.g:

<Info word> <Data> <Data> <Data> ... <Data> <Info word> etc.

And the info word could be split up into a series of actions, probably one in each byte. A 0 could signify the end of a line, <128 for n words of sprite, 128 for a mixed word of sprite & masked pixel, and >128 for n-128 words of mask. Obviously this method of compression isn't the best for sprites which are just blocks of colour - for that you'd have to introduce extra count info, perhaps splitting each <128 byte in two so the top nibble is how long the data is, and the bottom is how many times it should be drawn.

You'd also have to consider such things as how long it would take to load the sprite pixels at each different pattern length, and even if the whole pattern can fit into the registers at once.

My advice if you're going to try a compressed sprite plotter would be to write two routines - a fast one for when all the sprite is on screen, and a slower one for if it is partially off screen.

As Jeff suggests for vertical clipping the sprites have a table of which each element points to the start of each row of the sprite. IIRC (it's been a while) both Warp and Popcorn also use this table during plotting because it's easier than marking the start / end of each row in the sprite data.

Each row is encoded as a series of segments. Each segment begins with a word identifier which, IIRC, the bottom three bytes represents the length of the segment and the top bit represents whether it's a transparent section or actual sprite data that follows.

If it's a transparent section you simply add the segment length to your screen pointer and reduce your count of the number of pixels to plot for the row.

If it's sprite data you plot the pixels present (either bytes, half words or words) and reduce your count of number of pixels to plot for the row.

Horizontal clipping is a bit more involved. Basically you reduce the width of the row by the amount you are off the right hand side (easy). For left clipping you have to run through the row until you're on the screen and can start plotting.

Both Warp and Popcorn (and I think FastSpr) generate up to four versions of the sprite to increase performance at non-word aligned positions.

The technique is described in serveral places, including the FastSpr docs, the Popcorn articles in AU and I've got a doc at home describing it for Warp which I can pass on (along with source code) if you want.

I don't know how effective it is for 15/24bpp sprites because I wrote the Warp code when I only had an A4000 and the last version is a bit temperamental on my RS. However bear in mind that in both these colour depths you're chucking a hell of a lot of data across the RPCs bus. In theory Kinetic should really help here.

The method that Jeffrey mentioned abouit redrawing only sections of the screen is called 'dirty rectangle redraw'. There are numerous docs on the web about it and it is used heavily not only in games, but also in emulators.

It's one of the simplest ways of reducing the amount that you draw. Other little tricks such as not clearing the screen are good (assuming you are plotting to it all anyway) - very often used in software 3d. Basically anything which reduces data bandwidth each frame is a good thing.

The technique Lee suggests about effectively RLE'ing the transparent data is good as it means you are not testing loads of unplotted pixels. However it makes things awkward if you scale/rotate them.

There are loads of docs around the web that cover general ideas for speeding up 2d engines. I'm sure Gamasutra has some and a Google search should yield loads of stuff.

...David

So a lookup table would help by indicating the adress for the next row of sprite data on screen instead of calculating it?

No, the lookup table points to the start of each row of sprite data, not where it should be drawn on screen.

I think that different techniques are required for different requirements: if you've got sprites with a lot of 'holes' in it (ie. transparency), then having a routine that concentrates on moving lots of data around isn't going to be very efficient as it'll have to step around the holes; conversely, if you've got sprites with little or no transparency, you'd want to have something that has speed but limited dexterity. You also need to decide if the sprite is to be clipped or not, as clipping routines generally complicate matters quite a lot.

Also, if you've got sprites that are bigger than the cropped area, then you've got to put even more code in.

ArcCommand has three types of bitmaps - background graphics (which I'll ignore - they're compressed and decompressed directly to the screen), control panel artifacts, and player/enemy data.

The control panel artifacts are things like the scanner mode, and these are word aligned, word sized and non-clipped, so that a simple LDMIA...STMIA is used to copy the data on the screen. This is particularly fast.

The player/enemy sprites are an entirely different matter, as they are cropped and have a lot of transparency.

The technique is similar to what has been described before - except that each sprite file can have multiple sprites in it (one for each rotation). This is dealt with by a simple offset table into the sprite area for each sprite.

Anyway, the code does something like:

1. If the sprite is off screen, then don't do anything (trivial removal)

2. If the sprite number is higher than the number of sprites in the file, don't do anything (trivial removal, mainly in case of code errors).

3. Get the offset into the sprite area for this sprite

4. If the sprite is clipped in the Y then:

4a. If the sprite is clipped above the top of the screen (negative Y), use the offset table to get the position of the -Y line (ie. positive offset), and change the height by +Y (ie. decrease height)

4b. If the sprite is clipped below the bottom of the screen, just change the height by how much the sprite is off screen, and get the first line offset.

5. If it ain't clipped, then just get the first line offset.

6. If the sprite isn't clipped in the X, then a simple algorithm is used for each pixel in the X coordinate:

6a. Read byte. This indicates how many bytes to skip

6b. Read byte. This is how many bytes to plot. Plot these bytes

6c. Repeat until we've got to the end

Note that the code actually reads the first byte and if it's the width, skips the entire line (trivial line removal).

7. If it's clipped in the X, then do the same, but keep track of the clipping position (this is quite complicated)

8. Repeat until all rows plotted.

Equinox (the new game) actually has an extra bitmap type, and 5 different plotting algorithms depending on what it's doing:

- Back compressed image (title graphics)

- Player/enemy/bullet sprites (slightly enhanced version of the above algorithm)

- Control panel artifacts (word aligned, word sized, non-transparent, non-clipped)

- 'Shop' graphics (word aligned, word sized, non-transparent, vertically clipped)

- Game background map graphic (word aligned, word sized, non-transparent, non-clipped, map arranged)

I could go on a bit more, but I think I've spent long enough on it

It's interesting to see what someone wrote a while back...

Just realised this thread died a long time ago

You silly boy

Interesting about all the different clipping methods you've used though - I usually only bother with one, which will handle all situations (sprite on screen, sprite off screen, sprite partially off screen, sprite bigger than screen, etc.). It only comes to about 10 or 15 instructions extra, which shouldn't tax the processor too much for situations like HUD graphics which will be word on-screen, word-aligned, etc.

Recently I've been writing a set of routines as assembler macros, in the hope that they'll be flexible enough for me to never have to write any again. I'm more interested in the exotic sprite plotters - e.g. plotting rotated/scaled sprites, for which I'm going to try out 'tiling' - i.e. splitting the sprites up into small cache-line sized tiles in order to increase the probability of a cache hit. If you search round on the net then there are quite a few interesting tutorials on PC graphics which mention tricks like these (e.g. http://stuff3d.tripod.com/tutorials.htm http://www.exaflop.org/docs/fatmap/ind.html, although they are more about 3D graphics)

Just realised this thread died a long time ago

You silly boy

Well, I can always ressurect it

Interesting about all the different clipping methods you've used though - I usually only bother with one

Mine depend on the context they're used. The game mainly use:

1. Background plotting

2. Static object plotting (word aligned, non-clipped, non-transparent)

3. Full transparency + clipped.

I don't have sprites bigger than the screen, but I can see a way to implement them without too much overhead on single-sided clipped sprites.

The differences between the first two depend on the data orientation (which has been arranged to minimise transfer of background data that is contiguous).

Recently I've been writing a set of routines as assembler macros, in the hope that they'll be flexible enough for me to never have to write any again. I'm more interested in the exotic sprite plotters - e.g. plotting rotated/scaled sprites

Sounds interesting.

I've done 3D mapping (did a demo with a camouflaged tank), but I've not optimised it yet (ie. it's still in C). The 3D surface is a convex polygon mapping onto a convex polygon on a square bitmap, allowing for quite a bit of flexibility. I was going to make a game out of it, but 3D games are quite complex to get right.

I've done 3D mapping (did a demo with a camouflaged tank), but I've not optimised it yet (ie. it's still in C). The 3D surface is a convex polygon mapping onto a convex polygon on a square bitmap, allowing for quite a bit of flexibility.

Interesting

I was going to make a game out of it, but 3D games are quite complex to get right.

Hopefully once I've got the sprite plotter code done, I'll get round to writing some (2D) games - instead of just talking about it all the time

Not very useful when I'm trying to find hints for an algorithm to replace my current one

But since I'm here now...

Recently I've been writing a set of routines as assembler macros, in the hope that they'll be flexible enough for me to never have to write any again. I'm more interested in the exotic sprite plotters - e.g. plotting rotated/scaled sprites, for which I'm going to try out 'tiling' - i.e. splitting the sprites up into small cache-line sized tiles in order to increase the probability of a cache hit.

This macro based code does exist, and seems to work very nicely (Bar the rather ugly rotated/scaled sprite plotter). I haven't tried the tiling technique yet though, as I haven't had much need for plotting large numbers of rotated/scaled sprites until now. That and the poor quality of the controlling algorithm is a much greater concern to get sorted out.

For anyone who's interested, the sprite plotters are part of a smallish graphics package called "GnarlPlot", available here. It's written in a mix of C and assembler. There are three colour depths (8bpp, 16bpp, 24bpp) and four mask types (no mask, simple on/off mask, greyscale alpha channel, RGB alpha channel) supported.

This makes 12 basic sprite formats and 12 screen buffer formats, resulting in 144 different plotting algorithms. This is why I wanted to use macros, because writing and debugging 144 different sprite plotters isn't much fun

To save on memory/disc space I'm actually using runtime assembly to generate the sprite plotters. This also allows me to have more complex macros, since I can have the macro make decisions about how many registers are free for storing data in, etc. There are a few different plotter generators, each one tailored for different situations (e.g. word aligned plotting vs. non-word aligned plotting). Resulting code is kept in memory so that it can be reused as many times as needed. There are also last-resort plotters written in C, for if an appropriate plotter generator hasn't been written yet.

Besides the 12 basic sprite formats there are also four preshifted sprite formats (8bpp unmasked, 8bpp on/off mask, 16bpp unmasked, 16bpp on/off mask), with their appropriate plotter generators.

And if that isn't good enough, the system also allows for totally unique sprite formats, because everything is done via a C++ style class system. Each sprite has two bits of information: A pointer to its definition and a pointer to its data. The definition is just a list of functions, one for each sprite operation (creation, reading/writing pixels, plotting, etc), and the data part is completely at the mercy of the functions given in the sprite definition.

As long as a program sticks to using the interfaces given in the sprite definition, it will be compatible with sprites of any format.

At the moment the only extra format I have is one designed for manipulating !Paint sprites. This is particularly useful during the loading sequence of a game, e.g. to read a Sprite File from disc and convert all the sprites to a more optimal format for the current screen mode.

Now if only I could find a good algorithm to perform scanline conversion on rotated/scaled sprites