3d tile game

pretty simple question for anyone who knows the answer i guess.

I'm making a 3d game which is tile based. I've basically got loads of tiles
set out as the floor, they're all completely flat so y = 1.

What i want to do is have the user click somewhere on the screen (using a
normal 2d screen cursor) and have it select that tile.

The old way of doing this would be dividing the mousey and y by the size of
the tiles then rounding it. This can't be dont in this case because of the
perspective.


I figure that i've got to do something with vectors, probably from the
camera vector to the point that was clicked.. but i'm not sure.

The tiles are generated using a simple 2 triangle vector then drawn over and
over again to create the landscape.


I figure that if i can get the 'impact' vector from the point clicked i can
work it out the old way by dividing by the tile size to get which tile was
clicked.

I didn't really concentrate in maths when we were doing all the triangle
stuff - and I'm regretting it now. I'm really trying though - so if anyone
can suggest some resources I would be really grateful.

"gappy" <fake@email.com> wrote in message
news:3efda3c1$0$45180$65c69314@mercury.nildram.net ...
> pretty simple question for anyone who knows the answer i guess.
>
> I'm making a 3d game which is tile based. I've basically got loads of
tiles
> set out as the floor, they're all completely flat so y = 1.
>
> What i want to do is have the user click somewhere on the screen (using a
> normal 2d screen cursor) and have it select that tile.
>
> The old way of doing this would be dividing the mousey and y by the size
of
> the tiles then rounding it. This can't be dont in this case because of the
> perspective.
>
>
> I figure that i've got to do something with vectors, probably from the
> camera vector to the point that was clicked.. but i'm not sure.
>
> The tiles are generated using a simple 2 triangle vector then drawn over
and
> over again to create the landscape.
>
>
> I figure that if i can get the 'impact' vector from the point clicked i
can
> work it out the old way by dividing by the tile size to get which tile was
> clicked.
>
> I didn't really concentrate in maths when we were doing all the triangle
> stuff - and I'm regretting it now. I'm really trying though - so if anyone
> can suggest some resources I would be really grateful.

Depends on the language and platform you are using, but here are a few ideas
for you. The first is mapping, so that you basically have each pixel equal
1 unit. That way, if the mouse is loacted at pixel (85, 192), it will know
exactely what is there. The faults of this are major problems when changing
resolution and it can slow down the game if not done right. So languages
have built in code in their library that can automatically retrieve the
color where you are clicking or know if you are on an object or not. Also,
you could start the mouse at center and record the movements, so if the
mouse went 3cm to the right, you would know what is there.

> Depends on the language and platform you are using, but here are a few
ideas
> for you. The first is mapping, so that you basically have each pixel
equal
> 1 unit. That way, if the mouse is loacted at pixel (85, 192), it will
know
> exactely what is there. The faults of this are major problems when
changing
> resolution and it can slow down the game if not done right. So languages
> have built in code in their library that can automatically retrieve the
> color where you are clicking or know if you are on an object or not.
Also,
> you could start the mouse at center and record the movements, so if the
> mouse went 3cm to the right, you would know what is there.

hmm tahnks, but the problem with that is that the grid is in perspective..
so shows more tiles at the top than it does at the bottom.

So i'd have to hard code the stuff to work out how many tiles there are at
the top - which i really dont wanna do..

> hmm tahnks, but the problem with that is that the grid is in perspective..
> so shows more tiles at the top than it does at the bottom.


That's severely weird...

The whole point of doing tile-based games was to
use orthogonal projection so the size of every tile
is the same.

If you're going to do perspective-mapping, why are
you bothering with tiles instead of doing true 3d?

--
Hugh Bothwell hugh_bothwell@hotmail.com Kingston ON Canada
v3.1 GCS/E/AT d- s+: a- C+++ L++>+++$ P+ E- W+++$ N++ K? w++ M PS+
PE++ Y+ PGP+ t-- 5++ !X R+ tv b++++ DI+++ D-(++) G+ e(++) h-- r- y+

