3
\$\begingroup\$

I have a game engine which handles hexagon based war games and things like LOS, etc, for both flat and tip up hexes. A particular game I'm implementing at the moment, Band of Brothers, has facing for vehicles and, optionally, for infantry.

I've searched the web and have not found any algorithm to handle determining the hexagons that fall within an arc expanding out from a hexagon. Here are some pictures to describe what I'm talking about:

Firing arc for vehicles Hexes for infantry

I represent the hexagon locations as offset coordinates, and have the values for all the dimensions of each hexagon and the endpoints of the vertices and center in relation to the overall map stored as doubles. I also convert to cube coordinates for determining distance.

Just looking for ideas or pointers on how I might determine these hexagons.

EDIT: I do not have a rep > 10 so I can't add a picture of offset coordinates. There is a good one here on gamedev though. Here's an ASCII art representation of it. The numbers will be a little different depending on which row is indented:

0,0   1,0   2,0   3,0   4,0
   0,1   1.1   2.1   3.1
0,2   1,2   2,2   3,2   4,2
Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Part of the problem with your searching may be that that shape is a hexagon not a hex. When you said hex I initially thought you ment the hexadecimal number system (that is sometimes called hex) \$\endgroup\$
    – Richard Tingle
    Apr 19, 2017 at 19:02
  • \$\begingroup\$ This depends on how you index your hexes, and what kind of arcs you want to support. \$\endgroup\$
    – Peter
    Apr 19, 2017 at 20:36
  • \$\begingroup\$ If the maximum distance from the center of the arc is a small number of hexes, you could try out a "dumb" implementation. Checking all of the hexes within a short range (say, 5 tiles away or less) should be quick. I'm assuming here that you don't need to do this 1000s of times per frame...though that still may be fast enough. \$\endgroup\$
    – Victor T.
    Apr 19, 2017 at 23:46
  • \$\begingroup\$ Thanks for responding everyone. I index them in an array but the are stored with offset coordinates. Going by the first picture, I need to arc out 120 degrees and 60 degrees. The 2nd picture, seems like a 180 degree arc jetting out from the upper 2 vertices. And yes, I could just do that kind of approach. I would be done once and be cached it so there would just be that one time penalty. I do the same with LOS, I tuck away LOS from every hex to every other hex and tuck away the hexes between the 2 points to check for dynamic entities (like moving troops, smoke, etc). \$\endgroup\$
    – Brian Sturk
    Apr 20, 2017 at 14:02
  • \$\begingroup\$ Not sure if this will help but its worth looking into: redblobgames.com/grids/hexagons \$\endgroup\$
    – user16195
    Apr 20, 2017 at 22:29

1 Answer 1

Reset to default
1
\$\begingroup\$

If your range is limited, you can enumerate all the hexagons in each category, assuming the unit is facing north and is located at 0,0. Then use hex rotation (in cube coordinates) to match the direction. And use hex addition to move the coordinates to the unit's location.

By explicitly enumerating the hexes, you can have arbitrary shapes, such as being able to fire on side positions only when 2 ≤ distance ≤ 4, or having the range depend on the angle. I put a demo here.

If you have unlimited range, I think atan2 is probably the simplest thing. Use hex subtraction (in cube/axial coordinates) and then convert that to x,y and use atan2.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Your site has been invaluable for the current state of my game engine (thank you!), but this game's hex rules has thrown me for a loop. Thanks for putting up a demonstration! I assume the green hexes are the "matching" ones based on the rotation? Also, it looks like the demo is showing the 180 degree arc, how does the arc of inclusion come into the equation? <br/> My range is limited, so it's OK for me to walk all of the hexes, and I will cache all the results. However, I'm not understanding the algorithm(s) needed to determine which hexes are in those fields of view. \$\endgroup\$
    – Brian Sturk
    Sep 17, 2017 at 15:04
  • \$\begingroup\$ Ah! I missed that part of the question. The demo only shows how to rotate the cached results (any shape, not only arcs), but not how to calculate it in the first place. I think the easiest way is to use regular trigonometry. Assume the unit is at 0,0 and facing east. Iterate through all the hexes around it and calculate their pixel location. Use atan2(pixely,pixelx) to get the angle (radians). Convert to degrees. If it's in the range -30 ≤ angle ≤ +30 then it's in your 60 degree arc; if it's in -60 ≤ angle ≤ +60 it's in your 120 degree arc. \$\endgroup\$
    – amitp
    Sep 17, 2017 at 17:01
  • \$\begingroup\$ The 2nd picture, the 180 degree arc, is probably easier to calculate by testing for x > 0 when facing east. Once you've calculated everything facing east, you can rotate it to match the unit's actual direction. \$\endgroup\$
    – amitp
    Sep 17, 2017 at 17:02
  • \$\begingroup\$ Thanks again. I had been trying to determine the hexes in the arc by just using their coordinates since the angles followed the hex sides. I thought maybe there was some algorithm to figure it out that way, without much luck. I have the pixel info as far as center and vertices, so I could use that as well. \$\endgroup\$
    – Brian Sturk
    Sep 18, 2017 at 21:24
  • \$\begingroup\$ If it's always hex sides it you might be able to look at which of the three coordinates is largest (after taking absolute value). See the colors on this page. But I think that trick doesn't work for your second diagram. :( \$\endgroup\$
    – amitp
    Sep 20, 2017 at 4:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .