Hex grid line-of-sight

Apprentice
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
Apprentice
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
Member
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
http://www.justinfic.com
"It is better to be The Man than to work for The Man." - Alexander Seropian
Quote this message in a reply
Post Reply