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
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: techniques for tracking world position?

Post by rainwarrior »

pubby wrote:Just shift right by 4 then divide by 15.
Ah, yes that's correct for divison!

Realizing I actually meant "modulo" and not division. Sometimes I forget that you don't necessarily get both from the same calculation. (Though there's probably a similar useful composition of modulos.)
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: techniques for tracking world position?

Post by pubby »

For modulo I'd probably just use repeated subtraction (along with 12.4 fixed point)

Code: Select all

.repeat 5, i
    cmp #15 * (%10000 >> i)
    bcc :+
    sbc #15  * (%10000 >> i)
:
.endrepeat
Takes about 25-30 cycles.
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: techniques for tracking world position?

Post by dougeff »

Edit. Removed. It's too late for me to do math.

Edit 2.

I'm starting to think that the data should be 256x256 sized rooms (16x16 tiles). You will only be displaying 256x240 at most, but the data should be the full 256 (16 tiles high). Then, no math required, except to figure out how to shift each room.

I retract my earlier response, pending more contemplation.
nesdoug.com -- blog/tutorial on programming for the NES
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 »

The problem is that having "dead zones" in your level map complicates physics and collisions. You have to constantly account for that phantom row when calculating distances, moving objects, and so on. Not to mention it can restrict your usage of metatiles larger than 16x16 pixels, since they'll have part of them cut off when used at the bottom of a room. That's a world of little things I'd rather not worry about. Your solution does help with attribute handling though, I'll give you that!

Being a huge fan of the MVC model of software development, I consider it poor form to let hardware aspects influence the architecture of your game worlds as much as this (i.e. pretending parts of your level map don't exist). IMO, having 2 separate anchors, one for the model and another one for the view is a much classier and hardware-agnostic solution, but to each his own.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: techniques for tracking world position?

Post by Oziphantom »

This all comes down to
How do you store your levels?
How do you need your objects to behave?
What is the game?

Do you care if an enemy resets once it goes off screen?
Do your levels mostly follow 1 direction but you swing out to the other direction, I.e Mario 3 is mostly L and R but you can go up and down, Radian is mostly U and D but you can scroll L and R a bit?
In those cases you can store all your entities in an array from L to R. Then you keep a Head and Tail index. And each ent def holds a number of chars till next ent.
so
Type 00,14,02,05
Dist 00,05,04,01
So this way you add active entities from the Head, and when Tail moves over one, you remove the entity from being active( unless your entities can move and follow you across screens, like a boo for example at which point you only cull them once they are "out of screen" where out of screen might be screen size + extra)
If you count Chars or Blocks or Screens is up to the game design.
Which is basically the Anchor system tokumaru mentions but you have a Left Anchor and Right Anchor portion to the "window" rather than just a start.

Once you have entities you keep them in Screen Space, and cull as needed. If you are moving Left then you spawn the new enemy off screen on the L, if you are moving R you spawn them off screen on the R, so you don't need to work out where they are, no maths ;) For speed you can keep a OnScreen List and then a OffScreenButActiveList, the first gets full update and animation, the 2nd gets position only and no animation logic, you can also if your system handles it lower their update and collision rate to keep the frame rate rolling.

For something like Gauntlet that won't work, and you start to get into a Quad Tree like activation zone tables, or you carve up things in to large blocks and then add to a active block list, then you keep indexes into the position of those blocks, updating the list as you cross block boundaries.

Or you go with "volumes"/"zones" where you place down some special chars, or an AABB list that you can quickly detect against. Then you put triggers on the zones, so when the player enters the Zone, you spawn A,B,C and X,Y,Z etc then as the player moves around they enter the volumes/zones and that controls what objects are made. Used in things like RPGs where you have doors and towns and save points etc
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: techniques for tracking world position?

Post by calima »

rainwarrior wrote:
pubby wrote:Just shift right by 4 then divide by 15.
Ah, yes that's correct for divison!
Yup, and if your Y coord doesn't go above 4096, then you can use a simple LUT for the div-by-15. Otherwise a binary search or the wiki's decomposition.
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: techniques for tracking world position?

Post by dougeff »

The problem is that having "dead zones" in your level map
I think you misunderstood me. In my concept of 256x256 'rooms'...that is just how the data is stored. The screen is only 256x240, so if you're in the top most of the top 'room' the bottom is cut off. But if you start scrolling down, you see it. Nothing is 'dead zone'.

I'm thinking of a top-down all-direction game like Crystalis.

I almost feel like slapping together a demo, but I don't have time.
nesdoug.com -- blog/tutorial on programming for the NES
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 »

Sorry, I completely misread what you wrote. I agree with you on levels built of 256x256-pixel screens/blocks/whatever, but then we're back to the original problem of finding the equivalent position of a block from the level map in screen space. The problem of "figuring out how to shift each room" is what can be solved either by a division by 240 (or 15) or the use of 2 synchronized anchors for the camera.
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 »

Not to mention it can restrict your usage of metatiles larger than 16x16 pixels, since they'll have part of them cut off when used at the bottom of a room.
Actually Castlevania III does that with it's vertical scrolling screen. It seems to work fine. Mega Man games does that too but the verticall scroll is only "quick" scroll without gameplay.
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.)
I was going to write something, but then I undersood it would be better if whoever whants to implement that actually understood everything. In particular, it depends on many screen heigh you have in total. When supporting a heigh of up to 16 screens for instance, doing modulo is as simple as substracting 240*8, 240*4, 240*2 and 240 to a 16-bit integer whenever doing so will not result in a negative number. Quite simple really.

