Infinite scrolling maps/scroll plane "edge" DMA

Ask anything your want about Megadrive/Genesis programming.

Moderator: BigEvilCorporation

powerofrecall
Very interested
Posts: 237
Joined: Fri Apr 17, 2009 7:35 pm
Location: USA

Infinite scrolling maps/scroll plane "edge" DMA

Post by powerofrecall » Thu Jun 16, 2016 6:57 pm

I want to 8-way "infinite" scroll a plane, presumably by reloading the plane's nametable at just past the edge of the visible screen. What's the generally accepted way to accomplish this?

Assume I have two functions, both that do a DMA to copy either a 40 tile wide "row" or a 32 tile high "column." The "row" DMA is just a simple copy to whatever tile Y position is specified, 40 nametable entries long. The "column" DMA is similar but it takes a tile X coordinate, with the VDP auto increment set to 2 times the plane width (in this case 128), and the copy is 32 nametable entries long. I am assuming this is technically sound. I understand the idea of it--that basically, you figure where the edge of the visible screen is, where that position currently is in the nametable, and copy a row or column of the next nametable entries there to give the illusion of an infinitely large scroll. This is my understanding of it, correct me if I misunderstand.

Here's what I don't understand. Obviously if I have a map larger than 64x32 I cannot load the whole thing at once, especially if I eventually decide to compress the nametable at all. Putting the raw map into the ROM seems like it would work but that could get large quickly I assume. How is this done in a "real" game?

Sik
Very interested
Posts: 889
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by Sik » Thu Jun 16, 2016 7:49 pm

Check if a new row/column would be visible, then DMA it... yeah there isn't much more to it than that. Also don't bother doing it for more than one row/column because it's pretty much unlikely it'll happen (and if it's a problem, do like Sonic and put a cap on the camera's speed).

Relevant:
https://github.com/sikthehedgehog/drago ... e.68k#L197

By the way, if your tilemap is 64 tiles wide (i.e. 64×32 or 64×64) then you can set autoincrement to $80 to draw tiles vertically, so you can load a whole column with a single transfer.

EDIT: also you don't store the nametable as-is, that's ridiculous o_o (a nametable on its own is 4KB) You generally have chunks e.g. 16×16 pixels (2×2 tiles) or 32×32 pixels (4×4 tiles), which are usually just a byte each (indicating which graphic to show and/or which collision type it has). If you use 32×32 chunks, a 64×32 tiles nametable would be 16×8 chunks, which would be only 128 bytes on ROM. (and a screen is even smaller than that: 10×7 chunks i.e. 70 bytes)
Sik is pronounced as "seek", not as "sick".

powerofrecall
Very interested
Posts: 237
Joined: Fri Apr 17, 2009 7:35 pm
Location: USA

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by powerofrecall » Thu Jun 16, 2016 9:24 pm

Sik wrote: By the way, if your tilemap is 64 tiles wide (i.e. 64×32 or 64×64) then you can set autoincrement to $80 to draw tiles vertically, so you can load a whole column with a single transfer.
Good to know this will work the way I thought it would!
Sik wrote: EDIT: also you don't store the nametable as-is, that's ridiculous o_o (a nametable on its own is 4KB) You generally have chunks e.g. 16×16 pixels (2×2 tiles) or 32×32 pixels (4×4 tiles), which are usually just a byte each (indicating which graphic to show and/or which collision type it has). If you use 32×32 chunks, a 64×32 tiles nametable would be 16×8 chunks, which would be only 128 bytes on ROM. (and a screen is even smaller than that: 10×7 chunks i.e. 70 bytes)
Okay, cool. Are there any map editors out there that would help with this?

Sik
Very interested
Posts: 889
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by Sik » Thu Jun 16, 2016 9:35 pm

