Best way to generate bkg collision data?

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Post Reply
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Best way to generate bkg collision data?

Post by JoeGtake2 » Fri Jul 11, 2014 11:13 am

I've been reading many posts on the subject today and have plenty of good ideas. I completely understand the concept of creating essentially a grid of (16x16) metatiles and dividing by 16 to determine an object's position relative to that grid (or dividing by 32, for instance, to get the object's position relative to each tile)...this is essentially how I've done collision detection in several environments, so I get the core concept just fine). Most posts seem to suggest that a new attribute table is generated...sort of a collision map... to handle each of the four tiles' type and 'solidity', and then reading from that table and comparing it to an object's position to determine the result.

Originally, my concept was to assign each tile number an attribute (or maybe rows of tiles an attribute ... $0-$0F= walkable, $10-$4F = solid, etc...) then use the grid position to determine what 'tile' was in the player's position to handle the result.

I am not sure what the most efficient way to handle this data would be. I know that the former would allow for more diversity while the latter seems might be easier to implement? But aside from that - I'm not completely sure the best way to store this data (something similar to loading nametable, perhaps?) or the best way to actually find the character's grid position (I can do this easily with multiplication and division in other environments, but trying to figure out the most efficient way to do it in ASM).

I have found a few methods. Are there any you guys would suggest? (for right now, simple top down engine, no screen scrolling).

Thanks!

User avatar
tokumaru
Posts: 11894
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Best way to generate bkg collision data?

Post by tokumaru » Fri Jul 11, 2014 1:54 pm

Hardwiring any kind of attribute to tile/block numbers is useful if you have a limited amount of ROM, otherwise it's a useless restriction you're imposing on yourself. If you have the ROM space, I really suggest you make everything as explicit as possible, so you have more freedom to create unique levels. I'd only suggest the use of implied attributes if you were coding a game for a competition that required ROMs to be some small arbitrary size (e.g. 8KB) or a game with a large number of levels in 32KB or PRG-ROM or less.

Collision data in particular is often associated with metatiles. Very few games recognize individual tiles as entities of the level, tiles are almost exclusively a graphical element used to represent a portion of a metatile. That's probably because without an MMC5 the NES is unable to color individual tiles arbitrarily, so it makes sense to always process them in groups of 2x2, and that includes collisions.

One advantage of making the collision data part of the metatiles' attributes is that you can use the same code that decodes the level map to the screen to read the collision data. If you had a separate grid for collisions somewhere else you'd probably need different logic to access it.

Keep in mind that even if your collision data is arranged as a grid of 16x16-pixel blocks, you can have finer collision resolution if you store more than "solid" or "empty" for each block. Slopes for example are often done by specifying the height of each of the 16 columns in the block.

Since you don't seem to be working with metatiles yet, only (compressed?) name/attribute table data, and you don't scroll, maybe you'd benefit from a separate collision map for each screen. First you have to decide how many solidity states you have. If it's just "solid" vs. "empty", 1 bit per block will do. If you have to include "water", "hazard", and so on you'll obviously need more bits per block. Once you have figured out how many states you'll need, you have to group the bits into bytes and arrange them in a 2D array.

For example, if you have 4 solidity states you need 2 bits per block, meaning that 1 byte can hold the attributes of 4 blocks. If the collision blocks are 16x16 pixels, each screen has 16x15 = 240 blocks. Divided by 4 in each byte that's 60 bytes of collision date per screen.

You can manually define this data with .db statements, like this:

Code: Select all

Screen00Collision:
	.db %00000000, %00000000, %00000000, %00000000 ;1st row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;2nd row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;3rd row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;4th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;5th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;6th row of collision blocks
	.db %00000000, %00000000, %00111111, %11000000 ;7th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;8th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;9th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;10th row of collision blocks
	.db %00000000, %00000000, %00000000, %00000000 ;11th row of collision blocks
	.db %11111111, %11111111, %11110000, %11111111 ;12th row of collision blocks
	.db %11111111, %11111111, %11110000, %11111111 ;13th row of collision blocks
	.db %11111111, %11111111, %11110000, %11111111 ;14th row of collision blocks
	.db %11111111, %11111111, %11110000, %11111111 ;15th row of collision blocks
Here I have used 00 = empty and 11 = solid to make the data easy to visualize. Like with level maps, you'll want to use a pointer to indicate the active collision map, so you can easily read from it at any time. Then you just need some simple math to convert pixel coordinates into an index into this table:

Code: Select all

ByteIndex = (PixelY / 16) * 4 + (PixelX / 64);
In assembly this can be done with bit shifting and masking. Just put the result in Y and you can load the correct byte with LDA (CollisionMapPointer), Y. This will get you the collision data for 4 consecutive blocks, so you still have to select one out of these 4 blocks. You'll need another formula:

Code: Select all

