Jump to content
  • 0
Justin Baldock

Sprite and Tile Collision?

Question

Posted (edited)

Is there any pointers or tutorials on how to detect collision between sprites and tiles? As well as collision between sprites and sprites?

Is it possible to do mask collisions with tiles and sprites? My google-fu seems to be letting me down tonight.

Edited by Justin Baldock

Share this post


Link to post
Share on other sites

17 answers to this question

Recommended Posts

  • 0

A great article I read recently that talks about sprite to tile collisions and other considerations when thinking about implementing a platformer style game:

https://games.greggman.com/game/programming_m_c__kids/

The HW context is the NES but the principles still apply. Interestingly, the Collisions section starts with the sentence "Now for the fun part. NOT!

It won't give you the 6502 code but details some of the challenges and provides approaches to solving them.

I found it useful for one of my current X16 projects.

 

 

 

 

 

 

 

 

 

Edited by Geehaf
typo
  • Like 1

Share this post


Link to post
Share on other sites
  • 0

There is no hardware support for sprite/tile collisions, like with the NES. So, you just have to do the math. You need to calculate the screen position of tiles based on the current scroll settings and tile dimensions. Then you'll have to determine your own overlap margin to calculate when a sprite is actually colliding with the tile.

For Chase Vault, I wrote the sprite_getpos routine here:

https://github.com/SlithyMatt/x16-chasevault/blob/master/sprite.asm

This calls other routines in the repo, as well, so it's not easily pulled out on its own, but it is a working example.

  • Like 2

Share this post


Link to post
Share on other sites
  • 0

I am using what must be the most simple method. I just check in which tile the center of the sprite is located. Then I have a table that tells me if the tile is causing a collision (eg a tree) or not. It works surprisingly well, at least in a fast game like mine. If the sprites move faster than one pixel/frame you can’t really have pixel exact detection anyway : ).

  • Like 1

Share this post


Link to post
Share on other sites
  • 0

For the chopper game which I started and haven't had time to get back to for 3+ months 😐 (https://github.com/CJLove/x16-ChopperRaid) I had 1-bpp bitmaps of the chopper sprite and of the tileset and a copy of the tilemap in a bank of RAM so collision detection didn't involve accessing VRAM. 

