• Advertisement

Archived

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

Uneven terrain and mouse clicks

This topic is 6378 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

This problem has been bothering me for a while. Anybody who has played MechCommander, Alpha Centauri, or any of the Exile games from Spiderweb Software will know what I''m talking about. How does mouse feedback work for maps with uneven terrain? I came up with a solution for returning tiles in a 3D tile engine. It involves projecting tile corners into screen space and determining (with a point-in-polygon test) if the mouse pointer is inside any of the tile projections. Could this same technique be effectively applied to a 2D tile engine? Would it be viable to project tile corners onto the screen to determine which tile the mouse is over? That seems like a huge waste of overhead when you''ve got hundreds of tiles displayed at once, because you need to do a point-in-poly test for each one. Any input is greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Hi

I have pretty much teh same problem (well, my graphics engine isn''t done yet but it''s still bugging me)

I''ve come up with this:

- Isometric tiles are always exactly beneath each other. This means you can seperate the screen into mayn columns and only check in those.
- You''ll probably have maximum and minimum heights. this means that only a given number of Tiles can actually be at the position.

This should have narrowed the search down to about ~20-30 tiles (depending on your engine specifications)
This is a lot faster.

I thought of a second method but methinks it''s bad so I won''t post it :)

Hope this helped


- JQ
pmjordan at gmx dot at

lead programmer,
PWC Software

[Edited by - JonnyQuest on January 3, 2005 7:03:16 AM]

Share this post


Link to post
Share on other sites
There''s a tutorial by TANSTAAFL in the resource section here. It''s called mouse maps.

Basically for me all the tiles have a transparent color right? This is what make them Isometric. So now if I think the cursor is in a tile (It passed a simple rectangle test) I retrieve the color of the pixel on the SOURCE surface in the same relative position to the sprite.

For example if I had a tile in the upper left corner of my tilesurface. And My mouse is within a tile on the map that coresponds to this tile. Let''s say it 3 pixels to the left of the tiles rect.left and 10 pixels lower than the tiles rect.top

Well now I just go to that tile on the tilesurface and add 3 to it''s left, 10 to it''s top and retrieve that pixel (Which''d be the theoretical pixel the mouse is over) Now if that pixel is black (My transparent color or colorkey value) then it''s outside the tile, cause that color is not visible on the map! If it''s anything else I''m over part of the tile.

Wow, this all sounds pretty complicated... well read the articale it explains things much better!

See ya,
Ben

Share this post


Link to post
Share on other sites
This won''t work here though...
1) You have to get that triangle test to pass first (think about it and you know why it''s not that easy)
2) At least with me, the tiles are rendered (D3DIM) so you can pretty much forget the idea with mousemaps - there are just too many combinations...



- JQ
pmjordan at gmx dot at

lead programmer,
PWC Software

[Edited by - JonnyQuest on January 3, 2005 7:39:14 AM]

Share this post


Link to post
Share on other sites
Oops.... it was a little unclear.. I didn''t think you were using D3DIM... your right then. Use a polygon test, are you using a triangle strip making a diamond shape for each tile. Each tile being it''s on primitive object? If so you got the four co-ordinates right there! Then you just make up your polygon test routine for that... or are your tiles possibly more complex than 4 points? Either way a polygon test is how you''ll have to do it..

One thing to note is that you''ll want some sort of primitive test like a rectangle test, then if you it''s close you can do an indepth test like a polygon... you probably don''t have to do this for anything as simple as 4 points (If they are just diamonds) But anything larger makes your polygon test more complex and slower.

See ya,
Ben

Yes, you asked could this 3D point in polygon test be applied to a 2D engine... that''s why I answered that..

Share this post


Link to post
Share on other sites
First, I''ve already read Tanstaafl''s article. Second, it doesn''t help my situation. Third, I''m not sure I understand Jonny''s idea at all. Maybe you could elaborate.

I played some X-COM today and realized that its system of movement is effective but very annoying since you have to keep changing between layers to make sure the paths turn out okay. (The game has a horrible path-finder.) The layers in X-COM are always an arbitrary distance apart, but mine are not.

Let''s look at this another way. Say I dispense with layers altogether and just have a single layer with tiles of different heights. (Again, I suggest looking at MechCommander or Alpha Centauri.) My question is, how do I determine which tile the mouse cursor is over based on this single layer?

Of course, I want to introduce multiple layers into my final engine, but for now I''ll start small until I have a solution. Thanks for the help so far. It''s allowed me to clear up my original inquiry.

Share this post


Link to post
Share on other sites
You could use the same method as suggested in the newest issue of Game Developer Magazine for 3D paint programs.

You render the "clean" version of the scene, with flat lighting and without textures, into the backbuffer, but never display it. You just use it to determine where the mouse is. You store the X and Y coordinates of the tile into the R and G values of the color. So, tile (16, 17) would be color 0x101100 in 24-bit mode. You have to render this view again only when terrain changes or the map is scrolled, so this shouldn''t be a speed issue.