BlockIndex = (PixelX / 16) AND 3
The purpose of "AND 3" is to keep only the lower 2 bits of the result, since 3 in binary is %00000011. With this information in hand you can shift the collision byte right as many times as necessary (index 0: shit 6 times, index 1: shift 4 times, index 2: shift twice, index 3: don't shift) and mask away the upper 6 bits to get a value between 0 and 3 that will identify the solidity state of the block at the coordinate you checked.

This is the absolute simplest way to arrange/access collision data I can think of.

Celius
Posts: 2157
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Re: Best way to generate bkg collision data?

Post by Celius » Fri Jul 11, 2014 2:36 pm

Depending on your level/map structure, you might end up making multiple layers of metatiles. In my game, the level screens are made of 52 8x2 metatiles, which are actually sets of 4 2x2 metatiles (the game scrolls only horizontally, and has a status bar 4 tiles tall). 5 bytes go into defining the 8x2 metatile: 4 for the IDs of the 2x2 tiles, and 1 for the color attributes of the tiles (2 bits for each 2x2 tile). 5 bytes define the 2x2 metatiles: 4 for the IDs of the actual 8x8 pixel tiles, and 1 for the tile "type". The "type" indicates whether or not its solid, liquid, hazardous, etc.

Like tokumaru said, when I'm decompressing the level map down to the 8x8 pixel tile level, I can grab the tile type and put it into RAM. I use 2 pages of RAM to house the collision data for a rolling 2-screen window of level data. It gets updated as the screen scrolls. This makes collision detection very easy.

The downside to this approach is that to keep the same graphic for a 2x2 tile but have it behave differently, you have to define a new 2x2 tile and make it a different type. 5 bytes is a small sacrifice, but depending on the complexity of your levels, sacrificing one of the available 2x2 tile IDs might be more of a problem.

JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Best way to generate bkg collision data?

Post by JoeGtake2 » Fri Jul 11, 2014 3:03 pm

I've actually been considering developing a tool to create collision map data eventually, I just want to be sure I can get it working before I go down that road.

I appreciate the response. I'm still having a hard time understanding the use of a pointer. With your help, I was able to implement a pointer for nametable data, but I'm still confused how to implement one for this purpose.

I completely get the screen collision table you have created. I also (think) I understand how to find the character's position (in terms of tiles...calculate how many rows he is down...x16...plus how many columns he is across sort of thing). However, I'm not sure how to create a pointer and then call a reference to that pointer or where to write pointer data in this case (please forgive me if my nomenclature is off). I think this is the main reason that my approach was to literally check the value of a tile since those values already exist, however the method your describing is what I definitely would rather pursue, it was sort of *next*. If you could help me understand how the pointer would work in this instance (and subsequent instances where one might be required), that would be awesome.

I'm sorry if this is vague, but thank you so much for your thought our and quick responses!

tepples
Posts: 22091
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Best way to generate bkg collision data?

Post by tepples » Fri Jul 11, 2014 4:21 pm

tokumaru wrote:Very few games recognize individual tiles as entities of the level, tiles are almost exclusively a graphical element used to represent a portion of a metatile.
Examples of the few games that do use 8x8 primitives include Dig Dug, Tetris, Dr. Mario, Wit's, NESnake 2, Battle City, Rampart, and other (mostly non-scrolling) games.
That's probably because without an MMC5 the NES is unable to color individual tiles arbitrarily, so it makes sense to always process them in groups of 2x2, and that includes collisions.
An 8x8-oriented game separates its background into (usually predefined) "zones". For example, in the snake games and the falling block games, the playfield has its own color set and everything else uses other color sets. In Rampart, each player's side has its own color set. Dig Dug uses color sets to represent soil strata. Battle City has destructible areas in one color set and in another. Attribute Zone is somewhere in the middle because while it uses 8x8 pixel cells, the areas of influence are 2x2 cells each. The Legend of Zelda uses "vertical columns" (16x176 pixel areas) as its primitive in outdoor areas but allows certain things like rocks to be placed at half-metatile boundaries, so long as the area just above and below the rocks uses the same color set.

With that said, let's go back to games using 16x16 pixels as the primitive:

There's a general principle of not repeating yourself. This means there should usually be a single version of the truth, where "the truth" is the map layout. You'll end up designing some sort of data model and then deriving various "views" of that model. For example, if metatile value $1B represents a "crate" (or "treasure chest" or "? block"), then there will be one table describing the collision properties for $1B and other tables describing its appearance. The collision code takes the $1B and looks it up in the collision table; the drawing code takes the $1B and looks it up in the appearance table.

Super Mario Bros. divides its 256 metatile numbers into four 64-metatile subspaces, and each subspace is hardcoded to one color set whose bits are the same as bits 7 and 6 of the metatile value. But this isn't redundant information because, say, values $04 and $44 represent completely unrelated metatiles.

JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Best way to generate bkg collision data?

Post by JoeGtake2 » Fri Jul 11, 2014 5:09 pm

Yes, I understand the concept, thanks! It's more the implementation I'm having a problem with. I've done this sort in high level languages, just trying to translate it to my growing knowledge of ASM. For instance, I can generally use my nametable setup as a reference of how to set up a table, however, For this instance, where would/should/could I store to values?

Once stored, i can use the figuring of the coordinate system to find what metatile is there and then read its value to determine what to do, i get this too. I'm just trying to convert my logical understanding to ASM and the quirks of the NES. :-)


****EDIT****

I was able to cobble together something based on all of your great advice, my intuition from high language environments, and other resources that 'works'...likely less than efficient, but for the learning exercise that this is supposed to be, it'll do! Thanks so much!

Post Reply