The collision detection started by grabbing the block of tiles (e.g. a 3x6 grid) directly under the chopper sprite.  In the best case, "coarse" detection could detect if the chopper were over any "special" or non-blank tiles and act accordingly.  Otherwise (e.g. if the chopper were close to tiles for uneven terrain) it would resort to "fine" detection and do bitwise AND operations between bytes from the chopper bitmap and bytes from the appropriate area of the tile bitmap. If any of the ANDs returned non-zero then there was some sort of pixel collision. My thinking at the time was that even though this was computationally expensive I could allocate processing to separate iterations of the main loop. So if I was only updating chopper movement every 3rd frame (https://github.com/CJLove/x16-ChopperRaid/blob/master/test/test_chopper.c#L52) I could eventually do the collision detection in a separate frame.  It was a nice theory at least 🙂

  • Like 1

Share this post


Link to post
Share on other sites
  • 0

Very interesting, I am all ears because this is a tricky bit.

My first thought is that it is quite easy to identify the tiles under the sprite, but from there it seems hard to get to the point where you actually can start ANDing bytes. Have you managed to do it?

A second thought is that if you only move the sprite every third frame, the maximum speed will be 20 pixels/sec, in other words it will take 16 seconds to cross the screen horizontally if the resolution is 320x200. That’s very slow. If you move it more than one pixel at a certain time in any direction, you will not hav e the benefit of pixel perfect detection any longer, or am I wrong?

Share this post


Link to post
Share on other sites
  • 0

It's been a while since I wrote the code, so I'm going back to my (sadly sparse) dev notes and trying to refresh my memory as I go...

The chopper was moving multiple pixels per update (looks like I last had the deltaX set to +/- 4 pixels, deltaY set to +/- 2 pixels if explicitly moving up or down, otherwise deltaY set to 1 pixel for falling due to gravity).

Given the chopper sprite's x and y pixel position you can convert that to a tile position and "partial" x/y values (0-7): tileX = x/8; partialX = x mod 8; tileY = y/8; partialY = y mod 8;

The chopper was a 64x32 sprite, of which the chopper itself was actually 48x24 centered horizontally (hence a grid of 6x3 underlying tiles).  I created equivalent 8 56x24 1bpp bitmaps of each of the 5 chopper sprites (far left, left, center, right, far right) at 8 different horizontal offsets (shifting 1 bit right each time) and had those in banked ram with 1bpp bitmaps of the tileset.

Using tileX and tileY you can grab the underlying tiles (a 128x64x2 tilemap in VRAM was converted to an equivalent 128x64x1 map in banked RAM).

Using partialX and partialY you could then figure out the right set of bytes from the tileset bitmap and sprite bitmap to do the bitwise compares (https://github.com/CJLove/x16-ChopperRaid/blob/master/src/collision.c#L230).

I did get it to work, largely because of a large amount of unit test code (https://github.com/CJLove/x16-ChopperRaid/blob/master/test/test_collision.c) which tested each chopper bitmap against various scenarios of underlying tiles. Getting this to work through interactive testing would have been a non-starter.

The key to all of this was compiling the sprite bitmap, tileset and tilemap metadata for banked RAM from graphical assets in Piskel files and Tiled.  Some of the conversions were doable with Alovera, others were done with python scripts.

One hiccup happened when I decided to double the size of the tileset and forgot about the implications for the corresponding tileset bitmap in banked RAM; that resulted in a lot of "phantom" collisions and chopper explosions.

I'm hoping to come back to the project at some point as I had a lot of the game elements working separately, but they "day job" has been taking priority lately.

  • Like 1

Share this post


Link to post
Share on other sites
  • 0

Thanks for explaining this further! Yes, it seems totally doable. I will take a look at your code : ). It would be nice to have some tool for graphics that could automate the whole process of converting png images to an X16 binary format and at the same time generate the 1 bpp masks. Thanks also to @SlithyMattfor your contribution! 

  • Like 1

Share this post


Link to post
Share on other sites
  • 0
On 10/4/2020 at 2:46 PM, Johan Kårlin said:

It would be nice to have some tool for graphics that could automate the whole process of converting png images to an X16 binary format and at the same time generate the 1 bpp masks.

How did you imagine that the 1bpp masks should be created? I think you would need to outline your png or similar ?

Share this post


Link to post
Share on other sites
  • 0
17 minutes ago, JimmyDansbo said:

How did you imagine that the 1bpp masks should be created? I think you would need to outline your png or similar ?

Well, if you use PNG transparency, it should be relatively easy. Whether your sprite graphics correspond 1:1 to your collision mask is another matter. Suppose you're making a remake of Barbarian or International Karate... sometimes you need to allow some sprite overlap and not register it as a collision, e.g. hand-to-hand collision should be expected and not count as a hit. So, even though you could use sprite graphics to generate the collision mask automatically, there's plenty of situations where that's not practical.

Share this post


Link to post
Share on other sites
  • 0

Maybe it isn't a good idea. I haven't really thought about it. First of all you have to manually select which tiles cause a collision. For the tiles that do the first rule would be to look att the transparent color as @Guybrush just wrote. When it comes to tiles maybe you could select which colors should be considered as background colors. When neither of these alternatives work you have to draw the mask manually. If I would have used masks in my racing game this would have been really helpful. I have about 50 "collision tiles" and just about all of them have the same green color as background.

Share this post


Link to post
Share on other sites
  • 0

All I can really add is that is was common for games of the period to rely on simple axis-aligned box logic to detect collisions - this is where the term "hitbox" comes from - because it was frequently considered way too expensive to have pixel-perfect collisions. It was a requirement, then, that the graphical assets to conform reasonably well to some minimal set of hitboxes (in games this was typically 1 or 2 boxes total for the player, and 1 box for enemies, but needs varied).

A helicopter game where the heli is viewed from the side and can actually tilt in the direction of movement would be difficult to express in such hitboxes, so might require some special case logic. I would think this is fine as long as we're talking about 1 such special object in the scene, but I wouldn't expect there to be an abundance of processor power for, say, enemies to have the same kind of collision logic with random objects.

Share this post


Link to post
Share on other sites
  • 0

It doesn’t surprise me. As I wrote earlier in the thread, hitboxes work better than you might think, at least as long as the sprites are moving at a reasonable speed. But the subject is still interesting.

Share this post


Link to post
Share on other sites
  • 0
20 minutes ago, Johan Kårlin said:

It doesn’t surprise me. As I wrote earlier in the thread, hitboxes work better than you might think, at least as long as the sprites are moving at a reasonable speed. But the subject is still interesting. emoji4.png

It's funny you should mention "at a reasonable speed", because even modern game engines struggle with "the bullet problem" -- what happens when an object is moving so fast that its entire volume can travel from one side of an obstacle to the other within the span of a single frame. Actually, in some ways, the problem is harder today with rigid body physics, where you don't typically express world geometry in terms of "volumes" and instead reduce it to a series of surfaces. This means it's actually easier for small objects to move fast enough that it appears to "pass through" the solid surface.

Typically, modern physics engines attempt to resolve this problem by taking multiple interpolating steps from a start position to its end, hoping that by taking smaller "steps" within a frame they'll detect this kind of condition. This is why collision quality in engines like Unity or Unreal have multiple settings, so a large and slow object can skip the extra interpolation, while literal models of bullets, traveling at bullet-like speeds, can hog all the CPU time by making many hundreds of steps between each frame.

Of course, for bullets and the like, many 3D games these days also choose not to simulate bullets at all, they just cast rays into the scene. These games' behaviors are commonly referred to as "hitscan". Overwatch, by Blizzard, has a number of heroes which use hitscan weapons, while others use finite-speed projectiles. But you can find bullet-speed projectiles at least as early as Max Payne, which has a bullet-time mechanic where you can see the bullets traveling. It's also possible to calculate the bullet trajectory from one frame to the next and then raycast along that segment of the path, which has its own pros and cons (this can be inefficient if there are a lot of bullets in the air at one time).

So, "a reasonable speed" has always been an interesting problem, if you're trying to push the envelope for some reason. I suppose, putting my game designer hat on for a moment, the question is: Why do you need bullets that small to travel that fast? Like, what's the purpose, and would it be just as well to make the weapon's attack instantaneously travel along the line?

Edited by StephenHorn

Share this post


Link to post
Share on other sites
  • 0

Collision detection in modern 3D games - the thought is dizzying. Sounds like really advanced stuff. I am happy to be stuck in the 8/16 bit world : ).

  • Like 1
  • Haha 1

Share this post


Link to post
Share on other sites
  • 0
It's funny you should mention "at a reasonable speed", because even modern game engines struggle with "the bullet problem" -- what happens when an object is moving so fast that its entire volume can travel from one side of an obstacle to the other within the span of a single frame.


I have realized that I have sort of a bullet problem in my racing game. When the cars collide they are meant to bounce away from each other. But when they move fast they can suddenly be on top of each other in just a single frame. At the same time the physics calculations say they should bounce maybe two or three pixels which isn’t enough to bring them apart. The easiest way of solving this is of course to always make sure they are repelled with a certain minimum of pixels. But I am not so fond of the idea of having to compromise on - in the context - quite accurate calculations.
  • Like 1

Share this post


Link to post
Share on other sites
  • 0
On 10/26/2020 at 3:09 PM, Johan Kårlin said:

I have realized that I have sort of a bullet problem in my racing game. When the cars collide, they are meant to bounce away from each other. But, when they move fast, they can suddenly be on top of each other in just a single frame. At the same time, the physics calculations say they should bounce maybe two or three pixels which isn’t enough to bring them apart. The easiest way of solving this is, of course, to make sure they always are repelled with a certain minimum of pixels. But, I am not so fond of the idea of having to compromise on -- in the context -- quite accurate calculations. emoji848.png

How about "maybe two or three pixels" plus the radius of the cars.  It isn't perfect (it assumes that they were centered on each other), but it's easy.  Besides, would anyone notice a slight discrepancy (they are moving fast)?

Share this post


Link to post
Share on other sites
  • 0

That is a good suggestion, I will probably end up with something like that. But I think I will refine the approximation. I do know the relative speed of the cars and can use that to calculate the maximum possible overlap in pixels.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

Please review our Terms of Use