Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411670 Posts in 69397 Topics- by 58452 Members - Latest Member: homina

May 16, 2024, 12:46:45 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)What is the most elegant tile-based collision algorithm?
Pages: 1 2 [3]
Print
Author Topic: What is the most elegant tile-based collision algorithm?  (Read 16571 times)
Theotherguy
Level 1
*



View Profile
« Reply #40 on: February 20, 2010, 07:04:39 PM »

The original Super Mario bros. did that, hahaha
But that was in the 80's, holy shit.

Really? I find that very unlikely, considering that the player moves relative to the center of the screen.
Logged

raigan
Level 5
*****


View Profile
« Reply #41 on: February 22, 2010, 08:37:09 AM »

I hope that the OP has enough info here to at least provide some ideas of how to restructure things. Some of these comments seem pretty negative, this is supposed to be a technical forum Smiley
Logged
Tycho Brahe
Level 10
*****

λx.x


View Profile
« Reply #42 on: February 22, 2010, 09:52:38 AM »

I hope that the OP has enough info here to at least provide some ideas of how to restructure things. Some of these comments seem pretty negative, this is supposed to be a technical forum Smiley
I hope so too, he seems to be getting on quite well so far:
http://zachwlewis.dyndns.org/monolith/

But still, if he doesn't then I'm sure he'll post again for help!
Logged
Zachary Lewis
Level 1
*


Professional by day, indie by night.


View Profile WWW
« Reply #43 on: February 22, 2010, 10:22:18 AM »

Okay guys, OP here.

I still don't know if I should roll my own solution or use Box2D. Could you go over the reasons for/against each one again? Giggle

But, for seriously, you've been a big help. I rolled my own separating axis narrow phase collision, and I plan on using sweep and prune for my broad phase collision.

To handle the collisions on the boundaries of the level I duplicated the tile on the other side of the map (where the player will be wrapping to) and placed it on the boundary of the map. This allows the player to collide properly with "the tile on the other side of the map".

I hope that the OP has enough info here to at least provide some ideas of how to restructure things. Some of these comments seem pretty negative, this is supposed to be a technical forum Smiley
I hope so too, he seems to be getting on quite well so far:
http://zachwlewis.dyndns.org/monolith/

But still, if he doesn't then I'm sure he'll post again for help!

14113 is right, and you should check out the devlog to follow along!
Logged

Impossible
Level 3
***



View Profile
« Reply #44 on: February 22, 2010, 11:01:18 AM »

I rolled my own separating axis narrow phase collision, and I plan on using sweep and prune for my broad phase collision.

Isn't SAP overkill for what you are trying to do?  In your videos it looks like you are basically doing a couple of moving boxes vs. a static tile grid.  Are you planning on having lots of dynamic colliding objects?  If you want full rigid body dynamics and a lot of dynamic objects Box2D would be a better choice, at least for that part of your physics.  I still think that you are better off rolling your own platforming character physics, but that shouldn't need SAP...
Logged
raigan
Level 5
*****


View Profile
« Reply #45 on: February 22, 2010, 01:43:22 PM »

You also shouldn't need to duplicate tiles in order to achieve wrapping; instead you should just wrap your math. This is just OTOH:

Given:
Code:
grid_width //number of tiles in world, horizontally
tile_width //horizontal size of each tile, in pixels

Let:
Code:
world_width = grid_width*tile_width; //width of the world, in pixels
max_delta_x = world_width/2;         //used for wrapping

In order to collide a tile vs an object (e.g the player), consider the tile from the object's point-of-view:
Code:
delta_x = tile_x - object_x;

This is a "raw" delta pointing from the object to the tile; it might be pointing in the wrong direction. We now wrap the delta so that it points from player to tile in the shortest direction (i.e if it's shorter to wrap around one of the edges of the world, this will wrap the delta vector):
Code:
if(delta_x > max_delta_x)
{
  //delta is pointing right but it's shorter to go left
  delta_x -= world_width;
}
else if(delta_x < -max_delta_x)
{
  //delta is pointing left but it's shorter to go right
  delta_x += world_width;
}


The tile's position along the x axis, relative to the object, is delta_x  -- use this as its position for collision/etc. and you won't need to duplicate it, because the vector is wrapped in the correct way. For the y axis, if you want it to wrap just do the same thing, or if you don't want it to wrap just use the "raw" delta.

Note that there may be a simpler/smarter/better way to model the wrapping behaviour, but my example should work; the important concept is that you just need to work in a coordinate system that wraps, you don't need to explicitly duplicate objects or anything like that.

Imagine that positions in x are mapped to points along a circle (i.e you're looking down from above) -- there will always be two ways to get from A to B, clockwise and counter-clockwise; for collision you only need to care about the shortest way. And you know the shortest path has to be at most half the width of the world -- otherwise the other direction is shorter.

I hope this makes sense..
« Last Edit: February 22, 2010, 01:51:19 PM by raigan » Logged
salade
Level 4
****



View Profile
« Reply #46 on: February 22, 2010, 01:48:54 PM »

Just warp the main character once you reach the level's boundaries. Like Asteroids.

It seems like whatever you are doing is working though.
Logged
Zaphos
Guest
« Reply #47 on: February 22, 2010, 01:56:55 PM »

I rolled my own separating axis narrow phase collision, and I plan on using sweep and prune for my broad phase collision.

Isn't SAP overkill for what you are trying to do?  In your videos it looks like you are basically doing a couple of moving boxes vs. a static tile grid.
Yes, if it's just that I wouldn't use separating axis or sweep and prune; just a few simple array lookups to check 'is there a tile under [this part of the character]' should suffice.

But the more general collision stuff will probably still come in handy when he wants to do collisions vs a bunch of enemies, etc.
Logged
Pages: 1 2 [3]
Print
Jump to:  

Theme orange-lt created by panic