geek
The Hotness
Games|People|Company
Rules | Subscriptions | Bookmarks | Search | Account | Moderators
Recommend
7
7 Posts
New Thread | Printer Friendly | Subscribe  sub options | Bookmark
Your Tags: Add tags
Popular Tags: interesting [+] [View All]
Mircea Pauca
Romania

flag msg tools
mbmbmb
BoardGameGeek » Forums » Gaming Related » Wargaming
Hex-grid LOS math *general solution*
Hello all - I'm sure I'm reinventing the wheel here, but I'm not sure the solution I've found public so far
http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.h... is always correct. That one depends on a modified Bresenham line-drawing algorithm, and the Line of Sight may cross a hex even if it's not enough to warrant getting an ON pixel after the rounding (the idea of the algorithm for square grids).

Superpose a rectangular x,y grid onto the hex grid, such as one direction of hex-centers coincides with the x axis. So, the centers of hexes along it have x,y coordinates (0,0) - the observer/firer, (1,0), (2,0) ...



My hex-grid coordinates are what wargamers use 'by eye', and are different from the two systems proposed in that article:
D -> distance in hexes
L -> 'laterality' i.e. how many hex rows away from the x axis
A hex of hex-coordinates (D,L) moves from the origin: D-L hexes along the axis, and L hexes to 60 degrees (suppose 'up')

The rectangular coordinates of hex-coords (1,1) are (1/2, sqrt(3)/2)

So, the rectangular coordinates of the center of a hex (say the Target) are:

Xt = Dt - Lt/2
Yt = Lt * sqrt(3)/2

The coordinates of the lowest corner of the Obstacle hex are:

Xo = Do - Lo/2
Yo = Lo * sqrt(3)/2 - sqrt(3)/3

(Note: the lowest corner, and not e.g. the right-lower corner is the critical one if-and-only-if Dt >= 2* Lt. Else, look at it from another angle - rotate the X axis 60 degrees and mirror the image)

There is LOS to the target if the slope of the Firer-Obstacle line is not lower than the slope of the Firer-Target line:

So = Yo / Xo = (Lo * sqrt(3)/2 - sqrt(3)/3) / (Do - Lo/2)
St = Yt / Xt = (Lt * sqrt(3)/2) / (Dt - Lt/2)

So >= St
simplify by sqrt(3)/6

(3*Lo - 2) / (Do - Lo/2) >= 3*Lt / (Dt - Lt/2)

so there results the Minimum distance to the target to have LOS, given the other 3 variables (distance to obstacle, laterality of target and obstacle):

Dt min = Lt/2 + (Do - Lo/2) * 3*Lt / (3*Lo - 2)

not easy to apply, but cannot be further simplified meaningfully.

A particular case is when both target and obstacle are 1 hex lateral from the axis: Lt=1, Lo=1. Then the "3* X-distance" rule applies:

Dt min = 0.5 + (Do - 0.5) * 3

Example in image: if the obstacle is 2 hexes away, 1 lateral (Do=2, Lo=1), the nearest hex that is 1 lateral that is (barely) visible is (5,1):

Dt min = 0.5 + (2 - 0.5) * 3 = 0.5 + 4.5 = 5


Tim Benjamin
United States
Los Alamos
New Mexico
flag msg tools
Avatar
040506070809
mbmbmbmbmb
I think an old Moves magazine had an article on this topic with the words 'Orthofront Geometry' in the title.
Skip Franklin
United States
Oklahoma City
Oklahoma
flag msg tools
Avatar
patron05
mbmbmbmbmb
SPI's Battle for Cassino - Assaulting the Gustav Line, 1944 had this rule and chart in the rules for determining Line of Sight (LOS).





Click the pictures and select a larger version.
Phil
Germany
Bremen
Bremen
flag msg tools
mbmbmb
I would still use the "Russian"* version: holding the ends of a thread onto each hex and simply look what it hits.

It is faster and easier. ;)




*) Just to be sure:
No insult meant. Just remembered the NASA investing a lot of money to invent a pen that writes in space while the Russians simply used a pencil...
Mircea Pauca
Romania

flag msg tools
mbmbmb
Thanks Skip for the Cassino rule. Of course that formula is correct for the vertical direction - still the rules are not clear - are firers or targets in the center of the hex, or anywhere ? does the altitude of 'extra terrain' raise like a prism over all the hex ?

Then, that formula needs to know what hexes are passed over and what not - and here my formula works (or the thread - but I've seen a few cases where even with a thread it's close to ambiguous - way too sensitive to where the center of the hex is exactly - if not marked with a dot).
Ireland

flag msg tools
designer
Avatar
patron08
ROMagister wrote:
(...)I've seen a few cases where even with a thread it's close to ambiguous - way too sensitive to where the center of the hex is exactly - if not marked with a dot.


Yours is a cumbersome exercise in mathematics, far from an efficiently applicable solution. Ambiguity with the thread? Not unless you want to see the things your way and are prepared to split atoms over it.
Last edited on 2009-05-06 04:06:28 CST (Total Number of Edits: 2)
David Hailey
United States
Georgetown
Texas
flag msg tools
patron09
mbmb
I wrote an article for Advanced Squad Leader that may provide some insight. It is buried on the website http://texas-asl.com/. in the May 2000 issue of Banzai!! 5.2.
Front Page | Welcome | Contact | Privacy Policy | Advertise | Support BGG | Feeds RSS
BoardGameGeek and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.