well it is true 3d, but i'm only viewing it from one angle.. kind of the
same perspective as AOM and other top down games like that.

I'm using tiles (not 2d tiles) for the landscape..

"gappy" <fake@email.com> wrote in message
news:3efeefe1$0$45171$65c69314@mercury.nildram.net ...
> well it is true 3d, but i'm only viewing it from one angle.. kind of the
> same perspective as AOM and other top down games like that.
>
> I'm using tiles (not 2d tiles) for the landscape..
>
>

I think you were on the right track with the vector idea... You could create
a new vector and then trace a line until you make contact with a tile... The
tricky part is pointing the vector...

Well, since the camera is pointing in the correct general direction, what
we're really talking about is a modification to the camera's vector.

At this point, the only help I can offer is to tell you to post this
question in comp.graphics.algorithms (some of the guys their can answer
question like this in their sleep)...

Tony

You should be able to calculate the pointer vector from eyepoint to mouse
coordinate
and reverse transform it thru the view matrix.
Then your tiles (square??) correspond to known xyz coordinates in world space
as well, you could do
3D triangle intercept calculations (square is 2 triangles) to figure which tile
that pointer vector intersects,
giving you the tile selection info you need.

I did this in DirectX (its in one of the sample progs in the SDK)


D3DXVECTOR3 v;
v.x = (((2.0f * save_ptCursor.x) / m_d3dsdBackBuffer.Width ) - 1) /
m_matProj._11;
v.y = -(((2.0f * save_ptCursor.y) / m_d3dsdBackBuffer.Height) - 1) /
m_matProj._22;
v.z = 1.0f;

D3DXMatrixInverse(&mPick, NULL, &m_matView); // Get the inverse view matrix
-- will reverse to world coords??

// Transform the screen space pick ray into 3D space (vector defined by a
points and a direction vector)
vPickRayDir.x = v.x * mPick._11 + v.y * mPick._21 + v.z * mPick._31;
vPickRayDir.y = v.x * mPick._12 + v.y * mPick._22 + v.z * mPick._32;
vPickRayDir.z = v.x * mPick._13 + v.y * mPick._23 + v.z * mPick._33;
vPickRayOrig.x = mPick._41;
vPickRayOrig.y = mPick._42; // eye point
vPickRayOrig.z = mPick._43;


intercept with one triangle (you will loop thru all triangles making up your
tile map...)



BOOL IntersectTriangle( const D3DXVECTOR3& orig, //point
const D3DXVECTOR3& dir, //direction
of view line
D3DXVECTOR3& v0, /// 3 points
define plane -- the triangle being tested
D3DXVECTOR3& v1,
D3DXVECTOR3& v2)
{
FLOAT t, u, v;

D3DXVECTOR3 edge1 = v1 - v0; // Find vectors for two edges sharing vert0
D3DXVECTOR3 edge2 = v2 - v0;

D3DXVECTOR3 pvec; // Begin calculating determinant - also used to
calculate U parameter
D3DXVec3Cross(&pvec, &dir, &edge2); // gets the normal vector of plane

FLOAT det = D3DXVec3Dot(&edge1, &pvec); // If determinant is near zero, ray
lies in plane of triangle
if (det < 0.0001f) return(FALSE);

D3DXVECTOR3 tvec = orig - v0; // Calculate distance from vert0 to ray
origin

u = D3DXVec3Dot(&tvec, &pvec); // Calculate U parameter and test bounds
if ((u < 0.0f) || (u > det)) return(FALSE);

D3DXVECTOR3 qvec; // Prepare to test V parameter
D3DXVec3Cross(&qvec, &tvec, &edge1);

v = D3DXVec3Dot(&dir, &qvec); // Calculate V parameter and test bounds
if ((v < 0.0f) || (u + v > det)) return(FALSE);

t = D3DXVec3Dot(&edge2, &qvec); // Calculate t, scale parameters, ray
intersects triangle

// t is the z depth distance (distance from eye point)

if (t < 0.0f) return(FALSE); // dist in front (y) is behind
viewpoint ????

return(TRUE);
}




