gbadev.org forum archive

I have seen that nessie.gbadev.org has a map editor that I want to use, mostly because it allows flipping of tiles and 16 color tiles.
But I've seen that the sample map that comes with the maped zip has 45 degree tiles in its collision array.
How do you program 45 degree colision detection?
Is there any good formula for making other collision tiles with different degrees?

The only way to check 45 deg. is pixel by pixel creatin a mask of your tile... I think is the only way to do but you can found some problem when manage all other routines like jump and gravity...

You need to work a lot, i made mine for a platform i want to release but now i'm in vacation and is not 100% fixed i've some small problem...
_________________
Batblaster / 7 Raven Studios Co. Ltd
------------------------------------------

I did it quite easily actually but I cannot remember how I did coded it (damn my amature coding) how I did it though.....:/
_________________
[Blog] [Portfolio]

Well, if someone can help me. I want to know how to make it as fast as possible.

here is the code for the character moving up
var_x and var_y is the co ords for the map and the character always stays in the center of the screen.

Code:

case 1://up
{
switch((Tank_Out_Collision[var_snakeHeight][((((var_y+71) >> 3) << 6)) +
((var_x+108) >> 3)+65] & 0x000F))
{
case 4: return 1; break; //solid squares
case 2: return 1; break; //bottom left triangle
case 1: return 1; break; //bottom right triangle
case 5: func_moveEnvir(var_x, var_y, -1, 0); break; //top right triangle
case 6: func_moveEnvir(var_x, var_y, 1, 0); break; //top left triangle
case 3: var_snakeHeight--; break; //drop a level
case 7: var_snakeHeight++; break; //rise a level
default: break;
}

I can send the binary of it in action if you want...

btw sorry about the magic numbers :(
_________________
[Blog] [Portfolio]

Last edited by yaustar on Wed Jan 21, 2004 8:53 pm; edited 1 time in total

Quote:

The only way to check 45 deg. is pixel by pixel creatin a mask of your tile...

When you're tempted to say something that begins with "The only way to...", you would do well to reconsider, unless you have some reason to believe that you've explored every possible alternative (unlikely).

When colliding with perfect square blocks, a collision occurs anywhere in the block. When colliding with blocks that have a 45 degree slope, a collision only happens in the solid half.

For example, if tx is the distance from the left tile border, and ty is the distance from the top tile border, and the tile is solid on the bottom-right (i.e. a right incline), then a collision occurs when tx > tile_height - ty.

I've coded arbitrary angle collision detection tiles a couple of times now. The code for it is very simple and fast to run. You just need some basic knowledge of Vector Math to pull it off. Basically, setup 2 points on the edge of the char (in char coords), turn this into a vector. Assume that all points to the right of this line are solid. To test collision, get where on the char you wish to check, take the 2D determinant (cross product) of the line vector against the vector formed from your point and the starting point of the edge vector. If it's positive, you're colliding, negative, you're not, 0, you're on the line. Very qucik and can be turned into a reflection or slide along endge with ease.

Example of 45 degree diagonal (a solid char can be coded by running a vector along the edge of the tile):

Vector AB = {8 - 0, 8 - 0} = {8,8}

Vector AB = {8,8}
Vector AC = {1,4}
Vector AD = {5,2}
Vector AE = {2,2}

Det(AB, AC) = 8 * 4 - 1 * 8 = 24 : positive == collide
Det(AB, AD) = 8 * 2 - 5 * 8 = -24 : negative == no collide
Det(AB, AE) = 8 * 2 - 5 * 2 = 0 : On line

BTW, if you turn the line vector into a unit vector, the result of the Det is the actual distance from the line :)

I love vector math!

Mike

Code:

A-+-+-+-+-+-+-+-+
|X| | | | | | | |
+-\-+-+-+-+-+-+-+
|X|X| | | | | | |
+-+-E-+-+-D-+-+-+
|X|X|X| | | | | |
+-+-+-\-+-+-+-+-+
|X|X|X|X| | | | |
+-C-+-+-\-+-+-+-+
|X|X|X|X|X| | | |
+-+-+-+-+-\-+-+-+
|X|X|X|X|X|X| | |
+-+-+-+-+-+-\-+-+
|X|X|X|X|X|X|X| |
+-+-+-+-+-+-+-\-+
|X|X|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-B

Its actually a lot simpler than that for 45 degree angles.

The basic forumlar is just: D = X - Y
D will be neg for one side or pos for the other.

Assuming you are using 24:8 fix point maths then, you first detect a full cell collision, then a part cell collision using only the fractional component of the 24:8 fix point coords.

Code:

D = (X & 0xFF) - (Y & 0xFF)

For other 45 degree angles you swap one or both of the coords:

Code:

D = (0x100 - (X & 0xFF)) - (Y & 0xFF)

So there are no multiplies required.

BTW: This is the same method used to clip 3D polygons to 45 degree plains without using multiplies. Plus, the distances returned by this method can be plugged into a lerp function to calc the clipping point.

Derek Evans
http://www.theteahouse.com.au/gba/index.html

The other method which is the best IMHO. Is, to grab the disance to the cell under your feet, and then grab the distance to the next cell to the right. The distances should be 24:8 fix point maths.

You can then calc the actually distance based on your fractional X pos using a linear interpolation function:

Code:

#define f2i(A) ((A)>>8)
#define i2f(A) ((A)<<8)
#define intmul(A,B) ((A)*(B))
#define fixmul(A,B) f2i(intmul(A,B))
#define FIXLERP(A,B,C) ((A)+fixmul((B)-(A),(C)))
int realdist = FIXLERP(d1, d2, e->x & 0xFF);

This is the method used by 3D terrain engines. You can view a platform game as a 2D terrain. Note: you only have to use a LERP for cells which are defined as a terrain.

Derek Evans

Derek wrote:

The other method which is the best IMHO. Is, to grab the disance to the cell under your feet, and then grab the distance to the next cell to the right. The distances should be 24:8 fix point maths.

You can then calc the actually distance based on your fractional X pos using a linear interpolation function:

Code:

#define f2i(A) ((A)>>8)
#define i2f(A) ((A)<<8)
#define intmul(A,B) ((A)*(B))
#define fixmul(A,B) f2i(intmul(A,B))
#define FIXLERP(A,B,C) ((A)+fixmul((B)-(A),(C)))
int realdist = FIXLERP(d1, d2, e->x & 0xFF);

This is the method used by 3D terrain engines. You can view a platform game as a 2D terrain. Note: you only have to use a LERP for cells which are defined as a terrain.

Derek Evans

Your code may be useful to me!

Do you have any source code for this you can send me?

mail:
ola[(((((((((at))))]logotypes.se

Miked0801 wrote:

I've coded arbitrary angle collision detection tiles a couple of times now. The code for it is very simple and fast to run. You just need some basic knowledge of Vector Math to pull it off. Basically, setup 2 points on the edge of the char (in char coords), turn this into a vector. Assume that all points to the right of this line are solid. To test collision, get where on the char you wish to check, take the 2D determinant (cross product) of the line vector against the vector formed from your point and the starting point of the edge vector. If it's positive, you're colliding, negative, you're not, 0, you're on the line. Very qucik and can be turned into a reflection or slide along endge with ease.

Example of 45 degree diagonal (a solid char can be coded by running a vector along the edge of the tile):

Vector AB = {8 - 0, 8 - 0} = {8,8}

Vector AB = {8,8}
Vector AC = {1,4}
Vector AD = {5,2}
Vector AE = {2,2}

Det(AB, AC) = 8 * 4 - 1 * 8 = 24 : positive == collide
Det(AB, AD) = 8 * 2 - 5 * 8 = -24 : negative == no collide
Det(AB, AE) = 8 * 2 - 5 * 2 = 0 : On line

BTW, if you turn the line vector into a unit vector, the result of the Det is the actual distance from the line :)

I love vector math!

Mike

Code:

A-+-+-+-+-+-+-+-+
|X| | | | | | | |
+-\-+-+-+-+-+-+-+
|X|X| | | | | | |
+-+-E-+-+-D-+-+-+
|X|X|X| | | | | |
+-+-+-\-+-+-+-+-+
|X|X|X|X| | | | |
+-C-+-+-\-+-+-+-+
|X|X|X|X|X| | | |
+-+-+-+-+-\-+-+-+
|X|X|X|X|X|X| | |
+-+-+-+-+-+-\-+-+
|X|X|X|X|X|X|X| |
+-+-+-+-+-+-+-\-+
|X|X|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-B

Wow, can I set up any degrees in a ytile for collision with this code?

Vector Math, no I've never worked with it. Can you teach me quick?

2D determinant (cross product), teach me quick, this is heavy stuff :P

LOst? wrote:

Vector Math, no I've never worked with it. Can you teach me quick?

2D determinant (cross product), teach me quick, this is heavy stuff :P

Yeah Mike... teach him vector math, but make it snappy...

(Some of us spent several years in university learning vector math.)

Dan.

poslundc wrote:

LOst? wrote:

Vector Math, no I've never worked with it. Can you teach me quick?

2D determinant (cross product), teach me quick, this is heavy stuff :P

Yeah Mike... teach him vector math, but make it snappy...

(Some of us spent several years in university learning vector math.)

Dan.

lol

Come on. I only need the goodies!

lol!

Vectors 101

A vector is line with a direction. It can be formed by subtracting 2 points. The first point is an anchor, the second gives direction.

Vectors can be added, subtracted. They can be multiplied in 2 ways - through dot products and cross products. Without delving to deep into theory, a dot product can be thought as the projection of one vector upon another while a cross product returns a vector that is perpendicular to the 2 vectors that were crossed (useful for finding a normal to a plane - or if used right, the distance between a point and a line which is how I'm using it.)

A dot is calculated by multiplying like terms between the vectors and adding the results (giving a scalar value which is a magnitude.)

A cross is a bit more complicated but for 2D is formed by multiplying and adding/subtracting terms to form a new vector - or in the case of a Determinent, adding and subtracting the values.

Bah. Read a physics book. Learn. Enjoy the fruits of your own labors (labours) :)

There's a lot more to it than this. I can't prove my theories to you without you having basic knowledge - but if you learn vectors, yu will be amazed at how many sin/cos/tan/arctan type trig functions turn into simple additions, subtractions, and multiplies.

Determinant:

A determinant is a certain kind of function that associates a real number with a square Matrix.

Code:

A = [ a b]
[ c d]

det(A) = a*d-b*c

Cross product
If u = (u(1), u(2), u(3)) and v = (v(1), v(2), v(3)) are vectors in 3-space, then the cross product u x v is the vector defined by:
u x v = (u(2)*v(3)-u(3)*v(2), u(3)*v(1)-u(1)*v(3), u(1)*v(2)-u(2)*v(1))
and is perpendicular to both u and v

:)

lol. That's straight out of a linear Algebra book :)

I'm waiting for the full N-Space theory stuff next to confuse him :)

BTW, yes - my method works for any arbitrary angle - and can work across tile boundaries if you want to define you collision set in the world as a group of lines - though there are issues with this that involve finding the correct line to check against :)

Just define a different vector for each angle.

22.5 degrees - The A vector defined as (4,8).
0 degress - (0, 8)

So, your "Vector" variable? Can I see the typedef of it?

Let me guess (Ok, I'm really blind, so help me):

typedef struct
{
int x; // X coordinate
int y; // Y coordinate
int speed_x; // Horizontal speed
int speed_y; // Vertical speed
} Vector;

I really should learn some math :P
This is heavy stuff!

typedef struct _VECTOR2D {
s32 x;
s32 y;
} VECTOR2D;

or you can use an array as well. Just need 2 values for a 2D array like I'm showing in my samples. (8,8), (8,0), etc.

truth is in our engine its defined as an f16_16.

Code:

#include <math.h>
#include "vector.h"

//-----------------------------------------------------------------------------
// Name:
// Desc:
//-----------------------------------------------------------------------------

void CVector::operator = (CVector v)
{
x = v.x;
y = v.y;
z = v.z;
}

//-----------------------------------------------------------------------------
// Name:
// Desc:
//-----------------------------------------------------------------------------

CVector CVector::operator - (CVector a)
{
CVector t;

t.x = x - a.x;
t.y = y - a.y;
t.z = z - a.z;

return t;
}

//-----------------------------------------------------------------------------
// Name:
// Desc:
//-----------------------------------------------------------------------------

float CVector::Lenght ()
{
return (float)sqrt (x*x+y*y+z*z);
}

//-----------------------------------------------------------------------------
// Name:
// Desc: Convert to uint vector whit lenght 0-1
//-----------------------------------------------------------------------------

void CVector::Normalize ()
{
float len = 1 / Lenght ();

x*=len; y*=len; z*=len;

}

//-----------------------------------------------------------------------------
// Name: Dot product
// Desc: a Dot b = |b|*|a| * cos (theta)
//
// a dot b > 0 less than 90 apart
// a dot b = 0 exactly 90 apart
// a dot b < 0 more than 90 apart
//
//-----------------------------------------------------------------------------

float CVector::Dot (CVector v)
{
return ( x*v.x + y*v.y + z*v.z);
}

//-----------------------------------------------------------------------------
// Name:
// Desc:
//-----------------------------------------------------------------------------

void CVector::Cross (CVector a, CVector b)
{
x = a.y*b.z - a.z*b.y;
y = a.z*b.x - a.x*b.z;
z = a.x*b.y - a.y*b.x;
}

I looked at my friend's 3d engine, and guess what I found :P

Imagine that :)

Truthfully, creating a vector class is almost always one of the tasks given to newbie C++ programmers. You can find millions of these around :)

Here's a structure for a vector that I am working on... the idea is to split the components of a vector logically into it's fixed point and tile-based components using a series of unions. By accessing a vector's x_tile member, you get which tile your entity is located in, x_whole gives you the true x-component and so forth. This allows for 16.16 fixed point math and easy tile-based management...

This of course, assumes 8x8 logical tiles are being used for collision detection/response, it's not to difficult to change this to 16x16.

Code:

struct tile_vector {

union { /* Allow X Coordinate to be accessed raw, or via it's components. */

int x;

struct {

short x_fraction:16; /* for 16.16 fixed point. */

union {

short x_whole:16;

struct {
short x_subtile:3;
short x_tile:13;
}; /* The whole bits can be divided into the tile and sub_tile position. */

}; /* ends whole component union */

}; /* ends anonymous struct x_bits */

}; /* ends anonymous union x */

union { /* Allow Y Coordinate to be accessed raw, or via it's components. */

int y;

struct {

short y_fraction:16; /* for 16.16 fixed point. */

union {

short y_whole:16;

struct {
short y_subtile:3;
short y_tile:13;
}; /* The whole bits can be divided into the tile and sub_tile position. */

}; /* ends whole component union */

}; /* ends anonymous struct y_bits */

}; /* ends anonymous union y */

}; /* ends struct tile_coord */

Of course, you can always access the pure x/y components if you wish as these would be used for normal math functions.

I'm always very wary of bitfields. ANSI C doesn't define the way that the data has to be stored such that one compiler may store data Big Endian, another Small, another reverse, etc.

Call me paranoid, but I like to access my Fixed Data with Macros and bit operators so I know exactly how my data is stored and used.

I understand your concern... MACROS are definately a safe solution for accessing these sorts of things and on top of that you are also completely certain of what sort of code is being generated to access the various fields.

However, if you keep your development environment sufficiently consistent, the bitfield issue should not cause any problems, also the edian issue can probably be handled with #ifdefs

I meant this as a suggestion, but thanks for the feedback, I still have a ways to go with my GBA development and I may drop this union/struct idea all together.

Hey Mike, this was part of your post on the first page:

Miked0801 wrote:

Assume that all points to the right of this line are solid. To test collision, get where on the char you wish to check, take the 2D determinant (cross product) of the line vector against the vector formed from your point and the starting point of the edge vector. If it's positive, you're colliding, negative, you're not, 0, you're on the line. Very qucik and can be turned into a reflection or slide along endge with ease.

Can you go into detail regarding expanding this method for sliding along an edge? I think I get the general idea, to use a projection, but I'm having problems fully understanding it. Any clarification would be appreciated.

Thanks,
Andrew

Pulling up the old archives huh. Haven't seen that in a while :)

Sliding - use the previously mentioned method for determining a collision has occured. Move the offending object out of collision by either backing him up 1 tics movement (quick, but will cause some slighy jiggling of the sprite as it moves along the edge), or my determining at what point the movement vector crossed into the target object and placing him there (the correct dot product will tell you the magnitude along the wall where the collide occured. A mul and an add per coordinate gets you the location.)

Now, determine which direction relative to the edge normal that the player wishes to move (more dot/determinent quick work.) and slide the player in that direction using the walls positive or negative vector.

Easy right :)

The cool thing about this approach is that it works in N space for any vectors (2D, 3D, nD.)

Enjoy

Thanks a lot for the reply, Mike. It seems really straightforward, and I understand all of it except for one part:

Quote:

(the correct dot product will tell you the magnitude along the wall where the collide occured. A mul and an add per coordinate gets you the location.)

Using the example below, AB is my collision vector, CD is my movement vector, and point E is where the vectors meet.

AB = {8,8}
CD = {-4,2}
AD = {1,4}

I guess my question is that, which vectors do I need to take the dot product of? I assume that it's one of these two pairs,

AB dot CD = 8 * -4 + 8 * 2 = -32 + 16 = -16
AB dot AD = 8 * 1 + 8 * 4 = 8 + 32 = 40

but I haven't been able to figure out how either of those values relates to point E.

Code:

A-+-+-+-+-+-+-+-+
|X| | | | | | | |
+-\-+-+-+-+-+-+-+
|X|X| | | | | | |
+-+-\-+-+-C-+-+-+
|X|X|X| | | | | |
+-+-+-E-+-+-+-+-+
|X|X|X|X| | | | |
+-D-+-+-\-+-+-+-+
|X|X|X|X|X| | | |
+-+-+-+-+-\-+-+-+
|X|X|X|X|X|X| | |
+-+-+-+-+-+-\-+-+
|X|X|X|X|X|X|X| |
+-+-+-+-+-+-+-\-+
|X|X|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-B

The problem is to get the exact point of collison along the line, you have to normalize a vector which is expensive (read a coupl of divides and sqrts or edists and inverse muls if you're careful.) That's the reason in our engine, I just back them up a tic and deal with a touch of jiggling as they get close to the wall. I've run out of time tonight, but I'll post the exact formula tomorrow after I get some work done :)

You could also solve the simultanous system of equations that the 2 lines represent, but that'd be a bit slow as gausian elimination requires some horse power :)

gbadev.org forum archive

Coding > Collision detection with 45 degree tiles?

#15364 - LOst? - Wed Jan 21, 2004 1:11 pm

#15375 - batblaster - Wed Jan 21, 2004 4:43 pm

#15378 - yaustar - Wed Jan 21, 2004 5:40 pm

#15380 - LOst? - Wed Jan 21, 2004 7:19 pm

#15382 - yaustar - Wed Jan 21, 2004 7:24 pm

#15385 - sajiimori - Wed Jan 21, 2004 8:34 pm

#15392 - Miked0801 - Wed Jan 21, 2004 10:02 pm

#15408 - Derek - Thu Jan 22, 2004 6:02 am

#15409 - Derek - Thu Jan 22, 2004 6:14 am

#15427 - LOst? - Thu Jan 22, 2004 2:26 pm

#15429 - LOst? - Thu Jan 22, 2004 2:30 pm

#15433 - poslundc - Thu Jan 22, 2004 3:16 pm

#15435 - LOst? - Thu Jan 22, 2004 5:34 pm

#15436 - Miked0801 - Thu Jan 22, 2004 6:53 pm

#15437 - alek - Thu Jan 22, 2004 6:54 pm

#15438 - Miked0801 - Thu Jan 22, 2004 7:00 pm

#15464 - LOst? - Thu Jan 22, 2004 10:38 pm

#15471 - Miked0801 - Thu Jan 22, 2004 11:09 pm

#15472 - LOst? - Thu Jan 22, 2004 11:13 pm

#15475 - Miked0801 - Thu Jan 22, 2004 11:17 pm

#15803 - NitroSR - Fri Jan 30, 2004 5:47 pm

#15808 - Miked0801 - Fri Jan 30, 2004 7:19 pm

#15810 - NitroSR - Fri Jan 30, 2004 7:32 pm

#27155 - abilyk - Mon Oct 04, 2004 9:38 pm

#27215 - Miked0801 - Wed Oct 06, 2004 7:04 pm

#27218 - abilyk - Wed Oct 06, 2004 9:51 pm

#27231 - Miked0801 - Thu Oct 07, 2004 1:49 am