Collision solid objects, level data, tile-based movement

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

Pokun
Posts: 1322
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Collision solid objects, level data, tile-based movement

Post by Pokun » Thu Jul 09, 2015 4:25 pm

So I'm making a simple NROM single-screen Sokoban-style game, and I have a few newbie questions.

1. I need a hint on how to do collisions with non-moving solid objects like walls. I heard of having a map that keeps track of all solid terrain, but how would I go about doing that in practice?

2. How do people store level data? Do you simply store full screens of nametable and attribute data or do you somehow use loops and stuff to draw it? Currently I store every screen/stage in their own uncompressed table.

3. Currently the main character moves pixel by pixel but I'd like them to smoothly move one tile (or half tile) per button press like how Lolo or most RPG heroes does. Nothing I tried worked very well.
Last edited by Pokun on Fri Jul 10, 2015 4:31 pm, edited 1 time in total.

lidnariq
Posts: 9007
Joined: Sun Apr 13, 2008 11:12 am
Location: Seattle

Re: Collision solid objects, level data

Post by lidnariq » Thu Jul 09, 2015 6:13 pm

Since you're working with a "Sokoban-style" game, these answers are pretty easy

1- Just check the square the player / a block will be moving into before allowing it. Don't allow half moves
2- It's probably easier to store the level data uncompressed until you discover you need it compressed. Regardless of whether it's compressed in ROM, it's easier to work with an uncompressed copy in RAM.
3- Why don't you enumerate what you have tried and how it's not what you want?
Without knowing anything, I'd personally first try something like: a counter that counts frames and a state for "player is moving right", so effectively gameplay alternates between "playing an animation" and "waiting for input"

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

Re: Collision solid objects, level data

Post by tokumaru » Thu Jul 09, 2015 6:55 pm

Pokun wrote:1. I need a hint on how to do collisions with non-moving solid objects like walls.
Here's an object and the level map it interacts with:

Code: Select all

      00     01     02     03     04     05     06     07
   +------+------+------+------+------+------+------+------+
0  |      |      |      |      |      |      |      |      |
0  |      |      |      |      |      |      |      |      |
   +------+------+------+------+------+------+------+------+
0  |      |      |      |      |      |      |      |      |
1  |      |      |    0----------1    |      |      |      |
   +------+------+----|$$$$$$$$$$|----+------+------+------+
0  |      |      |    |$$$$$$$$$$|    |      |      |      |
2  |      |      |    |$$$$$$$$$$|    |      |      |      |
   +------+------+----|$$$$$$$$$$|----+------+------+------+
0  |      |      |    |$$$$$$$$$$|    |      |      |      |
3  |      |      |    |$$$$$$$$$$|    |      |      |      |
   +------+------+----|$$$$$$$$$$|----+------+------+------+
0  |      |      |    2----------3    |      |      |      |
4  |      |      |      |      |      |      |      |      |
   +------+------+------+------+------+------+------+------+
0  |      |      |      |      |      |      |      |      |
5  |      |      |      |      |      |      |      |      |
   +------+------+------+------+------+------+------+------+
You basically have to check all the blocks that touch one of the edges of the object whenever the object moves in that direction, and whenever solid blocks are found, push the object back enough so that it isn't overlapping the solid block anymore.

For example, if the object above moved right, you'd check all the blocks between points 1 and 3, which are (04, 01), (04, 02), (04, 03) and (04, 04). If any of those are solid, you push the object left enough so it stops overlapping the solid block. The process is the same for any of the 4 directions.
I heard of having a map that keeps track of all solid terrain, but how would I go about doing that in practice?
Where you store the collision data is entirely up to you. Some people do use separate maps for solidity, but it makes much more sense to have the solidity as an attribute of the blocks used to draw the levels.

For the sake of simplicity, let's assume that the blocks we're dealing with are tiles, because tiles are always 8x8 pixels, while metatiles come in various sizes depending on the game.

