nesdev.com
http://forums.nesdev.com/

techniques for tracking world position?
http://forums.nesdev.com/viewtopic.php?f=2&t=15871
Page 1 of 3

Author:  gauauu [ Fri Apr 28, 2017 8:20 am ]
Post subject:  techniques for tracking world position?

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?)

Author:  dougeff [ Fri Apr 28, 2017 8:25 am ]
Post subject:  Re: techniques for tracking world position?

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

Changed my mind.

Author:  tepples [ Fri Apr 28, 2017 8:34 am ]
Post subject:  Re: techniques for tracking world position?

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.

Author:  tokumaru [ Fri Apr 28, 2017 8:46 am ]
Post subject:  Re: techniques for tracking world position?

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.

Author:  gauauu [ Fri Apr 28, 2017 8:53 am ]
Post subject:  Re: techniques for tracking world position?

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)

Author:  tokumaru [ Fri Apr 28, 2017 9:03 am ]
Post subject:  Re: techniques for tracking world position?

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.

Author:  calima [ Fri Apr 28, 2017 11:22 am ]
Post subject:  Re: techniques for tracking world position?

I'd just LUT the division, it's such a common operation.

Author:  tokumaru [ Fri Apr 28, 2017 12:15 pm ]
Post subject:  Re: techniques for tracking world position?

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.

Author:  na_th_an [ Fri Apr 28, 2017 12:23 pm ]
Post subject:  Re: techniques for tracking world position?

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:
   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.

Author:  Bregalad [ Fri Apr 28, 2017 12:24 pm ]
Post subject:  Re: techniques for tracking world position?

Division of a variable by a constant, in particular a divion of a variable by 240, is extremely simple and reasonably fast to do on a 6502.

I still think tokumaru's solution is better, but this is the second best.

Author:  rainwarrior [ Fri Apr 28, 2017 1:53 pm ]
Post subject:  Re: techniques for tracking world position?

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.)

Author:  dougeff [ Fri Apr 28, 2017 2:05 pm ]
Post subject:  Re: techniques for tracking world position?

Do you mean this one...

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


(unrelated multiplication routine also here)
http://6502org.wikidot.com/software-math-intmul

Author:  rainwarrior [ Fri Apr 28, 2017 2:14 pm ]
Post subject:  Re: techniques for tracking world position?

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).

Author:  pubby [ Fri Apr 28, 2017 4:43 pm ]
Post subject:  Re: techniques for tracking world position?

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.

Author:  tepples [ Fri Apr 28, 2017 7:18 pm ]
Post subject:  Re: techniques for tracking world position?

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.

Page 1 of 3 All times are UTC - 7 hours
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/