Polygons intersecting rectangles

[Drummer_si]

 

I'm working on a board game in Phaser...

I'm working out line of sight for each player.. and have generated a polygon of the area the player can see (shown in red)

 

However, as this is a board game, I want to restrict the view to full tiles, so I need to calculate exactly how much of each tile the player can see...

I know I can intersect 2 rectangles, and find the area that both occupy... But it seems that intersecting Polygons is not possible in Phaser... Does anyone have any ideas about how I may intersect a rectangle with a polygon to return the area that both object occupy.

 

In my example below, Square A would occupy about 50%, while square B would occupy 100%.. Both you be shown... Anything smaller than 50% viewable area would still be hidden however.

[mattstyles]

These two pages [1] [2] will probably be of interest to you, they link to various articles describing FOV and LOS in square tile based systems.

I'm not sure of a generic inclusion algorithm for the intersection of polygons, its probably not too much work to create one (or find a module somewhere) but its probably not the cheapest set of operations, I'd imagine you'd have to check each line of each shape, or something to do with vertices against lines, in any case its going to be a fair amount of operations. You'd then have to do that for every tile in your search range (potentially your entire grid) which is incredibly wasteful and duplicates the expense, not to mention that your original algorithm for drawing the LOS polygon (the one you've shown in red) is probably quite expensive already.

(edit: actually I can think of one, you check a point and draw an arbitrary line and check it for intersections between every line representing your polygon shape, if there are an odd number of intersections then you're inside the polygon, even number you're outside. I think this is pretty accurate, possibly 100%, not sure).

I've recently achieved this using a brute-force LOS method of ray casting from the center position of my original tile and it's just about fast enough on most hardware (under the hood I'm using JS generators and I can tweak a number of variables if its running to slow to give less precision, on the fly). It's draws lines by increasing the position of a point along a line and marks a tile corresponding to that point (using cheap integer flooring to cross-reference against my tile grid) as visible, halting the line drawing on meeting a solid tile. I've got this drawing against a pretty big radius of tiles and I can get it within a frame (1000/60ms) fairly comfortably on most modern hardware (even mobiles, old ones struggle but I've got the precision cranked up fairly high). This probably wouldn't work for you though as you want a more selective inclusion method.

Have you considered working backwards on this:

For each tile in your grid, take each vertice (so, 4) and draw a LOS to your origin tile center (or to each of its 4 vertices, but that ups the expense). If 3 vertices are visible the tile is visible, not sure if this would be accurate enough but even though the algorithm would be very wasteful it would still be cheapish and you could easily clamp the search space by radius or some other criteria. Still relies on ray casting though. (edit: this would actually be a cheaper way of working out your polygon, looks like you're doing ray casting currently but checking from vertices representing walls in your tile grid would be cheaper, problem is most tile maps representations don't have a view of them representing walls, you can do it for each corner of a tile but its more expensive again, although cheaper than ray casting out from an origin point).

[Drummer_si]

Hey mattstyled.. Thanks for the in-depth reply

I've been a web developer for 10 years, but new to game development and the maths involved.

 

After reading your reply and following the links you posted.. I think I may try giving each tile a small "collision rectangle" in the center.. If at least one ray passes through this rectangle I can be fairly sure that the players can see it.

[mattstyles]

That sounds like a good plan, let me know how you go with it and what the output looks like. I use the entire tile, I hadn't considered just shrinking that intersection zone a little, but sounds like it could give good output (in my case though I actually want slightly unrealistic views, my view is pretty zoomed out and so things generally look better a little more permissive than strict).