-Jussi

Share this post


Link to post
Share on other sites
OK...
Let''s try again.

In an isometric view tiles are aligned in colums, i.e. tiles that are below each other always share the same x screen coordinates of each vertex respectively. You could also say that the north vertex is always exactly above the south vertex.

This means, if your tiles are, for example 96 pixels wide, you can split the screen into

ceiling(ScreenWidth / 96)

columns. This greatly reduces the tiles to check.

OK - now we have much fewer tiles to check already but we''ll reduce this even more. (if necessary)

Your tiles will probably have some kind of altitude limitation. (if not I don''t know how you did it )
If the limits (in pixels!) are close enough this method will probably optimise your click checking:
Here we only use the y coordinate of the mouse position. There will be a limited number of tiles that can actually be at that y-position. Now, if you only check for those tiles possible in that area you should be able to do this pretty quickly...

Note that I haven''t actually tried this myself but I see no reason why it shouldn''t work.

I hope that this is a better explanation than the last one

- JQ
pmjordan@gmx.at

lead programmer,
PWC Software

Share this post


Link to post
Share on other sites
Jussi, that''s a really great idea. It takes Tanstaafl''s color map idea a step farther. With a 3D card, I don''t think there will be any problem rendering twice as many tiles as normal to a separate surface. Grabbing the pixel color only once per frame should produce negligible overhead.

Thanks for the great idea.

Jonny: I think I understand what you''re saying now. Since both you and I are using D3DIM for our engines, you can understand why I like Jussi''s idea better. Still, thanks for the help.

Share this post


Link to post
Share on other sites
Well, for some time I thought of doing it by rendering in a special colour. But the downside of this (for me) is that you can''t find out where in the tile the user has clicked. Yes, this is a problem for me so I''ll be using my method even though it''s much more complicated. It just fits my needs better



- JQ
pmjordan@gmx.at

lead programmer,
PWC Software

Share this post


Link to post
Share on other sites
Okay, I''m awake now!

The Z-buffer idea I was talking about is similar to TANSTAAFL''s idea of using a colour map, except that you take advantage of hardware Z-buffering support by using Z writes to store the colour in the Z-buffer surface; this is essentially free on almost any newer graphics card, although it can be a little tricky to setup. It doesn''t let you calculate exactly where you are in a tile, although I''d be inclined to figure out which tile I''ve hit - and then figure out the exact location (pretty much the same way I do precise collision detection).

I don''t have any source code for this, yet. The idea only really struck me a few days ago, and I''ve been busy on other projects! However, the theory is relatively simple.

1. When you make your primary/back-buffer surfaces, also create a z-buffer. This is well documented in the SDK. You''ll want enough bits to be able to uniquely identify every tile on screen; 8 may not be enough for fine-grained maps. Fortunately, most cards support 16-bit Z-buffers natively.

2. When you are setting up your rendering states, make sure you switch off Z-buffer checking (isometric rendering relies on the painter''s algorithm, and you''ll get some odd results if you are specifying z values), but enable Z-buffer writes.

3. When you render a tile, be sure to set the z-buffer write value. IIRC, you can do this with one of the renderstates. You can also do this with a flexible vertex format (worth looking into anyway, since they let you have multiple texture positions in each vertex). Set the Z-buffer write value to a number that uniquely identifies your tile (being careful to take into account the bit-depth of the Z-buffer).

At this point, your Z-buffer surface is a nicely organized map of which tiles are taking up which pixels. If you include Z-writes for objects, walls, etc., you can have a *very* accurate mousemap! (IIRC, you can even have transparency supported properly, since transparent areas don''t have to write to the Z-buffer)

It''ll be a while before I can knock together a demo/example for this, but I thought I''d share the idea.

Share this post


Link to post
Share on other sites
quote:
Original post by Tom
Jussi, that''s a really great idea. It takes Tanstaafl''s color map idea a step farther. With a 3D card, I don''t think there will be any problem rendering twice as many tiles as normal to a separate surface. Grabbing the pixel color only once per frame should produce negligible overhead.

Thanks for the great idea.

Jonny: I think I understand what you''re saying now. Since both you and I are using D3DIM for our engines, you can understand why I like Jussi''s idea better. Still, thanks for the help.

Thanks, but as I said, it wasn''t actually my idea, though applying it to this context was. If you can find Game Developer Magazine''s September issue somewhere, it discusses this in more detail.

Remember, that you have to render the color map only when the map changes or scrolls, so you should copy it to a more safe place from the back buffer. If your map isn''t too big, you could even render the whole map at once and render again only when the map changes! Also, when you re-render, you should only render the parts that have change. That should be quite fast.

Just a note to avoid confusion: My name''s Jussi Lepistö, so Jussi is my first name, not an alias. Selkrank is my alias. You can refer me by whichever you like.

-Jussi

Share this post


Link to post
Share on other sites

  • Advertisement