Posted by Fobwashed (1900 posts) -

Point in Polygon you say!?

A point in polygon check is exactly what it sounds like. It's a check to determine whether or not a point lies inside or outside of a given polygon on a 2D plane. These types of checks are fairly common in video games and especially so when dealing with rectangles and circles. A very easy example would be your mouse cursor over any type of interface. Your mouse pointer has a coordinate, and that coordinate is typically being checked against a bunch of polygons (though usually in interfaces they're just rectangles and circles. . . more on that later) to determine whether the cursor should change shape and what should happen when any buttons are depressed.

What up with Rectangles and Circles?

Checking a point against a rectangle or a circle is super easy peasy. For a circle, all you need is the center point of the circle and its radius. You check if the distance between the center point and the point you're checking is greater than the radius of the circle and if it is, not inside. Otherwise. Inside. Done. For a rectangle it's also pretty damn easy in that you just check if the point is within the left and right sides (x) and also within the top and bottom (y) of the rectangle and you're done.

Non-rectangular polygons?

Once you have to start checking against irregular shapes, things get a bit more complicated but not to worry because there's plenty of resources online. The type of check that would work best for your needs depends highly on your specific needs. A small list of the types of things that could determine which methods might work best for you include things such as:

1. Which is more important, speed or accuracy.

2. Whether you're working with floating point numbers or integers.

3. If all your polygons are concave.

4. Whether your polygons have holes in them.

5. The number of polygons you need to check against.

6. The number of points you need to check.

7. Whether or not you will be breaking your complex polygons down into triangles.

Shitty example of some types of polygons. . .

There are plenty more factors which should determine what methods you use in your game/program.

Popular methods include

Stolen straight from Wikipedia

Hmm. . . I was going to write up a bunch of methods, but really. . . it's mostly just math. In most cases involving non-convex, complicated polygons, you'll probably use some form of ray-casting to determine whether your point is inside or not. That's a method where the point in question has a line drawn through it and the number of borders in the polygon is counted to determine whether it is inside (odd) or outside (even) the polygon. There are some issues with this method with the largest being floating point precision issues.

Floating point what now?

This can get super technical and you can find endless reading material on it just by searching Google for "floating point precision".

More than 10x Gertmanns!

The super watered down, I don't give a shit about math version is that programming uses different types of containers for numbers. The higher the accuracy of a number you want, the larger the container needs to be. A bit can be a 1 or a 0. A byte can be between 0 through 255. An int can hold -32,768 ~ 32,768 etc. For the calculations that are required when working with decimals and fractions (which we are for point in poly tests with non-rectangular shapes) you use floats and floats are squirrely bastards. They can hold up to 7 digits with a decimal point within somewhere which gives you a pretty damn good range but when you go over that (as you generally do when working with crazy fractions), the numbers can sorta shift around. So, when you do some math one time, you may get 1.234567 but you do the exact same problem later and you could end up with 1.234568 or 1.234566 or seemingly any damn random number filling that last spot that floats can't go beyond. So even though it's a small as all hell error, that tiny amount could mean the difference between a point being in a polygon and not. Soooo. . . if you need to be uber accurate, it could cause issues.

Why. . . Why all this?

I originally just wanted to post about some progress I made today with my game. I had spent around 2 and a half to 3 months working on the vision portion of my game engine to accurately simulate line of sight in a 2D isometric world and after trying a bunch of things, I found that the best way to do it would be to create polygons for in world objects/walls/floors/etc and then test points to see whether things are seen or not against those polygons. Now, the way I'm doing it is different from other 2D games with line of sight in that I didn't just want horizontal line of sight, but vertical as well because it's isometric with multiple vertical floors. Anyway, basically I went from this

to this

During a vision check, it would take almost half a second to finish because I was running over 3 million point in poly checks against 6,539 polygons. I set up the test to take place in manufactured situation that the player probably wouldn't encounter but they might and I'd rather the game not chug if they do. When I first plugged in the debug methods to check exactly how many times it was running the point in poly check, and more importantly, how many of them were hits rather than misses, I was pretty shocked. Less than 0.01% of the checks were returning as hits meaning that 99.99% of the checks were fails. . . I had already set up the method to cull out any polygons that they were nowhere near but I had to do more. What I ended up doing was increasing the fidelity of the array that was populated by the polygons which increased the number of polygons added to arrays from 11,116 to 92,322 but the trade off was close to 3 million point in poly checks. Also, the time it takes to run the method dropped by around 85%. So barring any memory issues, I think I'm on the right track =)

Oh, and the new hit count is around 21% which isn't bad at all in my opinion. I'm fairly decent at FPS games and my hit rate is rarely that high. I mean, because that's what I should be comparing it to right? -_-;;.

So yea, that's it

My quick status update of "Totally reduced the amount of time it takes to run a function today" into this mess. So I'll pretty much end this blog with a big ol "Fuck floating point precision errors!"

#1 Edited by ThePhantomStranger (353 posts) -

Trying to mess around with 2D game engines gave me just enough rough knowledge to understand about half of that...

Still a neat post.

I remember being so full of myself after making an interface made up of a circle divided into four sections and getting it to recognize the mouse being within the circle or not, radius as you mentioned, and then checking the angle to figure out which of the four sections the mouse was on.

Good luck for when you get to lighting!

#2 Posted by Fobwashed (1900 posts) -

Trying to mess around with 2D game engines gave me just enough rough knowledge to understand about half of that...

Still a neat post.

I remember being so full of myself after making an interface made up of a circle divided into four sections and getting it to recognize the mouse being within the circle or not, radius as you mentioned, and then checking the angle to figure out which of the four sections the mouse was on.

Good luck for when you get to lighting!

Every single step of the way is an achievement. I continually feel the same sense of accomplishment whenever I figure something out now as I did when I first put the text "Hello world" onto the screen =)

I've got what I think to be a good idea for handling lighting. I won't know how good it is till I implement it but I THINK it'll be pretty solid. I'll update about it when I have something to show.

#3 Posted by Chaser324 (6325 posts) -

Lighting and field of view can definitely be a pretty complex thing to implement, but luckily (although in some ways, unfortunately) there's a tremendous number of algorithms out there to pull ideas from. It looks like you're on the right track though, and that's always a pretty tremendous feeling when things start working.

Moderator
#5 Posted by Fobwashed (1900 posts) -

Lighting and field of view can definitely be a pretty complex thing to implement, but luckily (although in some ways, unfortunately) there's a tremendous number of algorithms out there to pull ideas from. It looks like you're on the right track though, and that's always a pretty tremendous feeling when things start working.

Yes they most certainly freaking are -_-;; I actually had a hell of a time finding any resources on specifically doing a field of view for an isometric game at all. In most situations, areas (such as indoors and rooms) just have a visible or fog of war state or vision is set up as a general distance in every direction from the source type thing. The vision method I eventually settled on and am currently using is at least the 4th one I tried to implement =\ I kept thinking to myself that 1st and 3rd person games get a pretty awesome free pass when it comes to what the player can and can't see -_-;;. I'm really curious to see how the Fog of war in that new company of heroes game turns out.