Archived

This topic is now archived and is closed to further replies.

leeor_net

Bounding Box Algorithim

Recommended Posts

I''m assuming the objects on your isometric map aren''t in 3D. So, making a bounding box might not seem a good idea for collision detection. There are 2 ways about this

1) First method : What you basically do is obtain the ''shadow'' directly underneath all objects on the screen.. Then you check for overlapping shadows. Take note that this method does not take care of collisions for objects at different heights.. assuming all your objects are on the ground and there''re no aerial objects, this will work fine

Its not to difficult to generate your shadows at runtime but i''d prefer to draw a shadow bitmap mask ready for each object that I have.

2) second method (which takes into effect ) is to segment out your objects into different ''height'' segments. for example, say you had a huge open umbrella planted into the ground.. The thing is , a dog would only collide with the umbrella at the middle (the umbrella pole/stick/whateveryoucallit) , but a bird flying at the same level with the umbrella''s flaps will collide with the umbrella earlier. So what you do is, specify a certain set of height-levels. For example height level1 : 20 pixels from the ground up, height level2 : the next 20 pixels upwards. Then, at each height level, you have a ''shadow'' representing the size of the object AT that height level, that you can use for collision detection. This has the effect of making an abstract representation of a mold of your 2d object , and you will get even more accurate collision detection than a bounding box.

So back to the umbrella, you would have say , a tiny little shadow (at height level1) : this is the umbrella pole. Maybe at about height level 3 , you have the umbrella flaps (which would have a larger shadow). When you do collision detection between the umbrella and the bird(assuming its also flying at height level 3), you will be using the umbrella''s shadow at height level 3.. ,and for the dog, you will be using the umbrella''s shadow at height level 1

The only drawback with this is that when you design your 2d sprites, you will have to pre-visualize how your sprite is going to be segmented, (Eg: make sure that the umbrella''s pole length will not end somewhere in the middle of a height level) ie everything would have to correspond to the height level boundaries to look right in the game.


Regards
Eddie

Share this post


Link to post
Share on other sites
Thanks for the help. I''ll remember that for another project.

I guess I wasn''t too clear.

I''m looking for a way to test what tile the mouse is on.

The engine is a little primitive, however, it''s meant to be that way.

I have the map drawn on the screen as a diamond. So the tiles are always in one place.

How would I detect which tile the mouse is on using this layout?

Thanks

Leeor...

[Edited by - leeor_net on June 20, 2009 3:57:28 AM]

Share this post


Link to post
Share on other sites
If you check the resources / articles link on this site there are a few good articles on how to do screen to world co-ord conversions.

A quick run down of the main ways of doing this are:

1: Maths
2: Seperate screen with a colour representing the tile to pick
3: Mouse maps ALA TANSTAAFL''s mouse maps (and my height enabled mouse map change)

Taking the route of the mouse maps these are documented pretty well, I''m not near my main PC with the details of how it works, also TANSTAAFL''s book has been packed away... But here''s a list of some of the links on this site:

Main List of Iso Articles http://www.gamedev.net/reference/list.asp?categoryid=44

TANSTAAFL Iso & Hex part 1 : http://www.gamedev.net/reference/articles/article747.asp

TANSTAAFL Iso & Hex part 1 : http://www.gamedev.net/reference/articles/article748.asp

My version of TANSTAAFL''s mouse maps that allow you to use height in your maps: http://www.gamedev.net/reference/articles/article2026.asp

When I find my code in tons of trouble,
Friends and colleages come to me,
Speaking words of wisdom:
"Write in C."

Share this post


Link to post
Share on other sites
here is some code how to do it:

inline bool PointIsInTriangle(int x1,int y1,int x2,int y2,int x3,int y3,int x,int y)
{
int a,b,c;
a = (x2 - x1) * (y - y1) - (y2 - y1) * (x - x1);
b = (x3 - x2) * (y - y2) - (y3 - y2) * (x - x2);
c = (x1 - x3) * (y - y3) - (y1 - y3) * (x - x3);
if ((a>=0 && b>=0 && c>=0) || (a<0 && b<0 && c<0))
return TRUE;
return FALSE;
}
MouseX=Input->GetMouseX();
MouseY=Input->GetMouseY();
int rectX=(MouseX+Xoffset)/TILE_W;
int rectY=((MouseY+Yoffset)/TILE_H)*2;
int MouseInRectX=(MouseX+Xoffset)%TILE_W;
int MouseInRectY=(MouseY+Yoffset)%TILE_H;
int RegionDX,RegionDY;
if (PointIsInTriangle(0,0,TILE_W/2,0,0,TILE_H/2,MouseInRectX,MouseInRectY))
{
RegionDX=-1;
RegionDY=-1;
}
else
if (PointIsInTriangle(TILE_W/2,0,TILE_W,0,TILE_W,TILE_H/2,MouseInRectX,MouseInRectY))
{
RegionDX=0;
RegionDY=-1;
}
else
if (PointIsInTriangle(0,TILE_H/2,TILE_W/2,TILE_H,0,TILE_H,MouseInRectX,MouseInRectY))
{
RegionDX=-1;
RegionDY=1;
}
else
if (PointIsInTriangle(TILE_W,TILE_H/2,TILE_W,TILE_H,TILE_W/2,TILE_H,MouseInRectX,MouseInRectY))
{
RegionDX=0;
RegionDY=1;
}
else
{
RegionDX=0;
RegionDY=0;
}
xTile=rectX+RegionDX;
yTile=rectY+RegionDY;

