This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

level object coordinates trick

level object coordinates trick
by on (#107844)
I've heard that some NES games used subpixel coordinates in the format where the per-pixel coordinate is shifted by 4 bits, and the low 4-bits are subpixels. If 2 bytes are used for the coordinates, levels are limited to being up to 16 screens long.

A trick to having longer levels that I came up with, is to have a small level collision map buffer in ram, and have it "wrap" as the player advances, so that a level can be longer than 16 screens in legnth, without resorting to using 3rd byte.

Is this a new trick, or was it already used a long time ago, and I just didn't think about it until now?

EDIT: Fixed poor wording.
Re: level object coordinates trick
by on (#107846)
Quote:
I've heard that some NES games used subpixel coordinates in the format where the per-pixel coordinate is shifted by 4 bits, and the low 4-bits are subpixels. If 2 bytes are used for the coordinates, levels are limited to being up to 16 screens long.

A trick is to have a small level collision map buffer in ram, and have it "wrap" as the player advances, so that a level can be longer than 16 screens in legnth.

Is this a new trick, or was it already used a long time ago, and I just didn't think about it until now?

I don't think it's too new. I do something a little similar. My subpixels for X and Y are stored in one byte.

00XXXYYY. (I only have eight degrees of precision, not 16. The other two bits are used for something else.
I have a small 2x2 screen collision map in RAM, and my collision routine only uses the lowest bit of the sprite's high byte to check where it is in this map. It copies in 2 new vertical screens when I scroll horizontally passed a border, and vice versa.

By how you're looking at things, my map size is limited to 2 screens per axis, but it could really be any size. My method still uses 19 bits per axis, even if 7 bits are ignored for a lot of things. If I wanted to, I could use 12 bits per axis. Your method (a fractional element of 16) could use 13 bits per axis. (4 bits for fractional element+8bits for low byte+1bit for high byte) Edit2: Well, I guess you could also use 3 more bits just to get more screens in the window. But there will only be the border between two screens per axis displayed at once on NES, so I see no point to allocate RAM to more than 2 screens.

I guess the difference between my method and your method is that I still store the entire high byte of each axis. I just don't need or use 7 bits of it for collisions. But those 7 bits are useful for other things that aren't background collisions.

Edit: Also, I don't store my subpixels with half of my low byte, because subpixel precision for collisions doesn't matter to me.
Re: level object coordinates trick
by on (#107847)
Scrolling the nametable itself works similarly. Scrolling coordinates are only 8 bits for each axis, which scrolls around up to four screens, and to the player looks like you're scrolling over a large level made up of tens of screens. I imagine it like one of those lamps with a circular shade that rotates.

Another way to deal with the coordinate issue is to keep the fraction in a separate byte, since it's not needed when checking for collisions, just when applying an object's velocity once each frame. This gives you the full 64K coordinate space in the main two bytes. It also means that you don't need to keep fractions on all objects, just those that have more involved physics. This way collisions are easy between fractional and non-fractional objects. It doesn't really seem issue if it's not cleared when the player is forced to a position, like when landing on a floor, so this is further lack of a need to adjust the fraction byte in most cases.
Re: level object coordinates trick
by on (#107848)
psycopathicteen wrote:
A trick is to have a small level collision map buffer in ram, and have it "wrap" as the player advances, so that a level can be longer than 16 screens in legnth.

This 2-screen sliding window of decompressed level data dates back to SMB1. But there are a few tradeoffs about destructibility if you're attempting bidirectional scrolling on the NES without using extra PRG RAM. Maps like WORLD 1-2 are why you can't go backward in SMB1.
Re: level object coordinates trick
by on (#107851)
blargg wrote:
Another way to deal with the coordinate issue is to keep the fraction in a separate byte, since it's not needed when checking for collisions, just when applying an object's velocity once each frame. This gives you the full 64K coordinate space in the main two bytes. It also means that you don't need to keep fractions on all objects, just those that have more involved physics. This way collisions are easy between fractional and non-fractional objects.

My approach exactly. Packing coordinate bits into 2 bytes doesn't even save you that much RAM, so I'd much rather use 3 bytes per coordinate (2 for the integer part + 1 for the fractional part) and not have to worry about complex bit layouts.
Re: level object coordinates trick
by on (#107852)
Oh yeah right, you don't have to do a two-byte-shift to get the pixel coordinates, e.g. when moving sprites.
Re: level object coordinates trick
by on (#107853)
tokumaru wrote:
blargg wrote:
Another way to deal with the coordinate issue is to keep the fraction in a separate byte, since it's not needed when checking for collisions, just when applying an object's velocity once each frame. This gives you the full 64K coordinate space in the main two bytes. It also means that you don't need to keep fractions on all objects, just those that have more involved physics. This way collisions are easy between fractional and non-fractional objects.

My approach exactly. Packing coordinate bits into 2 bytes doesn't even save you that much RAM, so I'd much rather use 3 bytes per coordinate (2 for the integer part + 1 for the fractional part) and not have to worry about complex bit layouts.


This is the way I usually do it too, but I do see a few benefits of switching to the "2 byte method" when it comes to the SNES:

-All coordinates are word size
-Tile collision address calculation is much simpler

Quote:
00XXXYYY. (I only have eight degrees of precision, not 16. The other two bits are used for something else.


Doesn't that approach kind've overcomplicates things?
Re: level object coordinates trick
by on (#107865)
Quote:
Quote:
00XXXYYY. (I only have eight degrees of precision, not 16. The other two bits are used for something else.

Doesn't that approach kind've overcomplicates things?

A little, but I lose very little time every frame for the savings as opposed to similar methods that use the same amount of RAM. There are reasons why I use 8 subpixels instead of 16 and other stuff, but it feels like it'd be off topic. There's a method to the madness, I promise!

What you're suggesting (at least for NES), is sort of a similar thing. You could just use three bytes like blargg and tokumaru suggested, and it'd be much simpler.
Re: level object coordinates trick
by on (#107881)
Another way of thinking of the separate fraction byte is as a form of a timer to move a whole pixel from the object's position every once in a while. Adding a fraction to it every frame has a similar effect to counting down and moving an extra pixel when it reaches 0. So in this respect, it's an implementation detail of the particular object. All the high-level collision/sprite system sees is its whole pixel movements, since that's all that matters.
Re: level object coordinates trick
by on (#107889)
What kind of coordinate systems did people usually use for the Sega Genesis. At first glance it looks like the 68000 can benefeit from using 32-bit registers, but then you realize that you can't manipulate the individual bytes that make up the register, without shifting or loading to memory, neither of which the 68000 is good at.
Re: level object coordinates trick
by on (#107892)
psycopathicteen wrote:
What kind of coordinate systems did people usually use for the Sega Genesis.

IIRC from the Sonic Physics Guide, object coordinates are 16 bits, with 8 extra bits for the fractional part, at least in all main Sonic games.
Re: level object coordinates trick
by on (#107896)
tokumaru wrote:
psycopathicteen wrote:
What kind of coordinate systems did people usually use for the Sega Genesis.

IIRC from the Sonic Physics Guide, object coordinates are 16 bits, with 8 extra bits for the fractional part, at least in all main Sonic games.


Do you know if the fractional byte is in the same register as the coordinates, or does the fractional byte have it's own register?
Re: level object coordinates trick
by on (#107910)
On 68K the easiest thing to do is to use 16.16 as you can use SWAP to separate fraction and whole. Lot less headache around code too. I am more than certain a lot of games use that way. Anything involving 8 bits is not too efficient on 68K, as 8 bits take as many cycles as 16 bits, but only processes half the data.
Re: level object coordinates trick
by on (#107916)
Actually I think the most common method is to just store the coordinates as integers directly and fake subpixel accuracy where really needed.
Re: level object coordinates trick
by on (#107920)
Interesting, what are ways of faking subpixel accuracy without subpixels? Note that a "add a pixel evern N frames" is subpixel, it's just using a "reciprocal" approach for storing the fraction (1/n instead of n/(2^b)).
Re: level object coordinates trick
by on (#107921)
TmEE wrote:
On 68K the easiest thing to do is to use 16.16 as you can use SWAP to separate fraction and whole. Lot less headache around code too. I am more than certain a lot of games use that way. Anything involving 8 bits is not too efficient on 68K, as 8 bits take as many cycles as 16 bits, but only processes half the data.


I didn't know the 68k had a SWAP instruction. Now all the fuss about 32-bit registers are starting to make more sense to me.
Re: level object coordinates trick
by on (#107924)
blargg wrote:
Interesting, what are ways of faking subpixel accuracy without subpixels? Note that a "add a pixel evern N frames" is subpixel, it's just using a "reciprocal" approach for storing the fraction (1/n instead of n/(2^b)).

GalaxyNES does what I'd call faked subpixel accuracy (in a way that I think is silly, now. But I didn't know any better.) It allows speeds of less than 1 pixel per frame for every object, but the objects don't store subpixels at all. That said, it still does use a timer so it may fit into your description.

The game has a timer that counts from 0-7. (Or 7 to 0. I forget and it doesn't really matter.)

Objects have a speed byte. They move (speed/8) pixels every frame. In addition, they move a pixel every frame that the lowest three bits of the speed (-1) are greater than or equal to the timer. (if the lowest three bits are 0, it doesn't do this.)

So for a speed of 1, the lowest three bits minus 1 is 0. So when the timer is 7-1, the object moves 1/8, so 0. When the timer is 0, it will move one pixel, because 1-1 >= 0.

So all objects with a speed of one will move one pixel on the same frame, regardless of when they started moving. Objects with a speed of 9 and 17 will move their "extra pixel" on the same frame every time.

This method also results in uneven speeds. An object with a speed of 4 will move 1 pixel 4 frames in a row, then not move 4 frames in a row. You'd expect the object to move every other frame in this case.
Re: level object coordinates trick
by on (#107926)
blargg wrote:
Interesting, what are ways of faking subpixel accuracy without subpixels? Note that a "add a pixel evern N frames" is subpixel, it's just using a "reciprocal" approach for storing the fraction (1/n instead of n/(2^b)).

There's the method described in the above post, but swap the bit order (which will actually fix the uneven speed issue).

Basically, let's suppose you store coordinates as 16-bit integer values, and you store speeds as 8.8 fixed comma values. Then you also have an 8-bit timer that's constantly counting up (this is global, would affect everything in the game).

What you would do is to take the speed value as a 16-bit integer, then add the value of the timer - bit with the bits reversed (i.e. bit 0 becomes bit 7, bit 1 becomes bit 6, etc.). Then just take the higher byte and add it to the coordinates as a normal integer.

As for reversing the bits order, well, I don't know much about the 6502, but the idea would be like this:
  • Set A to the value of the 8-bit timer
  • Set B to 0
  • Shift left A
  • Shift right B with carry
  • Shift left A
  • Shift right B with carry
  • Shift left A
  • Shift right B with carry
  • Etc.
Every time you perform those two steps (the two shifts) you're moving a bit. You can try pushing in all bits, but most likely you'll be able to get away with less (e.g. 4 bits may be more than enough for your average platformer). Also you only need to do this once per frame - store the result from B in RAM then reuse it for the rest of the frame.

psycopathicteen wrote:
I didn't know the 68k had a SWAP instruction. Now all the fuss about 32-bit registers are starting to make more sense to me.

32-bit registers were the most useful in practice in most games is in having more room for calculations, especially anything that's bound to overflow with 16-bit. That makes programming a lot easier.

EDIT: er, removed something huge because it went too off-topic. Will just PM him.
Re: level object coordinates trick
by on (#107961)
My upcomming project uses coordinates in 16.8 format, and velocity vectors in signed 8.8 format.

Code:
update_object_position:
lda !y_velocity
bpl positive_y_velocity
dec !y_position_hi
positive_y_velocity:
clc
adc !y_position_subpixel
sta !y_position_subpixel
bcc dont_increment_y_hi
inc !y_position_hi
dont_increment_y_hi:
lda !x_velocity
bpl positive_x_velocity
dec !x_position_hi
positive_x_velocity:
clc
adc !x_position_subpixel
sta !x_position_subpixel
bcc dont_increment_x_hi
inc !x_position_hi
dont_increment_x_hi:
rts