Map collision - NESdev BBS

Map collision
by ManicGenius on 2011-03-04 (#75117)

So I'm at the point with my game where I'm twiddlin' with the Ogmo Editor (customizable, check it out), and I'm thinking about how best to represent background tiles the player can collide with. I'm coming from a more modern programming background where I'm used to essentially having a separate "meta-map" storing the collision data for a map.

However, this doesn't seem as feasible on a limited system like the NES. Having 2 nametables worth of meta-collision data with my scheme would take roughly 60 bytes just to handle standard collision, but I'm prepping something to have flat, slope up, slope down, insta-death and water physics.

I'm kinda at the point where I'm thinking I'll just store a list of tiles instead referencing what properties they essentially have.

e.g.
#$01 = flat collision

I'm leaning that way so I use less RAM. Just wanna see what all you have done and any suggestions for doing something like this efficiently.

by 3gengames on 2011-03-04 (#75120)

Maybe have multiple tables of the background separate inside WRAM if you have it. You could have 4-bit per tile, then have XXYY where XX=Sloped/Not && how much. Then YY=Normal,Hard,Water,Death. Just my idea on how I'd do that. Takes RAM, But then you'd not have to run your insturctions through the PPU to read the background and is worth it IMO.

ETA:

If you don't put your tiles in ROM like Battle Kid (Only game I know that puts them in a specific way), then having those ranges would be easier because you could then use the top 6 bits to determine what type.

by qbradq on 2011-03-04 (#75123)

Many older games (like the Ultima series) establish tile ranges, and every tile within a particular range has a different function. An example range map might look like this:

Code:
$00 - $3f Collide, flat
$40 - $5f Collide, Slope Down Left
$60 - $7f Collide, Slope Down Right
$80 - $8f Liquid surface
$90 - $9f Liquid body
$a0 - $bf Hurts when Touched
$c0 - $df Instant Death
$e0 - $ff Background, do not collide

Then in your collision code you would detect when your objects enter the area of the tile, the use the tile's number (in a big if / else block) to figure out what to do.

A better approach might be to have a table in ROM that lists those attributes, then index that table with the tile number. It's a little bit slower but more flexable.

by tokumaru on 2011-03-04 (#75134)

qbradq wrote:
(in a big if / else block)

Jump tables plzkthx.

Seriously, don't EVER use big if / else blocks in 6502 assembly, specially for something that will be done several times per frame (like block type checks). In high level languages I think it's OK to do it, because as far as I know they get optimized to (tuh duh!) jump tables when compiled.

by Drag on 2011-03-04 (#75136)

tokumaru wrote:
qbradq wrote:
(in a big if / else block)

Jump tables plzkthx.

Seriously, don't EVER use big if / else blocks in 6502 assembly, specially for something that will be done several times per frame (like block type checks). In high level languages I think it's OK to do it, because as far as I know they get optimized to (tuh duh!) jump tables when compiled.

In high level languages, you'd use switch/case (a.k.a. "select case"), rather than a huge chain of if/else, and I think switch/case optimizes into a jump table.

But yes, jump tables are your BFFLs. In your example, you've defined each range to have at least $10 values to it, so I'd use the upper 4 bits of the tile byte as an index to a table of pointers, which point to the appropriate routines to handle collisions with those tiles. Since you're using 4 bits, you'd have 16 pointers, one for each set of 16 tiles.

To optimize it more, you could use the upper 3 bits instead for a smaller pointer table (8 pointers, 1 for each set of 32 tiles), if you don't mind performing another check in the liquid handler to determine whether it's surface or body.

by ManicGenius on 2011-03-04 (#75138)

3gengames wrote:
But then you'd not have to run your insturctions through the PPU to read the background and is worth it IMO.

As far as I know you don't really have to do that. Theres already a horizontal counter to figure out how far my dude is across my map, and the way I'm storing/compressing things makes it pretty easy to pick out what tile he's on straight out of ROM. WRAM isn't an option since I'm intending to get RetroUSB to produce this thing and to be honest... having any sort of extra features outside of CNROM/UNROM would jack the price up fairly bad.

by 3gengames on 2011-03-04 (#75139)

Ahhh...that is true. But just adding WRAM wouldn't be too much. Maybe $4 per chip or so. But I guess if you don't need it. If you used PRG-RAM and made an RPG, the extra cost might be justified.

by ManicGenius on 2011-03-05 (#75144)

Not just RAM though. Having that extra RAM requires a new mapper as well and that costs a couple extra bucks. Tack on cartridge shell, PCB, dust cover, label, manual, etc. it all adds up. So shaving off even just that $7 from the mapper and the RAM is intense at quantity. My game is just a simple platformer and I'm compressing the hell out of everything just so I can get the cheaper PRG chip. TBH, that's part of the reason I'm doing this in the first place. It's a challenge to work within constraints, and thus far more fun than cranking out an iPhone crapp for $0.99.

It's all scope though, and like you said, if I was doing an RPG the extra RAM would come in handy and would actually probably be a necessity to make any sort of interesting game.

by tepples on 2011-03-05 (#75149)

I imagine that even an RPG could use password save if it's railroaded enough that you could squeeze its persistent state between chapters down to 64 bits or fewer. For example, an 8-character password could record 32 bits of data and 8 bits of checksum, with the data split up as I described in this post. But you do need PRG RAM, serial EEPROM, or PRG flash if you want to save anything involving a large array, such as the overworld map in games like SimCity or Animal Crossing, or music that the player has written, or drawings in something like Drawn to Life or Mario Paint. I was working on something that was going to include small drawings by players like Drawn to Life, but I balked when I heard the high price of bunnyboy's SNROM equivalent.

Nintendo never made a board with UxROM/AxROM and battery save because it had already developed the replacement (MMC1 ASIC). But we currently have access only to 7400s and CPLDs, which AFAIK are more expensive than ASICs at the low volume of the modern NES era. So such a board would have the following parts list: PRG ROM, CIC, two 62256 SRAMs, 74HC20 for decoding, 74HC377 (like a 161 but also controlling the upper address lines of the RAMs), 74HC32 (can be omitted if you prefer mapper 7 instead of 2), battery, and various caps and diodes.