It is currently Sun Jul 22, 2018 6:05 am

 All times are UTC - 7 hours

 Page 1 of 3 [ 43 posts ] Go to page 1, 2, 3  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: techniques for tracking world position?Posted: Fri Apr 28, 2017 8:20 am

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 416
Location: Central Illinois, USA
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?)

_________________
My games: http://www.bitethechili.com

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 8:25 am

Joined: Fri May 08, 2015 7:17 pm
Posts: 2155
Location: DIGDUG
Dont allow Y > 239. It's a simple subtract 240 from low byte. No division needed.

Changed my mind.

_________________
nesdoug.com -- blog/tutorial on programming for the NES

Last edited by dougeff on Fri Apr 28, 2017 9:21 pm, edited 1 time in total.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 8:34 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20283
Location: NE Indiana, USA (NTSC)
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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 8:46 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10616
Location: Rio de Janeiro - Brazil
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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 8:53 am

Joined: Sat Jan 09, 2016 9:21 pm
Posts: 416
Location: Central Illinois, USA
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)

_________________
My games: http://www.bitethechili.com

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 9:03 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10616
Location: Rio de Janeiro - Brazil
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!

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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 11:22 am

Joined: Tue Oct 06, 2015 10:16 am
Posts: 761
I'd just LUT the division, it's such a common operation.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 12:15 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10616
Location: Rio de Janeiro - Brazil
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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 12:23 pm

Joined: Mon May 27, 2013 9:40 am
Posts: 473
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.

_________________
http://www.mojontwins.com

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 12:24 pm

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7443
Location: Chexbres, VD, Switzerland
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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 1:53 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6425
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.)

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 2:05 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2155
Location: DIGDUG
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

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 2:14 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6425
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).

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 4:43 pm

Joined: Thu Mar 31, 2016 11:15 am
Posts: 318
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.

Top

 Post subject: Re: techniques for tracking world position?Posted: Fri Apr 28, 2017 7:18 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20283
Location: NE Indiana, USA (NTSC)
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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 3 [ 43 posts ] Go to page 1, 2, 3  Next

 All times are UTC - 7 hours

Who is online

Users browsing this forum: Pokun and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki