Archived

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

Mathematically Identifying Tile Clicked

This topic is 5125 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have come up with a way to identify a clicked tile in an isomertic scene without using a mousemap. It works almost perfectly in a tile scrolled world, it errors when the world is scrolled by pixel for reasons that are related to how this method works. I said earlier that in a tiled scrolled world this method works almost perfectly, this is because I draw with a slight offset, half a tile up and left to get rid of the "jagged" effect of the drawing method i use. Consider the following isometric scene:
___________
| /\  /\ | 
|/  \/  \|
|\  /\  /| 
| \/  \/ | /____ Down half a tile
| /\  /\ | \
|/  \/  \|
|\  /\  /| 
|_\/__\/_|       
Each tile is in the shape, for lack of a better word, of a diamond. The drawing method increments across by the tile width and down half the tile height. This fact coupled with the "diamond" nature of the tiles makes identifying which tile was clicked a bit difficult. Each isometric tile is encased in a rectangular bitmap, and if the same method one would use to detect a clicked tile in a normal rectangular map (TileX = X / SpriteWidth) was used the diamond nature of the tile would cause the wrong tile to be chosen as clicked. However with a bit of manuevering this method can be used in an isometric scene. The first thing is to use the rectangular method to find the clicked tile. This will ignore the inbetween tiles (the tiles with a + going through them). I then multiply the TileY by 2 since the drawing method goes down half a tile thus twice as many tiles are drawn than in a normal rectangular method, and add 1 (a weak hack against the drawing offset to get rid of jaggedness).
   
__________
| /\ | /\ | 
|/  \|/  \|          Isometric Tiles split into their  
|\  /|\  /|    /____ rectangular casing.
|_\/_|_\/_|    \
| /\ | /\ | 
|/  \|/  \|
|\  /|\  /| 
|_\/_|_\/_|    
I use 128x64 tiles for the ground, thus the ratio of the tiles is 2:1. The slope of each side of the tile is .5, so for each line on the sides it should be y = .5x or, x = 2y. This, however, is not the case since the sides of the tiles are not always moving in the same direction as a normal x = 2y graph would.
 /\ /___ m = .5  
/  \\
\  /
 \/

y = .5x
6|     .
 |    / 
4|   /.
 |  /
2| /.
 |/__________
 0 1 2 3 4 5 
So I divided the tile into 4 sections and used different offset methods to extract the x for each.
_______
|a/|\b|
|/_|_\|
|\ | /|   
|c\|/d|         
Section a: x = -2y + 64 Section b: x = 2y + 64 Section c: x = 2y - 64 Section d: x = -2y + 192 I then compare the mouseX with this solved x value. If it is in section a and it is less than the solved x i go up and left, section b, if it is greater, go up and right etc. It works almost perfectly, and would, were it not for the fact that since I start drawing from -64, -32 and not 0,0 the rectangular grid is not entirely accurate. I said earlier that i add 1 to tileY to try to alleviate this but even with this, the accuaracy is only about 90%. If anyone can help, it would be much appreciated.

Share this post


Link to post
Share on other sites
I don''t know whether you are using a square or diamond shaped map? I used a diamond shaped one, with the coordinate axes laid out like this:

+ (xmax,y0)
/ \
/ \
/ \
(x0,y0) + + (xmax,ymax)
\ /
\ /
\ /
+ (ymax,x0)


In order to translate between the map coordinates and the screen coordinates, I used the following procedures:
OffsetX and OffsetY specify the screen position of point (0,0) on the map.
The tiles I used were diamond shaped, 32 pixels high and 64 wide.
The second function is basically derived from the first, i.e., the equations were rearranged.

procedure TForm1.MapToScreen(MapX, MapY: Double; out ScreenX, ScreenY: Integer);
begin
ScreenX := Trunc(32 *(MapY + MapX))- OffsetX;
ScreenY := Trunc(16 *(MapY - MapX))- OffsetY;
end;

procedure TForm1.ScreenToMap(ScreenX, ScreenY: Integer; out MapX, MapY: Double);
var
t1, t2: Integer;
begin
t1 := ScreenX + OffsetX;
t2 := 2 *(ScreenY + OffsetY);
MapX := (t1 - t2)/ 64;
MapY := (t1 + t2)/ 64;
end;

Share this post


