I am very new at this, so I apologize for my ignorance. I am learning C++ and thought a good way would be to try to build a game I used to like to play--Battletech. I''m trying to figure out a few algorithms that maybe someone could help me with. For now, the game is just going to be a basic text based game built in DOS, because I am just working on the programming logic more than anything else. The part I am working on is trying to figure out the hex''s that a straight line would pass through between 2 6-sided hex''s. For instances, if I have a hex-grid map with the first column numbered 1,1; 1,2; 1,3; etc. and the first row across numbered 1,1; 2,1; 3,1 etc. I want to be able to draw a straight line from the center of (8,9) to the center of (1,2) and figure out that the line touches the following hexes: (1,2), (2,2), (2,3), (3,4), (4,4), (4,5), (5,6), (5,7), (6,7), (7,8), (7,9), (8,9). Once I know each hex that the line passes through, then I can determine what characteristics each cell has and calculate Line Of Sight, modified to-hit numbers, etc. Anyone have experience, ideas, thoughts, etc on how to figure this out? Anyone have interest in a project similar to this? I''d love to discuss ideas for the game further. Thanks for any help, thoughts and ideas. ___ ___ ___ ___ /1,1\___/3,1\___/5,1\___/7,1\ \___/2,1\___/4,1\___/6,1\___/ /1,2\___/3,2\___/5,2\___/7,2\ \___/2,2\___/4,2\___/6,2\___/ /1,3\___/3,3\___/5,3\___/7,3\ \___/2,3\___/4,3\___/6,3\___/ \___/ \___/ \___/ etc. etc. etc. etc.

There may be a simple mathematical way to solve this, but i don''t know it
The way i used to do this was to break the hexes up into a regular rectangular grid and then do line/rectangle and line/triangle checks
ie:
each hexagon is broken into two parts - the top and bottom.
this forms two trapezoids.
..__
./__\
if the triangles on either side are chopped off, a rectangle is left, which is easy to check for.
_____________
|/|__|\|__|/|
|\|__|/|__|\|
etc (note there should be 3 unbroken horizontal lines drawn above)

ie - if it''s in column one, then hexes are formed from pairs of rectangles : 1+2, 2+3 etc
but if it''s in column 2, it''s offset by 1 rectangle: 2+3, 4+5
all thats left to check for is when the line crosses the triangle bits
|/|

|\|
that needs a line/triangle intersection.

Wyzfen.

ps, i''m not being very eloquent today, sorry.

Wyzfen,

Thanks for your comment. I''ve heard something else similar to the method you''re describing (i.e. breaking the hex into smaller shapes and testing those).

But, how do I actually go about doing the test.

What I will have is a player saying fire a weapon from my current position (8,9) at target (1,2).

Now, as the programmer, I need to determine which hexes are in the "line of sight".

I understand the basic concept of breaking the hex into squares and checking the squares, but I still don''t understand how to do the check. That is, how do I know which squares to check whether the "theoretical" line crossed or not?

Thanks again!!!

one method could be:
you''ve (in your mind) broken your screen up into a stack of columns - triangles in the first, rects in the second etc.

1 work out the first and last columns
- you know which cells you want, so you know the ''columns''
2 for each rectangle containing column, work out the max/min y values.
- using the line formula y=m * x + c and knowing the
x values for the left and right edges of the column, you
can work out the two y values.
3 using that max min, EVERY hex in that column between the max and min values is in your visible set (inclusively - if the max/min is INSIDE a rectangle, include it too).

4 all thats left is to work out when the ''line'' intersects the triangles. you could do this by treating pairs of triangles as rectangles as working out if the ''line'' intersects a side+top/bottom, top+bottom or side+side.
ie, for
|/|
the options are: ((L)eft,(R)ight,(T)op,(B)ottom)
left triangle only: L-T
right only : R-B
both: T-T, L-R, L-B, R-T

this is getting messy. i''ll see if i can work out a better solution

Wyzfen

There''s another less computationally intensive way to approach hex line of sight.

First off it''s a lot easier to look at the algorithm if you use a slightly different coordinate system. The problem with the way you have things now is that given (x,y), (x+1,y) might be to the northeast or the southeast. While now a big deal, it makes things more complicated.

One alternative is, given hex (x,y), (x+1,y) is always the northeast neighbor hex, and (x,y+1) is always the south neighbor hex. It follows that (x,y-1) is the north neighbor, (x-1,y-1) is the northwest neighbor, (x-1,y) is the southwest neighbor and (x+1,y+1) is the southeast neighbor.

