iDevGames Forums
Hex grid line-of-sight - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Design (/forum-5.html)
+--- Thread: Hex grid line-of-sight (/thread-1323.html)



Hex grid line-of-sight - GregX999 - May 8, 2009 04:08 PM

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?


Hex grid line-of-sight - IckyThump - Jul 30, 2009 08:20 AM

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.


Hex grid line-of-sight - JustinFic - Aug 3, 2009 08:20 AM

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.