# Computing Field of View on a Hexagonal Grid

This program illustrates the progress of an algorithm I developed to compute Field of View (FOV) within a hexagonal grid. View is computed from the centre of a hexagon, and expands outward in discrete steps (by pressing the "Expand" button). The grid contains some obstacles (darkened hexagons) which block view through them.

At each stage you see the set of "arcs" defining the current view radius. There are initially 4 arcs corresponding to the four quadrants; each arc is shown by drawing its two "arms" (and note that these are only drawn from the centre point out to where the defining point for the arm is, and not always out to the current perimeter of visibility), and (if you're viewing it in colour) shading the area between the arms and the centre in green.

Visible hexes are shown by drawing a number in them (the centre hex is marked "C"). This number looks like "r.i", where r is the radius from the centre (in hexes), and i is the index of that hex in that radius, where hexes are numbered in counter-clockwise order starting from the hex at 3 o'clock, which is numbered both 0 and 6*r. This info isn't meant to be that useful, it's only there because something has to be displayed to show visibility, colour is starting to be over-used, and this info is already calculated and available.

This algorithm is quite fast in practice; it does not need to look at any more than O(n) hexagons, where n is the number of hexagons marked visible. Note though that this Java implementation is meant to be illustrative more than efficient, and does not reflect the true speed of the algorithm.

The complete source code is freely available in info-zip format.

A more complete description of the algorithm is now available; see the description of the FOV algorithm in my text article, or the nice HTML form done by Amit Patel. [Also note that as of June 17, 1997, this is a new version, fixing a bug which caused NT+Netscape combinations to generate multiple windows.]

This code is by Clark Verbrugge. I can be contacted by email at: clump@cs.mcgill.ca

Note that you may freely use or modify this code in any project, commercial or otherwise.