So given the coordinates of two hexes, we can right away determines if they fall into any of the trivial special cases. So we have (x1, y1) and (x2, y2). Let (dx, dy) = (x2 - x1, y2 - y1). If dx is zero, the hexes fall on a north-south line. If dy is zero, the hexes fall on a northeast-southwest line. If dx equals dy, the hexes fall on a northwest-southeast line.

The other set of special cases is when LOS goes directly across hex boundaries. Mathematically this can only happen in the following cases: dx == -dy, dx == 2 * dy and 2 * dx == dy. For example if (dx, dy) is (2,-2) then LOS goes along the boundary between (0,-1) and (1,0), through (1,-1), along the boundary between (1,-2) and (2,-1), and into (2,-2). In the Battletech rules you''d then have to do something special because the LOS passed on those boundary hexes.

Now for the painful part. If you take out all the hexes in the first special case, you''ll have left six segments, or hextants. So you''ve got northeast, east, southeast, southwest, west and northwest hextants. The northeast hextant contains all hexes where dx > 0 > dy. The east hextant contains all hexes where dx > dy > 0. The southeast hextant contains all hexes where dy > dx > 0. The southwest hextant contains all hexes where dy > 0 > dx. The west hextant contains all hexes where 0 > dy > dx. The northwest hextant contains all hexes where 0 > dx > dy.

There''s a point behind dividing the board into hextants. Consider moving from (0,0) to (3,2) one hex at a time. (3,2) is in the east hextant of (0,0), so if you always want to move closer to (3,2) you can only move into a northeast hex or a southeast hex. To reach *any* hex in the east hextant in the least amount of moves you can only move into northeast hex or southeast hexes. In the southeast hextant you can only move south or southeast, in the southwest hextant you can only move south or southwest, in the west hextant you can only move northwest or southwest, in the northwest hextant you can only move north or northwest and in the northeast hextant you can only move north or northeast.

Now we''re given a source and destination hex for our LOS calculation. Given the hextant it''s in we know how many times in what directions we can move. e.g. moving from (0,0) to (3,2) we move southeast twice and northeast once, or moving from (0,0) to (1,-2) we need to move north twice and northeast once. Obviously if you need to move fifty times north and forty times northeast, that won''t follow the line of sight very exactly if you just move fifty times north and forty times northeast; you''d have to move north twice, then northeast, then north, then northeast, then north, etc., etc., etc. So given the basis steps and the distances involved you can use a variation of bresenham or some other such algorithm to figure out what order to do the traversal in.

So compared to doing actual line-hex intersection tests:
1) it''s faster. Pre-processing consists mostly of figuring out if it''s a special case and if not what hextant to consider. From there a hex is only considered if it''s along the LOS path. Also you''re working in map coordinates the whole time, so you don''t need to create a whole net set of coordinates for each hex just to do LOS calculations.
2) It''s more sane. With strict line-hex intersection tests, a target 20 hexes away could have a LOS path containing 25 hexes, most of those extra hexes are cases where the line just clipped the corner of the hex. With this method you''ll always go through exactly 20 hexes for a target 20 hexes away.

SiCrane,

Thanks for the advice; the thought process is good and helpful.

Unfortunately, I don''t think it works for hexes because if you are moving along a Northwestern straight line (i.e. at the upper-left 60 degree line) starting from hex (5,5), your path would be as follows:

(5,5) - (4,4) - (3,4) - (2,3) - (1,3) . . . now you''ve reached the left edge of the board. There is not a consistent x-1 pattern. The pattern in this case is (x-1, y-1), (x-1, y), (x-1, y-1), (x-1, y).

___ ___ ___ ___ ___
/1,1\___/3,1\___/5,1\___/7,1\___/9,1\
\___/2,1\___/4,1\___/6,1\___/8,1\___/
/1,2\___/3,2\___/5,2\___/7,2\___/9,2\
\___/2,2\___/4,2\___/6,2\___/8,2\___/
/1,3\___/3,3\___/5,3\___/7,3\___/9,3\
\___/2,3\___/4,3\___/6,3\___/8,3\___/
/1,4\___/3,4\___/5,4\___/7,4\___/9,4\
\___/2,4\___/4,4\___/6,4\___/8,4\___/
/1,5\___/3,5\___/5,5\___/7,5\___/9,5\
\___/ \___/ \___/ \___/ \___/

This is a good website for info on programming games which uses hex, tiles, and AI in general.

http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html

Good Luck

-ddn