Link to post
Share on other sites
Unfortunately that is not what I was looking for, you misunderstood me. I was looking for mouse to world or screen (without a mousemap) and not map to screen and vice versa.

Nonetheless, in case I had misunderstood you and you had meant mouse coordinates by screenX and Y, I tested the code and it did not work.

And to answer your question, I am using the left to right, top to bottom (rectangular) method, hence the jaggedness, to draw the isometric tiles.

Share this post


Link to post
Share on other sites
quote:
So I divided the tile into 4 sections and used different offset methods to extract the x for each.

_______
|a/|\b|
|/_|_\|
|\ | /|
|c\|/d|


Section a: x = -2y + 64
Section b: x = 2y + 64
Section c: x = 2y - 64
Section d: x = -2y + 192




I posted specific equations which only work in an unscrolled world on a tile at (0,0). These are more generic:

Section a: x = 2(vertex_y - mouseY)
Section b: x = 2(mouseY - vertex_y) + 64
Section c: x = 2(mouseY - vertex_y)
Section d: x = 2(vertex_y - mouseY) + 64

This is intepretated as If in section A and less than solved x, up and left else do nothing etc. Also I found that it is section a and c which are giving the trouble...so i guessed correctly, about 88% accuracy.



[edited by - Daerax on November 27, 2003 10:43:24 AM]

[edited by - Daerax on November 27, 2003 10:46:06 AM]

Share this post


Link to post
Share on other sites
To calculate which tile has been clicked in a "typical" isometric game (ie. Diablo-style flat, diamond-shaped tiles) is rather simple.

Assuming diamond shaped tiles, half as high as they are wide.

Assuming the tilemap is stored in a two-dimensional array, such that if the origin of the tilemap were centred on the screen, the first row of the tilemap (ie. tilemap[0,0], tilemap[0,1], ..., tilemap[0,n]) would extend from the centre down to the lower right. The first column of the tilemap (ie. tilemap[0,0], tilemap[1,0], ..., tilemap[m,0]) would extend from the centre down to the lower-left.

Given are:
h, w - the height and width of the tile bitmap. h = w / 2

mx, my - the co-ordinates of the mouse cursor with respect to the upper-left corner of the screen.

scrollx, scrolly - the screen-space co-ordinates of the origin of the tilemap with respect to the upper-left corner of the screen..

We need to calculate:
sx, sy - the screen-space co-ordinates of the mouse cursor with respect to the origin of the tilemap (ie, the top point of the diamond that represents the tile at tilemap[0,0]).

tx, ty - the tile-space co-ordinates of the mouse cursor (ie. the tile the cursor is currently over).

So:

sx = mx - scrollx
sy = my - scrolly

And basic geometry means that:

tx = (sy / h) + (sx / w)
ty = (sy / h) - (sx / w)

Obviously you could rewrite the above to exclude sx,sy.

Also, scrollx, scrolly can be calculated from the player''s location (assuming the player''s feet ar always the centre of the screen) quite simply using the same logic:

(px, py) - player''s location in tile-space.

scrollx = ((px - py) * w * 0.5) + (screenWidth * 0.5)
scrolly = ((px + py) * h * 0.5) + (screenHeight * 0.5)

So, given the player''s location on the tilemap and the co-ordinate''s of the mouse click you can calculate the tile that was clicked.

This may be the same as Useless Hacker''s post, I didn''t compare, sorry.

-hotstone

Share this post


Link to post
Share on other sites
Hotstone:
I wanted to start a thread about my question but I see that someone already did...
I''m working on an isometric game, and I cant find the tile that the mouse is above it.
I saw your answer above, but my tile(0,0) is top left, and tile(n,n) is bottom right...
how can I find the tile?

Share this post


Link to post
Share on other sites
Ah, thank you for the reply hotstone, however i couldn't get your code to work. Perhaps it is because I scroll the world in a different manner (player characters are not always in the center). Nonetheless I have remedied the problem by orienting around the 0 and 2 vertex only , instead of vertex 0 and 1, 1 and 2 and 0,3 and 3,2.


0
1/\3
\/
2

//this requies a 2:1 ratio, i.e. 64x32, 128x64

x = mouseX / width //truncated...
y = mouseY / Height

