Hex grid line-of-sight

Posts: 14
Joined: 2009.04
Post: #1
Ok, I've gotten pretty far in my hex-based game programming. I currently working on line-of-sight (or field-of-view).

My goal was to calculate LOS between 2 hexes by checking a line drawn from the center of hex 1 to the center of hex 2. If the line crosses any pixel of a hex that blocks LOS, the LOS would be blocked.

Here's a screenshot:
[Image: hex_los_example.jpg]

I drew in the red lines by hand to illustrate the issue below. The hexes with the red dots are within 10 hexes of the ork - his max sight range.

I've got my code working - as far as it's doing exactly what I intended it to. Here's a image from current test code. The dark hexes are not in LOS of the ork. As you can see, there are some "floating" hexes that are within LOS - according to center-center line method.

So, there seems to be a flaw with that method. I'm unsure what to do.

I was thinking about making a 2nd check, if center-center line method results in blocked LOS, I was going to then check 6 more lines, from the center of the viewer's hex to the 6 vertices of the "target" hex, and if 3 (or 2, or 4) of the vertices are within LOS, I'll say the hex is in LOS. That would open up more hexes to being in LOS.

Or... I could just make islands like that be NOT in LOS, the ruling being that a valid LOS can not pass through any hexes that block LOS, OR any hexes that are blocked themselves.

Any other ideas?

Is there a commonly used solution for such a problem?
Quote this message in a reply
Posts: 11
Joined: 2009.07
Post: #2
This question has been here unanswered for some time. Are you wondering why there are any floating hexes? The definition of your LOS-algorithm has flaws due to your idea of LOS and the realization - I think.

Could you state the problem more clearly? So far, I dont think a second check is necessary.
Quote this message in a reply
Posts: 338
Joined: 2004.07
Post: #3
Q is a couple months old but in case the OP is still looking for help:

I would introduce a sort of "fudge" factor to your visibility check. So as I understand it, if the line connecting the centers of your source hex and your target hex touch any pixel in a hex containing an obstacle, the target hex is not visible.

Instead of checking against every pixel in the target hex, I would check against a circle of variable radius centered on the center point of the obstacle hex. Once I got that working, I would tinker with that radius until I got results that looked and played pretty good. Just from eyeballing your picture I would say that radius is somewhere between 1/2 and 3/4 of the outer radius of your hex.

Using circles should also make computing LOS a little quicker/easier. You can also do things like have different obstacles use different radii (trees may block less than rocks, for instance.)

Hope that helps.

Justin Ficarrotta
"It is better to be The Man than to work for The Man." - Alexander Seropian
Quote this message in a reply
Post Reply