The trick to first shift right by 4 is clever, I didn't think about that. Does it work for modulo too, or only for division ? If the initial value fits in 12-bits then it's definitely a must, as it will save the substracting the hassle of doing it on 16-bit values, and doing it on a value that fits in the A register will lead to much shorter/faster simpler code. However, if the scroll values do not fit in 12 bit anyway, it's not worth it as it will not simplify the division operation itself.
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 »

You can do mod 240 by shifting right by 4, reducing mod 15, shifting left by 4, and taking the 4 bits from the original value.

Or assuming Python 3 division semantics, where // rounds toward negative infinity:

Code: Select all

def mod_240(x):
    return (x % 16) + ((x // 16) % 15) * 16
Or in 6502 (untested):

Code: Select all

.proc get_camera_y_mod_240
  tmp0 = $0000

  ; Load camera_y bits 11-4 into A
  lda camera_y_lo
  asl a
  sta tmp0
  lda camera_y_hi
  rol a
  asl tmp0
  rol a
  asl tmp0
  rol a
  asl tmp0
  rol a
  
  cmp #240
  bcc lt240
    sbc #240
    bcs not30
  lt240:

  cmp #120
  bcc lt120
    sbc #120
  lt120:

  cmp #60
  bcc lt60
    sbc #60
  lt120:

  cmp #30
  bcc lt30
    sbc #30
  lt30:

  cmp #15
  bcc lt15
    sbc #15
  lt15:

  ; Now that we're under $0F, shift that to the high nibble
  asl a
  asl a
  asl a
  asl a
  eor camera_y_lo
  and #$F0  ; keep upper 4 bits; take lower 4bits from camera_y_lo
  eor camera_y_lo

  rts
.endproc
But with all the shifting I'm not sure if this'd be faster than a mod 240 that uses 16-bit arithmetic.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: techniques for tracking world position?

Post by Sumez »

There's a really good algorithm in the thread tokumaru already linked. I'm using a technique very similar to it in my own engine, and as tokumaru also points out in that thread, it's not really bad to just call that once per frame (which makes my code feel more solid than trying to constantly sync up two variables).

I still do keep pixel scrolling and nametable variables separately, of course. It helps that my collision map is stored completely independent from my nametable map (even if they seem very closely related), as 2-bit values stored in groups of 16x16 tiles (= 256x256px). I pretend like the missing rows don't exist for everything other than loading in nametables, and it's working fine for me.
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 »

Sumez wrote:There's a really good algorithm in the thread tokumaru already linked. I'm using a technique very similar to it in my own engine, and as tokumaru also points out in that thread, it's not really bad to just call that once per frame (which makes my code feel more solid than trying to constantly sync up two variables).
So basically, this thread is an exact duplicate of that thread, everything that has been discussed here had already been discussed there, and this was a complete waste of time of ours. Why don't people use the search function.
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 »

Bregalad wrote:So basically, this thread is an exact duplicate of that thread, everything that has been discussed here had already been discussed there, and this was a complete waste of time of ours. Why don't people use the search function.
I attempted a search but didn't find anything. Probably more attempts with different search terms would have found it eventually, but I had no way of knowing whether or not such a thread existed.

I don't think it's really a waste of time to have a similar discussion 10 years later...
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: techniques for tracking world position?

Post by Sumez »

Agreed, this is an extremely relevant issue for any games wanting to do vertical scrolling on the NES, so it shouldn't necessarily be hidden away in a 10 year old archive. In fact this is a subject that could easily warrant an entire wiki article.

The title of the old thread doesn't exactly make it easy to find either. You need to pinpoint the exact problem (which can be really hard to envision until you're already knee deep) and figure division by 15 is actually a solution for that problem (which works for me, but the repeated suggestion of synchornizing two individual values is just as good to me).
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 »

Sumez wrote:Agreed, this is an extremely relevant issue for any games wanting to do vertical scrolling on the NES, so it shouldn't necessarily be hidden away in a 10 year old archive.
As opposed to the WWWthreads board datings from before the 2004 switch, it's not an archive, it's the same message board as here.
The title of the old thread doesn't exactly make it easy to find either.
Indeed, neither is the title of this very thread.
I attempted a search but didn't find anything. Probably more attempts with different search terms would have found it eventually, but I had no way of knowing whether or not such a thread existed.
Alas, the search function is indeed weak, one single misspellings and the results collapse to none.
Post Reply