Well, for Dragon's Castle I'm using Tiled, though you need to use some specific settings to have it work (more specifically, I have a converter script that takes the TMX file and turns it into the game's format, and it does so in a rather lame and lazy way). Still probably good enough to work I suppose, though you need to edit it each time you add an tile or object type (or to handle when effects get included).
https://github.com/sikthehedgehog/drago ... estage.php

The converter exploits the fact that Tiled will always output using a very specific syntax so you don't need to really implement a full blown XML parser to get it to work, just look for some specific patterns in each line.

Image

EDIT: just to make it clear, the converter is run from the build script so no, I don't forget to convert levels when rebuilding the ROM. It takes like less than a second to go through all levels anyway.
Sik is pronounced as "seek", not as "sick".

Nemesis
Very interested
Posts: 773
Joined: Wed Nov 07, 2007 1:09 am
Location: Sydney, Australia

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by Nemesis » Thu Jun 16, 2016 11:54 pm

I'd also add that visualizing what's going on in your head with the tile planes can be quite difficult, especially if you've got hscroll or vscroll happening. You might want to take a look at the plane viewer feature in Exodus:
Image
It allows you to inspect and debug these kind of problems much more easily. You might also want to observe the behaviour of other games, like the sonic series for example, to see how the approaches they used update the tile planes.

powerofrecall
Very interested
Posts: 237
Joined: Fri Apr 17, 2009 7:35 pm
Location: USA

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by powerofrecall » Fri Jun 17, 2016 2:26 am

Sik wrote:Well, for Dragon's Castle I'm using Tiled, though you need to use some specific settings to have it work (more specifically, I have a converter script that takes the TMX file and turns it into the game's format, and it does so in a rather lame and lazy way). Still probably good enough to work I suppose, though you need to edit it each time you add an tile or object type (or to handle when effects get included).
https://github.com/sikthehedgehog/drago ... estage.php

The converter exploits the fact that Tiled will always output using a very specific syntax so you don't need to really implement a full blown XML parser to get it to work, just look for some specific patterns in each line.

Image

EDIT: just to make it clear, the converter is run from the build script so no, I don't forget to convert levels when rebuilding the ROM. It takes like less than a second to go through all levels anyway.
This is great, I see what you mean about not really having to have a parser. Should make it easy to hack more objects in too. This is cool because I was messing around with Tiled anyway seeing if it would be good to go with.

powerofrecall
Very interested
Posts: 237
Joined: Fri Apr 17, 2009 7:35 pm
Location: USA

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by powerofrecall » Fri Jun 17, 2016 2:30 am

Sik wrote:Dragon's Castle
Oh by the way Dragon's Castle is excellent and definitely an inspiration for me to keep going. I'm very impressed it's in 68k, I am terrible at writing logic type stuff in assembly.

Sik
Very interested
Posts: 889
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by Sik » Fri Jun 17, 2016 9:50 pm

I really need to get back on track with that =/
Sik is pronounced as "seek", not as "sick".

BigEvilCorporation
Very interested
Posts: 209
Joined: Sat Sep 08, 2012 10:41 am
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by BigEvilCorporation » Sat Jun 18, 2016 4:39 pm

I'm doing pretty much that - stream in one screen's worth of data at the start of the level, then only work with the delta row/columns after that. Ensure that your camera's velocity can't exceed more than one tile or that you have the bandwidth spare to keep up.

I'm also using the "ridiculous" storage method - storing the raw nametable data in ROM. It's big, but it's flexible. My game's environment can't yet be narrowed down to 8x8 or 16x6 tilesets, maybe one day I'll sort that out.

For creating maps, I'm using Beehive, my own homebrew tile/map/sprite/animation editor: viewtopic.php?f=7&t=2259
Sik wrote: By the way, if your tilemap is 64 tiles wide (i.e. 64×32 or 64×64) then you can set autoincrement to $80 to draw tiles vertically, so you can load a whole column with a single transfer.
I didn't know autotincrement could go that high, that's just opened up a whole load of opportunities!
A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

MintyTheCat
Very interested
Posts: 484
Joined: Sat Mar 05, 2011 11:11 pm
Location: Berlin, Germany

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by MintyTheCat » Sat Jun 18, 2016 5:47 pm

BigEvilCorporation wrote:I'm doing pretty much that - stream in one screen's worth of data at the start of the level, then only work with the delta row/columns after that. Ensure that your camera's velocity can't exceed more than one tile or that you have the bandwidth spare to keep up.
I update with deltas too using carefully selected combinations of tiles too and it thus far is fine performance wise.
BigEvilCorporation wrote: I'm also using the "ridiculous" storage method - storing the raw nametable data in ROM. It's big, but it's flexible. My game's environment can't yet be narrowed down to 8x8 or 16x6 tilesets, maybe one day I'll sort that out.
No compression at all?! Have you not got a ROM size limit in mind? To be honest, I haven't really sat down to work out how much I want to spend on the ROM size but I make things take up as little space as possible to give me breathing space for later on.
UMDK Fanboy

BigEvilCorporation
Very interested
Posts: 209
Joined: Sat Sep 08, 2012 10:41 am
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by BigEvilCorporation » Sat Jun 18, 2016 8:14 pm

MintyTheCat wrote:No compression at all?! Have you not got a ROM size limit in mind? To be honest, I haven't really sat down to work out how much I want to spend on the ROM size but I make things take up as little space as possible to give me breathing space for later on.
It's on the "I'll deal with it when the time comes" list. Prototype build (2 levels) is currently 900kb (2 foreground maps, 2 background maps, 2 collision maps, level tiles, terrain tiles, player and enemy tiles, animation data, and a font), I guess I could go all the way up to 3MB before it becomes a real problem, fast and big cart space is dirt cheap. The only real issue I'm having is the 128kb limit on my devkit, but I have a build config which strips out everything but a tiny mechanics test level if I need to use it.

I have no knowledge of compression at all. I have a theoretical implementation in mind which is 1 byte of data followed by 1 byte with the count of that first byte, which for tile and map data that's mostly filled with 0's would shrink it down to something tiny and decompress ridiculously fast. It'll double the size of randomised data, though. I'll do some real research before I start, of course.
A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

Sik
Very interested
Posts: 889
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by Sik » Sat Jun 18, 2016 11:29 pm

https://www.youtube.com/watch?v=GFO6hAXCQSU
This thing used tile values 242 to 255 as special values for RLE (242 = repeat last tile twice more, 243 = repeat 3x more, 244 = repeat 4x more, etc.). This meant I could only use up to 242 tiles instead of 256 (not like I'd ever get anywhere close to that in the first place), but it meant data would never get larger, only smaller (a tile used on its own is stored as-is).

You could probably take a similar approach. That said, still questioning the idea of storing nametables as-is... if you're doing it for the sake of having more freedom, aren't you also likely to try to use so many unique tiles that they won't fit in video memory? Or are you planning to stream in tiles ala Sonic 3D?
Sik is pronounced as "seek", not as "sick".

MintyTheCat
Very interested
Posts: 484
Joined: Sat Mar 05, 2011 11:11 pm
Location: Berlin, Germany

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by MintyTheCat » Sun Jun 19, 2016 7:10 am

BigEvilCorporation wrote:
MintyTheCat wrote:No compression at all?! Have you not got a ROM size limit in mind? To be honest, I haven't really sat down to work out how much I want to spend on the ROM size but I make things take up as little space as possible to give me breathing space for later on.
I have no knowledge of compression at all. I have a theoretical implementation in mind which is 1 byte of data followed by 1 byte with the count of that first byte, which for tile and map data that's mostly filled with 0's would shrink it down to something tiny and decompress ridiculously fast. It'll double the size of randomised data, though. I'll do some real research before I start, of course.
You are describing "run length encoding".

There are several schemes that have been used and some here:

http://segaretro.org/Nemesis_compression
http://segaretro.org/Kosinski_compression
http://segaretro.org/Enigma_compression

Those may all be applicable to your game.
You will find many variations on Huffman Trees, dictionary based compression, etc. but off the top of my head this book was pretty useful when I was learning about compression back in College:

https://www.amazon.co.uk/Data-Compressi ... ssion+book

There are some compression schemes that you only find in one game on the MD such as outsuka used in Thunderforce 3 but it is really worth learning about what has already been developed for the MD compression wise as it can be quite beneficial.

Cheers.
UMDK Fanboy

BigEvilCorporation
Very interested
Posts: 209
Joined: Sat Sep 08, 2012 10:41 am
Contact:

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by BigEvilCorporation » Sun Jun 19, 2016 4:37 pm

Sik wrote:still questioning the idea of storing nametables as-is... if you're doing it for the sake of having more freedom, aren't you also likely to try to use so many unique tiles that they won't fit in video memory? Or are you planning to stream in tiles ala Sonic 3D?
The tile count is under control, it's just the map layout that's the problem. It will get redone at some point, but for now it's working and enough to get a prototype finished. The first few levels are throw-away tests so we'll get the opportunity to redo the pipeline.

The Sonic3D method keeps popping back into my head and I would really like to try an implementation of it some day.
MintyTheCat wrote: You are describing "run length encoding".
Woo! I knew a thing! I'll grab that book and get busy.
A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

powerofrecall
Very interested
Posts: 237
Joined: Fri Apr 17, 2009 7:35 pm
Location: USA

Re: Infinite scrolling maps/scroll plane "edge" DMA

Post by powerofrecall » Thu Jul 14, 2016 2:49 am

A good easy to implement fast RLE is the "mac packbits" format

https://en.wikipedia.org/wiki/PackBits

C packer source is available at https://pineight.com/nes/ under "pin eight NES tools"

Here's an unpacker, in C (this would be real easy to write in 68k though), that I have been using for nametables of static screens. I need to change this to write straight to the VDP actually...

Code: Select all

void unpack_bits(void *src, void *dst, int32_t len)
{
	int32_t c, n;
	uint8_t *psrc = src;
	uint8_t *pdst = dst;

	while (len > 0) {
		n = *psrc++;
		if (n < 128) {
			++n;
			len -= n;
			if (len < 0) break;
			while (n--) *pdst++ = *psrc++;
		}
		else {
			n = 257 - n;
			len -= n;
			if (len < 0) break;
			c = *psrc++;
			while (n--) *pdst++ = c;
		}
	}
}

Post Reply