if mouseX < x * width + width / 2
if mouseY < y * height + heigt/ 2
vertex_y = y * Height
sx = 2 * (vertex_y - mouseY)
if mouseX < sx
upperleft
else
vertex_y = y * Height + height
sx = 2 * (mouseY - vertex_y)
if mouseX < sx
lowerleft
else
if mouseY < y * height + heigt/ 2
vertex_y = y * Height
sx = 2 * (mouseY - vertex_y) + 64
if mouseX > sx
upperright
else
vertex_y = y * Height + Height
sx = 2 * (vertex_y - mouseY) + 64
if mouseX > sx
lowerright



[edited by - Daerax on November 29, 2003 11:28:09 AM]

Share this post


Link to post
Share on other sites
I haven''t read all of the posts above, sorry if I''m repeating someone...

In the editor I''m working on I have went a bit overkill concerning the mouse tile selection but I thought I could explain it anyway

My tiles are in ordinary isometric 2:1 ratio. I’m also using masking to render the tiles since they overlap each other. The tile in the upper left are used to create the lower map.



First I just pick the tile using a bounding box (the dark square bounding one tile in the picture) using mouse/screen coordinates. I store this value in two variables, something like selectedTileX and selectedTileY. Notice that one single bounding box actually overlaps eight different tiles. To find out which tile the mouse actually is over I create eight polygons and perform a point within triangle test to determine which one was selected. The first polygon is made from the upper left tile the second polygon is made from the upper right tile and so on, until I have checked all of the polygons/tiles. I had to break up each tile in 3 shapes to be able to check the polygon, 2 triangles and one square in the middle like so:



When I have found out which polygon the mouse is above I just offset the selectedTileX and selectedTileY variables according to the polygon’s position relative to the parent tile (polygon #5 in pic 1). This offset is different depending on if I am on an even or an uneven tile row. For instance if I am on an uneven row and I clicked the second polygon (polygon #1 when staring at zero) I would add selectedTileX by 1 and substract selectedTileY by 3.

Everyone got that, right? =D This method is pretty fast I think and it doesn’t consume a lot of memory (like a big colour scheme or something).


-----------------------------
www.OddGames.com

Share this post


Link to post
Share on other sites

0
1 /\ 3
\/
2


Actually it had not to do with the vertex i chose to work around (for the left side I use vertex 1, and the right i use 0 and 2) but that I forgot to translate the solved x back to the original screen location as it moves it to 0,0 to solve. So it would get 48 instead of 48 + 128 or 176, or 56 instead of 56 + 640 , 696 .

This line fixed it: sx += width * tilex, where tilex = mouseX / width. Now it truly works with 100% accuracy.

tilex = mouseX / width //truncated...
tiley = mouseY / Height

if mouseX < tilex * width + width / 2
vertex_y = y * Height + Height / 2
if mouseY < tiley * height + height/ 2
sx = 2 * (vertex_y - mouseY)
sx += width * tilex
if mouseX < sx
upperleft
else
sx = 2 * (mouseY - vertex_y )
sx += width * tilex
if mouseX < sx
lowerleft
else
if mouseY < y * height + heigt/ 2
vertex_y = tiley * Height
sx = 2 * (mouseY - vertex_y) + 64
sx += width * tilex
if mouseX > sx
upperright
else
vertex_y = tiley * Height + Height
sx = 2 * (vertex_y - mouseY) + 64
sx += width * tilex
if mouseX > sx
lowerright






[edited by - Daerax on November 29, 2003 8:57:30 PM]

Share this post


Link to post
Share on other sites
ElectronicSandClock:
Do you mean that you store the tiles such that the first row (Tilemap[0,0], Tilemap[1,0], ... Tilemap[n,0]) would go horizontally across the screen?

That''s how I initially did it actually, but I found it complicated virtually every aspect of the program. I later separated the concept of the game-world from the screen''s representation of it by imagining that the world is represented by a piece of grid paper, which is then depicted on the screen in an isometric view.

This made life much much easier - the co-ordinates are more intuitive for AI, etc., and I found some simple formulae (mentioned above) could translate between screen-space and tile-space. Also, even though I was making an iso game, I was basing my game on Moria (similar to Nethack, etc.) so it made sense to have the world as a simple two-dimensional grid.

In short, if you are storing your tiles that way then I don''t know how you''d find the tile co-ord''s unfortunately; probably some fiddly like mousemaps etc. I''m afraid.

-hotstone

Share this post


Link to post
Share on other sites
greetings all =D

I thought i would step in and just pose the question ''why?''

why would you want to do it mathamaticly, when it''s just as easy and sufficantly fast *IMO* when looping through the tiles and checking that the pixel your mouse is over on a given tile image isnt transparent *color key comparison, or alpha byte/bit*

now i know everyone is screaming "GAH! what if i have a 1000x1000 sized tile map? what then mr. smarty pants?"

well i would first wonder if your actualy enumerating all those tiles each frame *and I know your not drawing them all*.

so the first step is before you render your map create a subset of the map, part of the map that is visible,

now that you have that array, your probably only looking at maybe 200 tils at most *depending on tile size and display res i know but lets be realistic=)*

