techniques for tracking world position?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

techniques for tracking world position?

Post by gauauu »

For large scrolling games that include vertical scroll, how do you all handle keeping track of the world position of objects?

I was originally thinking I'd just use 2-byte values for position (worldX, worldY), and just track position relative to the whole large level. But I keep finding myself wanting/needing to divide by 240 when translating from world coordinates to screen coordinates, which is a pretty slow operation (unless somebody knows a math trick that I haven't thought of?)

I'm now wondering if I should instead think in terms of discrete screens, so I instead track which screen I'm on as well as X,Y position within that room. So each level would logically made up of many screens, and I only have to keep track of the player's position within the screen (which I believe is how metroid handles it?). It seems like this way I'll use a lot more ram tracking every object's screen as well as position within the screen, and have to do more bookkeeping dealing with moving between screens.

I'm curious if you folks with more experience have ideas of the pros and cons of both ways of handling it (or are there other techniques I haven't thought of?)
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: techniques for tracking world position?

Post by dougeff »

Dont allow Y > 239. It's a simple subtract 240 from low byte. No division needed.

Changed my mind.
Last edited by dougeff on Fri Apr 28, 2017 9:21 pm, edited 1 time in total.
nesdoug.com -- blog/tutorial on programming for the NES
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: techniques for tracking world position?

Post by tepples »

Not using values 240-255 for the lower byte of the Y coordinate complicates collision between objects near the bottom of one "screen" and objects on the "screen" below it.

Tokumaru had an idea of making hardware screen coordinates separate in some way.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: techniques for tracking world position?

Post by tokumaru »

gauauu wrote:But I keep finding myself wanting/needing to divide by 240 when translating from world coordinates to screen coordinates, which is a pretty slow operation (unless somebody knows a math trick that I haven't thought of?)
I used to have the exact same problem back when insisted on having fixed synchronization between world coordinates and screen coordinates, and I solved this by using dynamic synchronization instead.

I basically have a CameraY variable which's in world coordinates, and an NTCameraY variable in screen coordinates. Whenever the camera moves, both coordinates are updated by the same amount, and NTCameraY has some extra logic to skip values 240-255. All operations are then relative to these coordinates, and there's no hardcoded synchronization between the level and the screen. If for example I need to render a new column of metatiles, I'll use CameraY to calculate the column's source address in the level map, but I'll use NTCamaraY to calculate the target VRAM address for the column.

The link between world space and screen space is created by giving each one its own anchor, so that the relationship between everything else and the anchors is the same, regardless of the absolute position of each anchor. I hope I'm getting the idea across.

In theory you could do the same in the X axis and make world and screen spaces completely independent, but there's little reason to do that when the name table has such a nice width as 256 and you can save some time by using a single coordinate for both spaces.
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

Re: techniques for tracking world position?

Post by gauauu »

dougeff wrote:Dont allow Y > 239. It's a simple subtract 240 from low byte. No division needed.
Yeah, that was my thinking with option #2 that I mentioned above
tepples wrote:Not using values 240-255 for the lower byte of the Y coordinate complicates collision between objects near the bottom of one "screen" and objects on the "screen" below it.
And that was one of the bookkeeping issues that I was referring to.
tokumaru wrote:The link between world space and screen space is created by giving each one its own anchor, so that the relationship between everything else and the anchors is the same, regardless of the absolute position of each anchor. I hope I'm getting the idea across.
Absolutely. This is the solution I started mulling around in my head after posting this. I had gotten as far in my head as having a camera anchor, but hadn't worked out whether I needed a separate anchor for each object, or if they could somehow reuse the relative distance between the world camera and NT camera anchor. (Which really I guess is just a tradeoff of RAM vs CPU time)
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: techniques for tracking world position?

Post by tokumaru »

Just for fun, here's my post from 2007 when I was trying to solve the same problem: viewtopic.php?f=2&t=3230

I'm kinda surprised to realize after all these years that the solution was given to me by someone else (dvdmth)... I always thought I had the idea myself! :oops:
gauauu wrote:This is the solution I started mulling around in my head after posting this. I had gotten as far in my head as having a camera anchor, but hadn't worked out whether I needed a separate anchor for each object, or if they could somehow reuse the relative distance between the world camera and NT camera anchor. (Which really I guess is just a tradeoff of RAM vs CPU time)
You just need two anchors, one for everything dealing with the game world (objects, collisions, level map) and another one for dealing with the name tables (setting the scroll through $2000/5 and updating VRAM through $2006/7). The idea is that each anchor marks the same point (i.e. the top of the camera) in their own space, so a block that's, say, 5 blocks below the world space anchor, will be rendered 5 blocks below the NT space anchor. As long as the relative distance to the anchors is the same, you get all the synchronization you need.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: techniques for tracking world position?

Post by calima »

I'd just LUT the division, it's such a common operation.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: techniques for tracking world position?

Post by tokumaru »

I don't see why you'd use a LUT for something you can have ready at all times at no performance cost, but that's just me.

Unless you don't understand the other possible solutions well enough, in which case I can understand a programmer using something they're more comfortable with even if it's not optimal. I'm definitely like that, sometimes people here (tepples, mostly) come up with crazy ass algorithms that are faster/smaller than those I can come up with, but I don't use anything I don't fully understand. At least when it comes to NES programming, with more modern stuff I can tolerate a moderate amount of blackboxing.
Last edited by tokumaru on Fri Apr 28, 2017 12:41 pm, edited 1 time in total.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: techniques for tracking world position?

Post by na_th_an »

I use "logical" 256x256 pixels screens and separate screen logics when I do vertical scrolling. It's just a matter of updating both things (level position and screen position) as you scroll. That way you can use byte coordinates and rely on just a circular collision buffer (mine is 256 bytes big as metatiles are 16x16).

A simple situation, when the engine just scroll upwards "pixels" pixels, I just...

Code: Select all

	scroll_y -= pixels;
	if (scroll_y < 0) scroll_y += 480;
	scroll (0, scroll_y);

	cam_pos -= pixels;
	cam_pos_lsb = LSB (cam_pos);
cam_pos is world-coordinates. scroll_y is screen coordinates. To keep them synchronized, you just update both at the same time.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: techniques for tracking world position?

Post by Bregalad »

User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: techniques for tracking world position?

Post by rainwarrior »

Did someone write a 16-bit division by 240 routine? (I don't see one in the reference you linked, but it would probably be good to have one around.)
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: techniques for tracking world position?

Post by dougeff »

Do you mean this one...

http://6502org.wikidot.com/software-math-intdiv


(unrelated multiplication routine also here)
http://6502org.wikidot.com/software-math-intmul
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: techniques for tracking world position?

Post by rainwarrior »

dougeff wrote:Do you mean this one...
No, I didn't mean generic division routines, I meant one optimized for division by a constant 240. Though, you can apply the technique on the wiki page bregalad linked, I was just wondering if someone had already worked one out for 240, like the others in Omegamatrix's thread (linked in that wiki article).
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: techniques for tracking world position?

Post by pubby »

Just shift right by 4 then divide by 15.

Pro tip: Store y-values in fixed-point format with the lowest 4 bits as the fractional component. This simplifies a ton of nametable operations, among other things. For x-values, use a whole byte for the fractional component.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: techniques for tracking world position?

Post by tepples »

One practical problem with 12.4 fixed point, where 16 units represent one pixel, is that your objects' diameters are closer to 256. This means you have to maintain 16-bit precision throughout more of your collision detection.
Post Reply