This did work for a targeter I used in 3D for billboards, the basic mathematics
are
there (dot products and cross products etc...)

You can probably find more on subject if you look on game programming websites
keywords line intersect plane




Tony Di Croce wrote:

> "gappy" <fake@email.com> wrote in message
> news:3efeefe1$0$45171$65c69314@mercury.nildram.net ...
> > well it is true 3d, but i'm only viewing it from one angle.. kind of the
> > same perspective as AOM and other top down games like that.
> >
> > I'm using tiles (not 2d tiles) for the landscape..
> >
> >
>
> I think you were on the right track with the vector idea... You could create
> a new vector and then trace a line until you make contact with a tile... The
> tricky part is pointing the vector...
>
> Well, since the camera is pointing in the correct general direction, what
> we're really talking about is a modification to the camera's vector.
>
> At this point, the only help I can offer is to tell you to post this
> question in comp.graphics.algorithms (some of the guys their can answer
> question like this in their sleep)...
>
> Tony

Hey thanks, I have no doubt that this will be useful - It should be easier
for me because the tiles y coord is always 1.


"Eternal Vigilance" <wotan@oneeye.com> wrote in message
news:3F0157B5.806821DF@oneeye.com...
>
> You should be able to calculate the pointer vector from eyepoint to mouse
> coordinate
> and reverse transform it thru the view matrix.
> Then your tiles (square??) correspond to known xyz coordinates in world
space
> as well, you could do
> 3D triangle intercept calculations (square is 2 triangles) to figure which
tile
> that pointer vector intersects,
> giving you the tile selection info you need.
>
> I did this in DirectX (its in one of the sample progs in the SDK)
>
>
> D3DXVECTOR3 v;
> v.x = (((2.0f * save_ptCursor.x) / m_d3dsdBackBuffer.Width ) - 1) /
> m_matProj._11;
> v.y = -(((2.0f * save_ptCursor.y) / m_d3dsdBackBuffer.Height) - 1) /
> m_matProj._22;
> v.z = 1.0f;
>
> D3DXMatrixInverse(&mPick, NULL, &m_matView); // Get the inverse view
matrix
> -- will reverse to world coords??
>
> // Transform the screen space pick ray into 3D space (vector defined
by a
> points and a direction vector)
> vPickRayDir.x = v.x * mPick._11 + v.y * mPick._21 + v.z * mPick._31;
> vPickRayDir.y = v.x * mPick._12 + v.y * mPick._22 + v.z * mPick._32;
> vPickRayDir.z = v.x * mPick._13 + v.y * mPick._23 + v.z * mPick._33;
> vPickRayOrig.x = mPick._41;
> vPickRayOrig.y = mPick._42; // eye point
> vPickRayOrig.z = mPick._43;
>
>
> intercept with one triangle (you will loop thru all triangles making up
your
> tile map...)
>
>
>
> BOOL IntersectTriangle( const D3DXVECTOR3& orig, //point
> const D3DXVECTOR3& dir,
//direction
> of view line
> D3DXVECTOR3& v0, /// 3
points
> define plane -- the triangle being tested
> D3DXVECTOR3& v1,
> D3DXVECTOR3& v2)
> {
> FLOAT t, u, v;
>
> D3DXVECTOR3 edge1 = v1 - v0; // Find vectors for two edges sharing
vert0
> D3DXVECTOR3 edge2 = v2 - v0;
>
> D3DXVECTOR3 pvec; // Begin calculating determinant - also used to
> calculate U parameter
> D3DXVec3Cross(&pvec, &dir, &edge2); // gets the normal vector of
plane
>
> FLOAT det = D3DXVec3Dot(&edge1, &pvec); // If determinant is near
zero, ray
> lies in plane of triangle
> if (det < 0.0001f) return(FALSE);
>
> D3DXVECTOR3 tvec = orig - v0; // Calculate distance from vert0
to ray
> origin
>
> u = D3DXVec3Dot(&tvec, &pvec); // Calculate U parameter and test
bounds
> if ((u < 0.0f) || (u > det)) return(FALSE);
>
> D3DXVECTOR3 qvec; // Prepare to test V
parameter
> D3DXVec3Cross(&qvec, &tvec, &edge1);
>
> v = D3DXVec3Dot(&dir, &qvec); // Calculate V parameter and test
bounds
> if ((v < 0.0f) || (u + v > det)) return(FALSE);
>
> t = D3DXVec3Dot(&edge2, &qvec); // Calculate t, scale parameters, ray
> intersects triangle
>
> // t is the z depth distance (distance from eye point)
>
> if (t < 0.0f) return(FALSE); // dist in front (y) is behind
> viewpoint ????
>
> return(TRUE);
> }
>
>
>
>
> This did work for a targeter I used in 3D for billboards, the basic
mathematics
> are
> there (dot products and cross products etc...)
>
> You can probably find more on subject if you look on game programming
websites
> keywords line intersect plane
>
>
>
>
> Tony Di Croce wrote:
>
> > "gappy" <fake@email.com> wrote in message
> > news:3efeefe1$0$45171$65c69314@mercury.nildram.net ...
> > > well it is true 3d, but i'm only viewing it from one angle.. kind of
the
> > > same perspective as AOM and other top down games like that.
> > >
> > > I'm using tiles (not 2d tiles) for the landscape..
> > >
> > >
> >
> > I think you were on the right track with the vector idea... You could
create
> > a new vector and then trace a line until you make contact with a tile...
The
> > tricky part is pointing the vector...
> >
> > Well, since the camera is pointing in the correct general direction,
what
> > we're really talking about is a modification to the camera's vector.
> >
> > At this point, the only help I can offer is to tell you to post this
> > question in comp.graphics.algorithms (some of the guys their can answer
> > question like this in their sleep)...
> >
> > Tony
>

gappy wrote:
> pretty simple question for anyone who knows the answer i guess.
>
> I'm making a 3d game which is tile based. I've basically got loads of tiles
> set out as the floor, they're all completely flat so y = 1.
>
> What i want to do is have the user click somewhere on the screen (using a
> normal 2d screen cursor) and have it select that tile.
>
> The old way of doing this would be dividing the mousey and y by the size of
> the tiles then rounding it. This can't be dont in this case because of the
> perspective.
>
>
> I figure that i've got to do something with vectors, probably from the
> camera vector to the point that was clicked.. but i'm not sure.
>
> The tiles are generated using a simple 2 triangle vector then drawn over and
> over again to create the landscape.
>
>
> I figure that if i can get the 'impact' vector from the point clicked i can
> work it out the old way by dividing by the tile size to get which tile was
> clicked.
>
> I didn't really concentrate in maths when we were doing all the triangle
> stuff - and I'm regretting it now. I'm really trying though - so if anyone
> can suggest some resources I would be really grateful.
>
>
>

Another option is to let the rendering subsystem do the work for you
using openGL selection or whatever the D3D equivallent is.

Peter.

gappy wrote:

> Hey thanks, I have no doubt that this will be useful - It should be easier
> for me because the tiles y coord is always 1.
>
>

yeah if your map is flat (y constant) your tile vertices will be only in x z
coordinates in a regular pattern
( so that you can do loops while traversing the triangles being checked....)

but since you are using perspective, and I assume you are looking at map with a
orthoganal view
(eye isnt at y=1....) the direction of the eye-mouse vector will have all 3
xyz components.