Hi all, I've started a bit of work on a new Hexagonal Tile engine (eventually to be ISO, but is currently just overhead) and am having difficulty coming up with an algorithm that doesn't feel 'hacky' for the following problem: I want the user to be able to select a group of tiles by drawing a rectangle on the screen; Everything that intersects the rectangle will be selected. So I have a rectangle in pixel coordinates with the origin and a width and height. I know what tile (hex coordinates) is at the origin, but what's the best way to decide wether or not I have to draw the row above and to the right of the origin tile? Similarly for the last row. For example:

 0/ \1/ \2/ \3/ \4/ \5/ \   
0|   |   |   |   |   |   |  
  \ / \ / \ / \ / \ / \ / \ 
  1|   |   |   |   |   |   | 
    \ / \ / \ / \ / \ / \ / \  
    2|   |   |   |   |   |   |  
      \ / \ / \ / \ / \ / \ / \ 
      3|   |   |   |   |   |   |
        \ / \ / \ / \ / \ / \ / 

a rectangle with the origin in (1,1) could intersect (2,0). And the maxX,maxY of the rect could end in (4,2) but may or may not include tiles in row 3. What I'm doing now is: -find the origin in hex coordinates -find the number of rows to draw by dividing rect.height by tilesize.height*.75 (round up) -find the numbers of cols to draw by dividing rect.width by tilesize.width (round up, increase by one every other row) -check to see if the tile at origin.x++, origin.y-- intersects the rectangle and start drawing at that tile instead if so -select one more row, just in case. granted the last "just in case" is fine for drawing, but not for selecting. Any tips, pointers to get me in the right direction? I feel like I'm missing something obvious. Edited by - IPC on June 2, 2001 8:00:04 PM

do you want to select only those hexagons that are wholly within the bounding rectangle, or do you want all hexagons that overlap the bounding rectangle to be selected?

I want to select partially selected hexes as well; that is to say all hexagons that overlap the bounding rectangle.


Edited by - IPC on June 3, 2001 3:22:03 PM

Umm. This is a guess, but wouldn''t your criteria be if point (at origin) is within the upper triangle part of the hex then include hexes from the row above?

Likewise, if the destination point (maxX, maxY) has a Y-value that puts it into the lower triangle portion then include everything in the lower row?

I suppose the details depend on the dimensions of your hexes, but most of them use a 1:2:1 ratio for a single hex (i.e. for hex 64 pixels high, the first 16 are in teh upper triangle, the middle 32 are the widest part, and the lower 16 are the other triangle).

This would make it a simple check to see if MaxY > (RowY -1) + (HexHeight >> 1).

Okay, i''ve given some thought to this. This can be done mostly with the bounding rectangle for a hex tile.

the first thing you need to do is determine in what tile the upper left corner of the rectangle is in.

next, you need to determine where within that hex the upper left of the rectangle is. there are three zones that determine what else you have to do.

the first zone(zone a) is the upper third. this is where the top "pointy bit" of the hexagon is. The second and third zones are the left bottom two thirds(zone b), and the right bottom two thirds(zone c).

for zone a, move northeast by one tile. for zone b, do not move.

the tile you are on is the "upper left" tile. determine the left position of this hex''s bounding rectangle. only the left position is important. mark this tile as "selected", and keep this tile''s position in some temporary variable.

move right one tile, and redetermine the left of the bounding rect for the tile. if this value is less than the right of the selection rectangle, mark this tile as selected, and repeat until left is not less than the right of the selection rect.

now, restore the value of the upper left tile (i.e go back to the beginning of the row). depending on what the original zone was, you will move diagonally downwards (southwest and southeast alternately). for zone a, you will start moving to the southwest. for zones b and c, you will start moving to the southeast.

each time you move down, determine the top coordinate of the bounding rect of the hex tile. if this value is greater than or equal to the bottom of the bounding rect, stop. you are done. otherwise, check another row for selection as you did above.

after each row, change direction from southeast to southwest or from southwest to southeast. in this way, you zig-zag down the edges.

the bounding rectangle for the hex tile should be the bounding rect for the tile only.

Thanks Ernest,

I haven''t had a chance to try this out yet, but I will report back here when I have an let the group know my findings.

Thanks,
Ian

quote:

---

Original post by TANSTAAFL

Okay, i''ve given some thought to this. This can be done mostly with the bounding rectangle for a hex tile.

---

Thanks Ernest... this worked out well. They key observation that I missed doing a hit-test per hex and ending the loop when you missed. I was trying to determine the number of hexes from the dimensions of the rectangle but that proves problematic as you hit edge cases.

For now I''m using the bounding rectangle and the selection rectangle for hit testing but if I may go back and do an actual hex/rect hit test before I''m done because I feel it will provide a better user experience. It''s kind of strange to see a hex light up when the selection rectangle hasn''t touched it yet.

Thanks again

Oops, double post

Edited by - IPC on June 11, 2001 11:41:06 AM