Share this post


Link to post
Share on other sites
Prepare yourself... One of my favorite pastimes is attempting to devise methods of detecting which tile was clicked in an isometric game without a mousemap. Thus when I saw this post I needed little prompting to attack the problem with renewed vigour. This is my most successful result yet, its the shortest, fastest and easiest to understand method I''ve come up with. Also it is 100% accurate, unlike the other methods i''ve thought up. I will give the code first, then an explanation in case you are interested... Also, If your tiles are other than 128x64 then it would be advisable to read it.

 
tileX = MouseX / 128;
tileY = MouseY / 128; //64 * 2 , as its isometric there are twice as many rows

mouse_in_tileX = X % 128; mouse_in_tileY = Y % 64;
twice_mouse_in_tileY = mouse_in_tileY << 1;

if( mouse_in_tileX < (-twice_mouse_in_tileY + 64))
{
tileX --;tileY--;
}
else if ( mouse_in_tileX < (twice_mouse_in_tileY - 64))
{
tileX--;tileY++;
}
else if( mouse_in_tileX > (-twice_mouse_in_tileY+ 192))
tileY++;
else if( mouse_in_tileX > (twice_mouse_in_tileY + 64))
tileY--;

/**************** Only use below If Map is drawn a bit to the left and Up to remove jagged edges
if(tileY%2 != 0)
tileX++;

tileY++;
****************/


The basic idea of this method is to, based on the y location find the right or left most value of the tile and see if the mouse x exceeds or is less than that that value.

I thought to represent an isometric tile by creating 4 lines such that they intersected a certain way creating a 128x64 tile. I then planned to test if the equations were correct and observe some test cases. I at first thought the difference of coordinate systems would be a difficulty ; the Coordinate system of computers is different from that most often used in mathematics. The y coordinate increases downards instead of upwards, however the 4th/lower right quadrant of a 2D Cartesian plane represents the monitor quite well. One simply has to invert the y coordinate.



I knew the slope of my tile was .5 as its dimensions were 128x64.

Based on that I knew if the line were to have a y intercept at -32 (I had to subtract 32 from y) it have an x intercept of 64. The second line was as the first but simply with an opposite slope. The upper right line had a horizontal displacement of -64 and the bottom right had a horizrontal displacement but also a vertical one of 64 so that it could intersect with the lower left at -64.
.


I then wrote the equations and sought to compactiy them.

y1 = .5x - 32
y2 = -.5x - 32
y3 = .5x(x - 64) -64
y4 = -.5(x - 64)

y3 and y4 reduce to:

y3 = .5x - . 532- 64 = .5x - 96
y4 = -.5x - -(.5)64 = -.5x + 32

Solving for x gives:

x1 = 2y + 64
x2 = -2y - 64
x3 = 2y + 192
x4 = -2y + 64

Because of the behavior/slope of the lines I knew that only one condition at a time could be met if I required mouseX be less than x_line at x1 and x2 (top left and bottom left) and greater for x3 and x4 (top and bottom right). For example with an x at 76 and a y at 62 the only condition that could be met is an mouseX > x3, for at that point mouseX < x4 and > x1 and x2. If you dont believe me test it, you but have to look at the lines.

And that is my method, I hope this was helpful to you.

*This method can be used for any quadrilateral.

Share this post


Link to post
Share on other sites
ehh.. hmmm.. I just noticed you stated you draw your map the other way, the diamond way, this method is meant for the rectangular isometric method. It can be modified to work with that method but it borders on complexion and must be tailored specifically to how you implemented your diamond staggered drawing.

Share this post


Link to post
Share on other sites
Just Reverse your drawing algorithm, ie

int convert_mouse_to_map(int MouseX, int MouseY)
{
int sx = MouseX + CameraX;
int sy = MouseY + CameraY;

MouseTileX = sx/32 + sy/16;
MouseTileY = -sx/32 + sy/16;
MouseTileX /= 2;
MouseTileY /= 2;
}

Something like that(64*32 Sized Tiles).

Share this post


Link to post
Share on other sites