so then you want to what tile your mouse is over, obviously this should be done once, in response to a mouse move or frame update

so you loop through the subset of the map, checking for tiles who''s rectangular boundries fall within the point, when you find one, do a hit-test on the tile''s image *which could mean a lock ,read and unlock on vram but who cares, 1 or two isnt gonna kill ya. when you find the tile that has a positive hit test *mouse is over a part of the image that is opaque, or atleast not fully transparent, then you save the tile''s pointer, you then use that pointer *which could be null* as reference to the tile structure, simple as that, no crazy math=D
and to make things even simpler=D, for each map in the game you could simple generate a boolean hit-test mask in the shape of the sized tile this particular map is using and read from that, totaly removing the lock,read,unlock overhead. so all there is to it is to loop through some tiles and do some point-in-rect tests, sounds simple and straight forward to me=)

ok now I know im gonna get flammed for providing a lo-tech solution, so just be gentle



Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
well.. I suppose that would work too, but I am thinking of implenting zoom in my tile editor also (not done yet though). That way I would be able to see a whole bunch of tiles at one time. But that matter can probably also be solved using color key somehow.. I don''t know

Why do it the easy way when there is a hard!

Share this post


Link to post
Share on other sites
Raymond:

Are you suggesting that he perform a boolean hit-test on a tile mask for each tile currently displayed on the screen, using the current mouse location, and stopping once he gets a succesful hit?

I''m assuming this process is incorporated into the screen-drawing function? (It would be pointless to enumerate the tiles on the screen twice.)

For a standard Diablo-style isometric engine this wouldn''t be a good solution obviously (it''s far easier and quicker to simply convert directly from screen co-ord''s to tile co-ord''s), but it may solve ElectronicSandClock''s problem of calculating the selected tile I guess.

Not sure how you''d solve the related problem of tile-to-screen co-ordinates though (eg. "a ring is lying on the floor at tile co-ordinates [3.5, 7.25] - where should it be drawn on the screen?"). Note that the equations used for this process can be re-arranged to find which tile the mouse is over.

-hotstone

Share this post


Link to post
Share on other sites
You would do a point-in-rect hit test on each visible tile

when one of those becomes true then you do a mask test =)


as for tile to screen coords

that sounds like drawing to me =)

im sure there is some kind of transform you could apply that would map the screen space directly into tile space and back

*rotating and scaling apropriatly*

but thats way over my head =D




Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
So, I started doodling a bit, and here''s what I came up with:

You''re on to something with dividing a tile into the four sections ABCD, but i came to realize that section B is the same as section C, and section D is the same as section A. Really there are only two cases, not four, of these "quarter tile" coordinates.

the width of these rectangular sections is the width of the tile over two, and the height is the height of the tile over two, so it is easy enough to determine which rectangular section a particular point is by division.

//which quartertile are we in?
quartertilecolumn=worldx/(tilewidth/2);
quartertilerow=worldy/(tileheight/2);

//we''ll need these later...
quartertilex=worldx%(tilewidth/2);
quartertiley=worldy%(tileheight/2);

the only difference in the two cases is the slant of the line, one is positive (\) and the other is negative(/), according to their slopes in the coordinate system of the screen. the manner in which you determine the slant of the particular rectangle the mouse resides is to find out if quartertilecolumn plus quartertilerow is an odd number.

within the rectangle, the line is drawn between two corners, either from (0,0) to (w,h) or from (0,h) to (w,0), where w is tilewidth/2 and h is tileheight/2.
based on the linear equations for these lines, we can determine whether a particular point is above, below, or on the line.

equation for (0,0)-(w,h)

(x2-x1)*(y-y1)=(y2-y1)*(x-x1)
(w-0)*(y-0)=(h-0)*(x-0)
w*y=h*x
-h*x+w*y=0

