Scrolling RPG maps

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

User avatar
Quietust
Posts: 1710
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Re: Scrolling RPG maps

Post by Quietust » Tue Mar 30, 2021 7:54 am

zanto wrote:
Mon Mar 29, 2021 8:05 pm
When the screen loads up (e.g. after the map is just loaded), this is how I can get the bytes I need to display
1) I have to figure out what's the address of the byte on the top left tile within the camera, something like

Code: Select all

first_byte = start + (cameray * map_width) + camerax
2) Then, I'd have to loop go get all bytes in that row, so 32 times.
3) After that, I'd have to find the first byte of the next row. I can do that by adding the width to the first byte

Code: Select all

first_byte_in_row = prev_first_byte + map_width
4) go back to (2). Rules 2, 3 and 4 will be executed 30 times

Then, after I scroll to the right, for example:

1) get the first byte inside the camera, like (1) above
2) add 256 to it, so we have the byte right on the top left part that is to the right of what's displayed on screen
3) get byte 1 and byte 2 so we have a 16x16 tile
4) go to the next row, by adding "map_width" to the address we found in 2
5) go back to (3). repeat 3,4,5 30 times.

I want to make sure this is the idea, because if so, it involves a bunch of things I still don't know how to do in ASM, like 16 bit operations and multiplication. I also want to make sure that it's feasible to do these things the way I thought without causing lag and stuff

Also, will this idea work if my map is RLE compressed?
There are a variety of techniques for handling large maps. Here are the first few that come to mind:

1. Rather than storing a large map as a flat 2D array (which requires doing multiplication to find the correct offset inside, which can be quite slow if your map dimensions are not a power of 2 since the 6502 doesn't have a MUL instruction), instead use an array of pointers to other arrays. That way, no math at all is required for finding a specific entry - you just use one coordinate to find the desired pointer, then use the other coordinate as an index into that pointer. You also no longer need to know how large the map is, aside from knowing when to stop loading more data.

Code: Select all

maprow0: .db 1,2,3,4,...
maprow1: .db 5,6,7,8,...
maprow2: .db 9,10,11,12,...
map: .dw maprow0,maprow1,maprow2,...

getTile: ; with coordinates in X and Y registers
	; multiply coordinate in X by 2, since pointers are 2 bytes long
	TXA
	ASL A
	TAX
	; copy pointer from "map" into temporary pointer variable in zeropage
	LDA map,X
	STA $FE
	LDA map+1,X
	STA $FF
	; then just index into the resulting array and you have your map tile
	LDA ($FE),Y
	RTS
Of course, this approach only works with a maximum map size of 256x128 (which would take up over 32KB of space), so you'd need a further technique to handle anything larger:

2. Divide the map into "meta-tiles", or groups of tiles that are frequently reused - for example, each byte in your top-level map could refer to an 8x8 group of actual nametable entries. As long as the meta-tile dimensions are a power of 2 (i.e. 2x2, 4x4, 8x8, 16x16), any multiplication or division will simplify to bit shifting, which the 6502 can do rather easily.

3. Use multiple levels of meta-tiles and apply compression to them. Since you'll typically be fetching map tiles in groups (rows or columns), you'll be fetching the same meta-tiles over and over again, so you can decompress one into RAM and keep it around until you need to look at a different one.

I'm sure there are more methods that are more appropriate for your use case, but this should at least point you in the right direction.
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Tue Mar 30, 2021 9:38 am

My issue with using metatiles that are bigger than 16x16 pixels is that they may end up making the map looking too blocky, which looks terrible on a RPG world map. :/

User avatar
tokumaru
Posts: 12040
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling RPG maps

Post by tokumaru » Tue Mar 30, 2021 11:45 am

zanto wrote:
Mon Mar 29, 2021 8:05 pm
First, a quick question: I noticed in some examples have instructions like "lda CameraY+0". Is that the same as "lda CameraY"? If not, what's the difference?
Yes, it's the same, but I like to put the "+0" to make it clear that the variable being manipulated is larger than a byte.
The world map in Dragon Warrior 4, for example is 4096x3840 pixels. I don't know if mine will be as big, but it'll be pretty big too.
Without compression, that would need more than 240KB of space to store. I think it's time to start thinking about compression.
I'm feeling overwhelmed now, because I have no idea how to find the tiles I need to show on screen. It'd be so much easier if ASM could work with 2D arrays
The formula for accessing a 1D array using 2 dimensions is very simple: y * width + x. If the width is a power of 2, this is pretty easy to calculate in assembly.
I know a next step will be to implement a RLE compression on map data, so I'm afraid if I to work on a solution that doesn't consider it, I'll have to scrap it and think of something else because of the compression.
RLE, LZ, or any compression with variable ratios will not allow you random access to the map data, you'll have to first decompress the data to RAM before you can use it for collisions and scrolling. At 1024 bytes per screen, and only 2048 bytes of RAM, that's pretty much it of the question.

The first kind of compression you should consider is metatiles. Most NES games build their maps with 16x16-pixel blocks, and just by doing that they reduce the space required for background to 1/4 of the uncompressed size (not including the overhead of the metatiles themselves, but that becomes less relevant the more you use the metatiles). Some games even use 32x32-pixel metatiles (most games by Capcom), so an entire screen can be represented in 64 bytes instead of 1024, 1/16 of the original size! At that point you can consider buffering 4 screens worth of map data in RAM, as that'd require only 256 bytes.

User avatar
Dwedit
Posts: 4417
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Scrolling RPG maps

Post by Dwedit » Tue Mar 30, 2021 1:25 pm

I've been asked to describe how Dragon Warrior 2-4 compressed its overworld map.
This is a rough outline. (Not a full specification of the actual bit layout used by the game)

==DW2-4 Overworld Map==

It's an RLE system. 5 bits are used for Length (0-31 plus 1), 3 bits are used for Tile Type. (0-7)
But to allow more than 8 possible tiles, one Tile Type will ignore Length, and instead use the Length as the tile number. This allows up to 39 possible tiles (before applying ocean smoothing).

DW2-4 also adds shorelines to the oceans. It looks at neighboring tiles, and sees if they are Land Tiles or Ocean Tiles, then applies shores to ocean tiles as needed.

There are also Row Pointers to help you start at a particular Y coordinate.

Illustration:
Image
In this screenshot, we see Common Tiles (grass, forest, water, hills, mountains, bushes, not-shown: sand), and Uncommon tiles (signpost, bridge, 4 tiles of the castle)
Common tiles (red boxes around them) are encoded as a byte that contains the Length (up to 32 long), and the tile type. Uncommon tiles (blue boxes around them) are encoded as a byte containing a special tile type, and the Length part is used as the tile type instead.

==Implementation Strategy==
-- Smaller non-compressed view of the map --
You can't directly operate on compressed map data, you'd need a buffer of decompressed tile data.
In order to hold enough tiles to fill the screen as well as upcoming scrolling areas, then be able to do ocean shorelines, you'd need:
16 tiles horizontally (because the screen is 256 pixels wide)
+2 for scrolling
+2 for offscreen edge tiles when calculating shorelines
15 tiles vertically (because the screen is 240 pixels tall)
+2 for scrolling
+2 for offscreen edge tiles when calculating shorelines
So this map buffer would need to be at least 20x19 tiles large (380 bytes)

(more to come)
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Tue Mar 30, 2021 8:40 pm

Dwedit wrote:
Tue Mar 30, 2021 1:25 pm
I've been asked to describe how Dragon Warrior 2-4 compressed its overworld map.
This is a rough outline. (Not a full specification of the actual bit layout used by the game)
Wow! This is a treasure trove of knowledge! Discovering how games I love work makes me really excited hahaha! This will be really helpful for the map system in my game!

Dwedit wrote:
Tue Mar 30, 2021 1:25 pm
(more to come)
Can't wait for the next part! :D

Dwedit wrote:
Tue Mar 30, 2021 1:25 pm
Uncommon tiles (blue boxes around them) are encoded as a byte containing a special tile type, and the Length part is used as the tile type instead.
So, if the first 3 bits had a special value (maybe something like "111"), the game would interpret the 5 last bits as an uncommon tile? Also, just to make sure, when we're talking "tiles" here, I imagine we're actually talking about 16x16 metatiles, right? So the values I read from these bytes would actually reference another part of the memory where each of the 4 tiles (one byte each) are stored, right?

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Fri Apr 02, 2021 8:01 pm

So, I made a little (very little) progress, and I'm still struggling with scrolling :(

This is what's happening now. I placed the horizontal scroll position on the center of the two nametables. This is what some RPGs do. I don't know why, but I'm trying to do it with my game too. However, when I do it, I get the following result:
img1.png

I thought to myself this is happening because even though the scroll was in the middle of the screen I was drawing the bg at PPU address $2000, so I changed it to a different value, just to check what would happen.

Code: Select all

lda #$20

	bit PPUSTATUS
	lda #$20
	sta PPUADDR
	lda #$02
	sta PPUADDR
	ldy #$00
And this was the result:
img2.png
I'm not really sure what's happening... could anyone help me get this to work?

User avatar
tokumaru
Posts: 12040
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling RPG maps

Post by tokumaru » Fri Apr 02, 2021 9:06 pm

zanto wrote:
Fri Apr 02, 2021 8:01 pm
And this was the result:
img2.png

I'm not really sure what's happening... could anyone help me get this to work?
You started writing the data 2 bytes after the start of the name table, so you shifted the whole map by 2 tiles (the 2 rightmost columns wrapped around to the left side, 1 row down), and 2 bytes of the map ended up spilling into the attribute tables, corrupting the colors of the first 2 32x32-pixel blocks.

The NES won't automatically start drawing things to adjacent name tables, you're gonna have to calculate the addresses yourself and draw the maps in pieces to the correct name tables, as opposed to a full name table at once. Writing an 8-way scrolling engine is not exactly trivial, specially if this is your first NES project, and even for an experienced programmer this is not so simple that we could quickly write everything in a forum post.

Maybe you can simplify things a bit by drawing two full screens during the initialization, one on each name table, so you can at least scroll a bit from side to side before having to update the background. Then you can try detecting when the camera enters a new name table (hint: the 9th bit of CameraX/ScrollX will change), and when that happens you draw an entire new screen (one or two columns per frame, since there's no time in vblank to draw an entire screen), overwriting the screen that was left behind. Once you have all the horizontal scrolling working, you can think about coding the vertical part, which's harder.

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Fri Apr 02, 2021 9:52 pm

tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
Writing an 8-way scrolling engine is not exactly trivial, specially if this is your first NES project, and even for an experienced programmer this is not so simple that we could quickly write everything in a forum post.
Oh, it's not 8-way scrolling. It's 4-way. You can't move diagonally in this game. This will be a normal RPG like Dragon Warrior or Final Fantasy. I'm not even concerned about the graphical glitches that are bound to happen on the edges due to scrolling.
tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
Maybe you can simplify things a bit by drawing two full screens during the initialization, one on each name table, so you can at least scroll a bit from side to side before having to update the background. Then you can try detecting when the camera enters a new name table (hint: the 9th bit of CameraX/ScrollX will change), and when that happens you draw an entire new screen (one or two columns per frame, since there's no time in vblank to draw an entire screen), overwriting the screen that was left behind. Once you have all the horizontal scrolling working, you can think about coding the vertical part, which's harder.
My approach was to make so that when you take a step (1 step will make you move 16 pixels up, down, left or right), you load the next 16 pixel row or column in the direction you're facing.
tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
The NES won't automatically start drawing things to adjacent name tables, you're gonna have to calculate the addresses yourself and draw the maps in pieces to the correct name tables, as opposed to a full name table at once.
Is there an example somewhere on how to calculate that?


Also, I just realized that I may be making things harder for myself when I load a map. The way I'm doing it is I get the player's starting x and y position and subtract an horizontal and vertical offset to get the initial scroll x and y positions. So, basically

Code: Select all

scrollx = playerxstart-112
scrolly = playerystart-112
As a result, the scroll positions can vary depending on where the player starts in the map. Maybe I should make it so that scroll positions always start at the same position regardless of where the player starts on the map.

User avatar
tokumaru
Posts: 12040
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling RPG maps

Post by tokumaru » Fri Apr 02, 2021 10:35 pm

zanto wrote:
Fri Apr 02, 2021 9:52 pm
Oh, it's not 8-way scrolling. It's 4-way. You can't move diagonally in this game. This will be a normal RPG like Dragon Warrior or Final Fantasy. I'm not even concerned about the graphical glitches that are bound to happen on the edges due to scrolling.
Well, 4-way scrolling is as complex as 8-way, the only difference is that you'll either be updating a row *or* a column of blocks each frame, not both. The process itself is the same.
tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
My approach was to make so that when you take a step (1 step will make you move 16 pixels up, down, left or right), you load the next 16 pixel row or column in the direction you're facing.
Yup, that's the basic idea, but what complicates things is that since the scroll can be anywhere in the 512x480-pixel area of the NES' background, these columns and rows will be split across different name tables, so the process isn't as simple as setting constant VRAM addresses and writing the tiles... you have to dynamically calculate the address of where the tiles go based on the camera coordinates, figure out where the name table boundary cuts the row/column to split it in two, calculate the target address for the second part of the row/column in the other name table, and then do the same for the attributes, which are particularly complicate to handle because each attribute byte controls the colors of 32x32-pixel areas, but you're only updating 16x16-pixel areas, so there's a lot of bit manipulation involved.
tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
Is there an example somewhere on how to calculate that?
I can't think of anything at the moment, but maybe someone can point you to some example code.
As a result, the scroll positions can vary depending on where the player starts in the map. Maybe I should make it so that scroll positions always start at the same position regardless of where the player starts on the map.
If you are going to implement free scrolling, you will absolutely need to code an engine that can update columns and rows anywhere, so the starting coordinates should not be a problem.

I think that a 4-way scrolling engine may be a bit too complicated for you to tackle right now, maybe you should try implementing only the horizontal scroll first, and worry about the vertical part later. This will get you acquainted with the basics of process before you have to add a whole new dimension and the attributes issue into the mix.

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Fri Apr 02, 2021 11:10 pm

tokumaru wrote:
Fri Apr 02, 2021 10:35 pm
I think that a 4-way scrolling engine may be a bit too complicated for you to tackle right now, maybe you should try implementing only the horizontal scroll first, and worry about the vertical part later. This will get you acquainted with the basics of process before you have to add a whole new dimension and the attributes issue into the mix.
Yeah, that's what I'm doing at the moment. Once I get horizontal scroll working, I imagine working on vertical will be considerably easier.
tokumaru wrote:
Fri Apr 02, 2021 9:06 pm
Yup, that's the basic idea, but what complicates things is that since the scroll can be anywhere in the 512x480-pixel area of the NES' background, these columns and rows will be split across different name tables, so the process isn't as simple as setting constant VRAM addresses and writing the tiles... you have to dynamically calculate the address of where the tiles go based on the camera coordinates, figure out where the name table boundary cuts the row/column to split it in two, calculate the target address for the second part of the row/column in the other name table, and then do the same for the attributes, which are particularly complicate to handle because each attribute byte controls the colors of 32x32-pixel areas, but you're only updating 16x16-pixel areas, so there's a lot of bit manipulation involved.
Just thinking about attribute manipulation sends a shiver up my spine...
tokumaru wrote:
Fri Apr 02, 2021 10:35 pm
Is there an example somewhere on how to calculate that?
I can't think of anything at the moment, but maybe someone can point you to some example code.
I see... I feel like this is the hardest part of working with nes development, specially ASM... it's not easy to find examples for things beyond the basic stuff like drawing stuff on screen. I rarely found code examples that were for useful my issues, so I had to do most things from scratch. Or maybe I didn't search the right places or didn't understand what is available. Sorry for venting like that :P
tokumaru wrote:
Fri Apr 02, 2021 10:35 pm
As a result, the scroll positions can vary depending on where the player starts in the map. Maybe I should make it so that scroll positions always start at the same position regardless of where the player starts on the map.
If you are going to implement free scrolling, you will absolutely need to code an engine that can update columns and rows anywhere, so the starting coordinates should not be a problem.
I thought making the scroll always start on the same place would make it easier to know where in the memory I need to draw rows and columns. And from there knowing where the next rows and columns need to be drawn as the player move would be more "under control"... But I guess I'll drop that idea.

Maybe you can simplify things a bit by drawing two full screens during the initialization, one on each name table, so you can at least scroll a bit from side to side before having to update the background. Then you can try detecting when the camera enters a new name table (hint: the 9th bit of CameraX/ScrollX will change).
I don't really understand this. Does it mean that if the 9th bit of camerax/cameray changes I can switch which nametable the new columns/rows will be written to? Is this a thing that only works when scrolling happens?


Oh, can I change the address I'm writing to using PPUADDR while I'm writing bytes into PPUDATA?

Pokun
Posts: 1814
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Scrolling RPG maps

Post by Pokun » Sat Apr 03, 2021 9:16 am

The 9th bit of CameraX is the same as the nametable number I guess.

Yes you can change the address between each write to PPUDATA, but it's slower than writing repeatedly and just let the auto-increment handle it.

When you are stuck it might help to look at how Dragon Quest and Final Fantasy is doing this. That's what I did in the past. DW1 is here and FF1 here. I found DW2 here but link appears to be dead.

GameFAQ also has save format and formula guides for most DW games which I find very useful, although those don't describe scrolling.

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Sat Apr 03, 2021 9:35 am

Pokun wrote:
Sat Apr 03, 2021 9:16 am
The 9th bit of CameraX is the same as the nametable number I guess.

Yes you can change the address between each write to PPUDATA, but it's slower than writing repeatedly and just let the auto-increment handle it.
I see, that's good to know.

Pokun wrote:
Sat Apr 03, 2021 9:16 am
When you are stuck it might help to look at how Dragon Quest and Final Fantasy is doing this. That's what I did in the past. DW1 is here and FF1 here. I found DW2 here but link appears to be dead.

GameFAQ also has save format and formula guides for most DW games which I find very useful, although those don't describe scrolling.
Oh cool! This will be very helpful! Thank you for sharing these! :D

Pokun
Posts: 1814
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Scrolling RPG maps

Post by Pokun » Sat Apr 03, 2021 10:37 am

Also remember that VRAM increment mode is changed in $2000. It can be set to +1 (for horizontal nametable writes) or to +32 (for vertical nametable writes). So when you scroll horizontally you set it to +32 to update a character column and to +1 when scrolling vertically to update a character row, I guess. That way you might never need to change the VRAM address more than once per BG update.

User avatar
zanto
Posts: 53
Joined: Sun Mar 07, 2021 11:15 pm
Location: Rio de Janeiro, Brazil

Re: Scrolling RPG maps

Post by zanto » Sat Apr 03, 2021 11:20 am

Pokun wrote:
Sat Apr 03, 2021 10:37 am
Also remember that VRAM increment mode is changed in $2000. It can be set to +1 (for horizontal nametable writes) or to +32 (for vertical nametable writes). So when you scroll horizontally you set it to +32 to update a character column and to +1 when scrolling vertically to update a character row, I guess. That way you might never need to change the VRAM address more than once per BG update.
I was reading there's a flag that makes it so that it increments to nametable address can be either +1 or +32. So, if your ROM has vertical mirroring, is it better to use the +32 increment and write in columns? And if so, if your map is RLE compressed, does that mean that you have to decompress the row every time to find each tile in the column? When I'm loading a screen (for example, the player just entered a new map) is it better to load all the screen into RAM before loading it into the nametable?

I think this is the only way to make it work considering in my case scrollx/scrolly can start at any part of the nametable depending on where the player is on the map when the screen loads

User avatar
Quietust
Posts: 1710
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Re: Scrolling RPG maps

Post by Quietust » Sat Apr 03, 2021 12:17 pm

zanto wrote:
Sat Apr 03, 2021 11:20 am
I was reading there's a flag that makes it so that it increments to nametable address can be either +1 or +32. So, if your ROM has vertical mirroring, is it better to use the +32 increment and write in columns? And if so, if your map is RLE compressed, does that mean that you have to decompress the row every time to find each tile in the column? When I'm loading a screen (for example, the player just entered a new map) is it better to load all the screen into RAM before loading it into the nametable?
You almost never want to be decoding your map data directly into VRAM, since decoding the data takes time - unless you want to turn off rendering (which you don't want to do for incremental updates), you've only got about 1700 cycles per frame during which you can safely write data to the PPU.
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.

Post Reply