Since the collision points are calculated from the sprite position, they are in pixel units. To find the coordinates of the corresponding tile, you have to divide the pixel coordinates by 8 (the width/height of a tile). For example, a point at pixel coordinates (173, 204) corresponds to the tile at (21, 25). Having the coordinates of the tile, you can calculate its address in a tile map using the following formula: Y * 32 + X, so in our example we're looking for the tile at offset (25 * 32) + 21 = 821. Using pointers you can read the index of the tile at that position, and use it to look up its solidity status. How you're gonna do that is up to you. You could have a table with 256 entries specifying the solidity of each tile, but for a simple game it makes sense to have that information built in the tile index itself... for example, tiles $00 to $3F are empty, tiles $40 to $7F are solid, tiles $80 to $BF are water, and so on.
2. How do people store level data? Do you simply store full screens of nametable and attribute data or do you somehow use loops and stuff to draw it? Currently I store every screen/stage in their own uncompressed table.
Whatever fits the design of the game. Uncompressed NT/AT data is 1KB per screen, so that only makes sense for games that don't have many unique screens. Games with static screens should at least use RLE or LZ to reduce the size of these raw screens. Most games use metatiles though. 16x16 or 32x32 are very popular sizes, because they reduce the space occupied by each screen from 1024 to 254 and 64 bytes, respectively. And you can even compress the maps further.
3. Currently the main character moves pixel by pixel but I'd like them to smoothly move one tile (or half tile) per button press like how Lolo or most RPG heroes does. Nothing I tried worked very well.
One way to do it is to create a state variable for your character. The variable starts in the "idle" state. When a direction is pressed in the controller, check if the player's coordinates are multiples of 8, and if that's the case, set the state to "walking up/down/left/right", depending on the direction that was pressed, otherwise, ignore the input. Then, check the state and move 1 pixel in the direction specified by it, if any. If after the movement the coordinates became multiples of 8, set the state to "idle" again.

zzo38
Posts: 1059
Joined: Mon Feb 07, 2011 12:46 pm

Re: Collision solid objects, level data

Post by zzo38 » Thu Jul 09, 2015 8:23 pm

What lidnariq wrote seems to be valid.

For level data (of a "Sokoban-style game"), I have used huffed RLE data stored in CHR-ROM; the pointers to this data (including bank number) are stored in PRG-ROM. It is then uncompressed into RAM, and then is written into the nametables.

However, in the specific case of Sokoban, there is an even better way to compress levels, as I have figured out.
[url=gopher://zzo38computer.org/].[/url]

Pokun
Posts: 1322
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Collision solid objects, level data, tile-based movement

Post by Pokun » Fri Jul 10, 2015 5:31 pm

Thanks for all replies!

3. I've done more work on movement and here is my unfinished movement subroutine:

Code: Select all

P1Movement:
  lda P1Moving ;check direction
P1MoveUp:
  and #$08
  beq @exit ;cancel if not moving up
  lda P1Y
  sta Temp1
  lda #TILESIZE
  sta Temp2
  jsr Modulus ;P1Y % 8 (if TILESIZE is 8)
  cmp #$00 ;check if multiple by 8
  bne @exit ;ignore button press if already moving
  lda P1Y
  sec
  sbc #MOVEMENTSPEED
  sta P1Y ;move
  cmp #TOPWALL
  bcs @exit
  clc
  adc #MOVEMENTSPEED
  sta P1Y ;move out of wall
@exit:
  lda P1Moving ;check direction
P1MoveDown:
  ;...
  rts
TILESIZE is set to 8. I haven't touched collisions yet, I just have constant values for the outer wall coordinates for now. But I guess I can ditch them if I give wall tiles solid attribute.

Of course this routine doesn't give me smooth movements, and requires MOVEMENTSPEED to be multiple with 8 to even work. I'm not sure how to make them walk 8 pixels but over several frames. I guess I need that frame counter? I don't how a counter would work.

User avatar
rainwarrior
Posts: 7716
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Collision solid objects, level data, tile-based movement

Post by rainwarrior » Fri Jul 10, 2015 5:39 pm

What's in your Modulus routine? If it's a power of 2 you can do it in a single instruction (AND).

Code: Select all

; this code...

  lda P1Y
  sta Temp1
  lda #TILESIZE
  sta Temp2
  jsr Modulus ;P1Y % 8 (if TILESIZE is 8)
  cmp #$00 ;check if multiple by 8

; i would suggest this instead:

  lda P1Y
  and #(TILESIZE-1) ; P1Y % TILESIZE if TILESIZE is power of 2
  cmp #$00

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

Re: Collision solid objects, level data, tile-based movement

Post by tokumaru » Fri Jul 10, 2015 5:42 pm

There's no need for the cmp #$00 either, the AND operation will handle the Z flag.

Pokun
Posts: 1322
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Collision solid objects, level data, tile-based movement

Post by Pokun » Sat Jul 11, 2015 3:43 am

Thanks, it works with AND. I don't get why you put a -1 after TILESIZE though? And the parenthesis wasn't needed (in asm6 anyway).

My modulus routine looked like this:

Code: Select all

Modulus:
;Temp1 % Temp2 = A
  lda Temp1
  sec
@loop:
  sbc Temp2
  bcs @loop
  adc Temp2
  rts
But it isn't needed anymore.


Still can't figure out how to make the character to move 1 pixel per frame instead of 8.

User avatar
rainwarrior
Posts: 7716
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Collision solid objects, level data, tile-based movement

Post by rainwarrior » Sat Jul 11, 2015 10:02 am

To understand the -1 and why AND works in this capacity, consider how a power of 2 like the number 8 looks in binary:

Code: Select all

; these two lines are equivalent
AND #8
AND #%00001000

; these two lines are equivalent
AND #(8-1)
AND #%00000111
Sure, the parentheses probably aren't necessary but I prefer them to illustrate that the immediate prefix # applies to the whole expression. It helps my own comprehension when reading my code, but if you don't like my style, write it how you like.

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

Re: Collision solid objects, level data, tile-based movement

Post by tokumaru » Sat Jul 11, 2015 12:44 pm

Here's some pseudo-code for the walking thing:

Code: Select all

if (PlayerState = Idle) then
	if (Up pressed) then PlayerState = WalkingUp
	elseif (Down pressed) then PlayerState = WalkingDown
	elseif (Left pressed) then PlayerState = WalkingLeft
	elseif (Right pressed) then PlayerState = WalkingRight
end if

if (PlayerState = WalkingUp) then PlayerY = PlayerY - 1
elseif (PlayerState = WalkingDown) then PlayerY = PlayerY + 1
elseif (PlayerState = WalkingLeft) then PlayerX = PlayerX - 1
elseif (PlayerState = WalkingRight) then PlayerX = PlayerX + 1

if ((PlayerX and 7 = 0) and (PlayerY and 7 = 0)) then PlayerState = Idle
Of course this is ignoring the collision detection. You should probably check whether the direction the player pressed is clear before changing the state to "WalkingXXXX".

Pokun
Posts: 1322
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Collision solid objects, level data, tile-based movement

Post by Pokun » Sat Jul 18, 2015 2:28 pm

Ah thanks Tokumaru and Rainwarrior, this code mostly worked. :) I worked a bit on my sound engine and then went back to tile-based movement and it works now as long as the player doesn't press in any diagonal direction.

