I have a square, fixed-grid terrain with one terrain type per grid unit in my game, and I want to do an arbitrary polygonal terrain query which returns all of the grid units enclosed/intersected by the polygon. Can anyone point me towards an algorithm for this?
I'll be using this to make sure that my actors aren't going through invalid terrain when they move.
Thanks!
Prepare your polygon
Set up your polygon as a directed sequence of points / lines. This is described in any point-in-polygon test, for which there are countless resources online and on Stackoverflow / Stackexchange, so I won't repeat here.
Prepare your map for querying
Assign every grid square a unique ID.
Construct a list of all unique vertices (corners) which define your grid squares. For a map N x M squares, there will be (N+1) x (M+1) corners.
Give each corner a list of which squares reference it. (between 1 and 4 -- most will be 4 since generally a corner sits at the intersection of four squares).
Query and resolve
Now against every corner point, run point-in-polygon test. For corner points that fall inside, add them to a new "inside" list.
The final step is to determine which squares your inside points belonged to; this is why we kept lists of squares for each corner, earlier. There are two ways you can interpret "insideness" for squares:
If the former, it's very easy, just run through all inside points and add squares referenced by them, to a set (i.e. a list that does not allow duplicates). This set is your final result.
Else, you can do reference counting. Set up a map of integer values (zeroes) keyed by square IDs, for every square of your terrain. Now run through the list of inside points, and for every single referenced square in every one of those inside points, add one to the relevant keyed map entry. Once this is done, run through the map and add any entries that have a 4 in the value field, to a new list. This is your final result., since those squares' 4 corners fall completely inside the polygon.
Optimisation - OPTIONAL
You can simplify the process somewhat by assigning each square a centre point, and checking which of these fall inside the polygon. This is conceptually simpler, but not as accurate as 4-corner checking. If you don't mind a rougher approach, I'd recommend this.
Final tip
Quantising polygons and polyhedra into cells can often be a tedious process. In cases like this, I sometimes recommend that if you don't want to go through the rigmarole above, you instead just construct your game dynamics such that your polygon is in fact already just a shape made out of cells / blocks, rather than a nice neat polygon. This makes it very easy to check against the grid map.