dropp off the =0, and you''ve got a linear equation. for any particular x and y, only 0 means "on the line", positive and negative are on opposite sides of the line, which makes for a really simple test.

say that w and h were both 4(making the tiles 8x8):
x->
y
|
v
0 1 2 3 4
0 0 - - - -
1 + 0 - - -
2 + + 0 - -
3 + + + 0 -
4 + + + + 0

the actual values do not matter, only the sign.

for the other slant (0,h)-(w,0):

(x2-x1)*(y-y1)=(y2-y1)*(x-x1)
(w-0)*(y-h)=(0-h)*(x-0)
w*(y-h)=-h*x
w*y-w*h=-h*x
h*x+w*y-w*h=0

and again drop the =0, and here''s the graph for w and h of 4 for all x and y values within

x->
y
|
v
0 1 2 3 4
0 - - - - 0
1 - - - 0 +
2 - - 0 + +
3 - 0 + + +
4 0 + + + +

how is this all useful? well, based on the quartertile row and column, you can determine which two tiles the mouse might be in, and you can determine the slope of the line bisecting it. with the equations, you can tell what side of the line you are on, which you can use to decide which tile of the two the mouse is in.

is this "better" than a mousemap? no. in fact, it is almost identical to a mousemap. really, you wouldn''t want to calculate with these equations each time the mouse moves. you''d want a lookup table, which would serve exactly the same purpose as a mousemap.

Share this post


Link to post
Share on other sites
I was certain that the method could be reduced to two sections as i noticed certain patterns, I did not however, persue it after I got the 4 section method working, as I was lazy/did not think it was worth it. Hoperfully I shall be able to pursue your method some day, TANSTAAFL.

Indeed this method is basically like a mousemap, without the mousemap, a mathematical representation of one...

Why would I not simply use a mousemap? I have always wondered how to do mouse to tile without a mousemap and thought it would be interesting. I was also lazy and did not want to do the steps required to get a mousemap up and ready. Also I only require this operation to be performed when there is a mouse down event and not during mouse move events, thus i do not require a look up table and use the method as is. Its quite fast used in that way (only in mousedown).


[edited by - Daerax on December 4, 2003 2:17:43 AM]

Share this post


Link to post
Share on other sites
Raymond:
You said: "im sure there is some kind of transform you could apply that would map the screen space directly into tile space and back"

These transforms have already been given by myself and Useless Hacker in a different thread:

tx = ((sx - mapx) / tilewidth) - ((sy - mapy) / tileheight);
ty = ((sx - mapx) / tilewidth) + ((sy - mapy) / tileheight);

and:

sx = ((tilewidth / 2) * tx) - ((tilewidth / 2) * ty) + mapx;
sy = ((tileheight / 2) * tx) + ((tileheight / 2) * ty) + mapy;

where:
(sx,sy) - screenspace co-ordinates.
(tx,ty) - tilespace co-ordinates.
(mapx, mapy) - origin of tilespace in screenspace co-ordinates.
tilewidth, tileheight - dimensions of tile's bitmap (so to speak - you know what I mean I'm sure).

NB: I have tilespace x axis running down and to the right on the screen, and tilespace y axis running down and to the left.

-hotstone

[Edit: Initially referred to Raymond by his login accidentally.]

[edited by - hotstone on December 4, 2003 9:29:45 AM]

Share this post


Link to post
Share on other sites
I made this today. This iso collision function is written in basic but obviously can be converted in any language. The input coordinates should be taken from zero up to the bounds. Rotation as negative. I have barely tested it but 64,32 tiles and 128,64 iso tiles work just fine. Maybe someone can improve the code to take work with any rotation and size.

Function RRectcollision(x,y,w,h,rot#)
a = ((((Cos(rot)*((x/2)-(w/2)/2.5) ) + Sin(rot) * (y-h/2.5))+(w/2))*1.4)-h
b = (((-Sin(rot) * ((x/2)-(w/2)/2.5) ) + Cos(rot) *(y-h/2.5)+h) * 1.4)-3
If a{ 0 Or a} w/2 Or b{h Or b}h+h Then Return True
Return False
End Function

collision = RRectcollision(32,32,64,32,-45)

Edit : replace { with < and } with >


[edited by - Rve on December 5, 2003 1:12:42 AM]

Share this post


Link to post
Share on other sites