If you press diagonally the character never stops walking until you manage to realign them to the grid again. I guess the reason to this is because if the player press in one direction and then immediately another direction the player will stop walking in the first direction and continue walking in the other direction. If the second direction is of the opposite axis as the first direction the character will end up between the tiles and never stop moving.

My movement code:

Code: Select all

P1InputHandle:
  lda P1Movement
  and #$00 ;make sure the player isn't moving
  bne @exit
@up:
  lda con_cur ;read controller
  and #CON_UP
  beq @down ;if UP is pressed
  ;jsr collisioncheck
  lda #$08
  sta P1Moving ;set moving direction to UP
  jmp @exit
@down:
  ;...
@exit

P1Movement:
  lda P1Moving ;check direction
@moveup:
  and #$08
  beq @movedown
  lda P1Y
  sec
  sbc #MOVEMENTSPEED ;move character
  sta P1Y
  jmp @exit
@movedown:
  ;...
@exit

P1PosCheck:
;Check if position is multiple by TILESIZE:
  lda P1X
  and #(TILESIZE-1) ;if X position...
  bne @exit
  lda P1Y
  and #(TILESIZE-1) ;...and if Y position...
  bne @exit ;...are both multiple of TILESIZE...
  lda #$00
  sta P1Moving ;...then set to "not moving"
@exit:
I added an extra check for character's moving direction (P1Movement) and make sure the player is standing still before reading the controller to prevent him from changing direction in the middle of a move but it doesn't work. I don't get why.

mikaelmoizt
Posts: 120
Joined: Sat Apr 12, 2014 12:11 pm
Location: Gothenburg, Sweden

Re: Collision solid objects, level data, tile-based movement

Post by mikaelmoizt » Sat Aug 08, 2015 5:04 am

Any news Pokun? For having basically the same questions, I will post here. (maybe we should go team Sweden? :) )
Ah yes. I am really doing some actual coding now!

The motherload of "hard to grasp n00b issues".. how the h*ll do I translate a sprite position on screen to actual
tile address on the nametable in order to set up a collision detection between sprites and tiles?
It seem everyone gets stuck on this problem for quite some time.. :)

I went with the KISS philosophy.
The basic setup is to

1. Divide sprite x and y positions with 8 to get tile size based coordinates
2. Look up in nametable data by using pointers for every tile x and tile y
3. When you increase your sprite x and y position it changes where on your data table you will read, the pointer adress changes. Sprite not moved with 8px per frame, but 1. Sound added for maximum annoyance :P
Maybe I have misunderstood the concept of this..?

So I got this to (almost) work. The problem I am facing is that it seems my sprite movemenent for some reason
breaks nametable fetching after a while. Eventually the selection box will be very off center. Its okay to take a look at the code, but a fair warning - it aint pretty right now because I just wanted some progress before bed time last night.
What I need now is some guidance on how to improve this.

To help you help me, how would you go about to:

Have a movable sprite (at 1px per frame), read what tile is "beneath" it based on for example nametable data? Pseudo code works.
Attachments
collisioncrap.nes
(40.02 KiB) Downloaded 118 times
I´ve got %01100011 problems but the BITs aint one.

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

Re: Collision solid objects, level data, tile-based movement

Post by tepples » Sat Aug 08, 2015 5:42 am

mikaelmoizt wrote:how the h*ll do I translate a sprite position on screen to actual
tile address on the nametable in order to set up a collision detection between sprites and tiles?
It all depends on how you are representing your map in the CPU's RAM. Are you representing it literally as a 32x30-byte array in, say, $0400-$07FF? Or are you using some sort of metatile array or region list?
2. Look up in nametable data by using pointers for every tile x and tile y
The practicality of that depends on how the nametable is stored. Video memory can't be read or written outside vertical blanking (or forced blanking by writing 0 to $2001) because the PPU is busy using it to make the picture.
To help you help me, how would you go about to:

Have a movable sprite (at 1px per frame), read what tile is "beneath" it based on for example nametable data? Pseudo code works.
That would depend on how you are organizing your map data. If you don't yet know how to organize map data, I can help you plan that out too. Screen shots work.

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

Re: Collision solid objects, level data, tile-based movement

Post by tokumaru » Sat Aug 08, 2015 6:42 am

tepples wrote:It all depends on how you are representing your map in the CPU's RAM.
Or ROM... level maps can be in ROM too.

Either way, knowing the map format is indeed essential to define the formulas necessary to read it.

An uncompressed 32x30 array of tile indices is unpractical in most real game scenarios, due to the huge amount of memory (ROM or RAM) they occupy. Games that only have a couple of different screens might still go this route though, to keep things simple.

If your map is indeed just a 32x30 array of tile indices, as is common in beginner tutorials, the formula for converting pixel coordinates into map offsets is (PixelY / 8) * 32 + (PixelX / 8). We divide by 8 because each tile is 8x8 pixels, and we multiply the Y part by 32 because each row is "worth" 32 tiles, since that's how wide the map is. Here's an example of how to create a pointer to a tile based on pixel coordinates:

Code: Select all

	lda #$00
	sta MapPointer+1
	lda PixelY
	and #%11111000
	asl
	rol MapPointer+1
	asl
	rol MapPointer+1
	adc #<MyMap
	sta MapPointer+0
	lda MapPointer+1
	adc #>MyMap
	sta MapPointer+1
	lda PixelX
	lsr
	lsr
	lsr
	tay
	lda (MapPointer), y
MapPointer is a 16-bit ZP variable. < and > are used to get the low byte and the high byte of the map's address (in NESASM you use LOW() and HIGH(), I think), and the last instruction gets the index of the tile at the address we calculated (NESASM would use [] for indirection).

You could load the map address from a table or from a variable, instead of using a hardcoded label, so you could reuse the same code for different maps.

Anyway, now A holds the index of the tile under the pixel specified by (PixelX, PixelY), and you have to use this index to find out the type of the tile: empty, solid, harmful, whatever. A simple way to do this would be to use the tile index itself. For example: $00 to $3F are empty, $40 to $7F are solid, and so on. This is a bit restrictive though, so a more common approach is to have a table of tile/block attributes, and you can use the tile index to read information from this table.

mikaelmoizt
Posts: 120
Joined: Sat Apr 12, 2014 12:11 pm
Location: Gothenburg, Sweden

Re: Collision solid objects, level data, tile-based movement

Post by mikaelmoizt » Sat Aug 08, 2015 6:59 am

tepples wrote: It all depends on how you are representing your map in the CPU's RAM. Are you representing it literally as a 32x30-byte array in, say, $0400-$07FF? Or are you using some sort of metatile array or region list?
I load and display my screen with hard coded data from ROM $8000 - $83bf right now, so my zp pointer uses that (00,80) and then I translate every 8 pixels of sprite movement into either +/- 1 (left or right) or +/- 32 bytes (up or down) to relate to that screen. Or atleast I am trying to do that ;)

Here is the basic idea I had how to do this sort of thing

Code: Select all

 lda #<screen ; low byte of screen  
 adc pageloc ; +/- 1 (left or right) or +/- 32 (up or down) 
 sta pointer

 lda #>screen ; hi byte of screen 
 adc pageloc2
 sta pointer+1

 lda sprite1_vpos ; sprite vertical pixel position/8
 lsr
 lsr
 lsr
 tay

 lda(pointer),y ; $8x00+y where hi byte is updated elsewhere
; the reuslt in acc should be a match bewteen $8xxx and nametable on screen $2xxx
The red square is supposed to control where you fetch data from
collevesen-0.png
collevesen-0.png (2.68 KiB) Viewed 3041 times
About organization of map data, yes that would be nice too.
I´ve got %01100011 problems but the BITs aint one.

Post Reply