ID:1397597
 
I'm working on an RPG-style game and one thing that has me stumped is how best to implement collision with objects that are not rectangular, e.g. triangles. I'm looking for something relatively simple.

What sort of approach would you take to solving this in a way that integrates cleanly into Byond? One straightforward approach is to, at run time, create many small 'collision' boxes. This seems like the easiest method, but creates a lot of extra objects. Are there better design philosophies for collision that you've used or worked with before?
I've been wondering about this as well and hoped to see it implemented once but I think this is not the right way. It's strange that nobody replied you. *confused*

All I could think of was circle collisions where you'd just assign radius and count everything run-time.
All shapes can be defined as a series of triangles.

Therefore, solving for a triangle:

http://community.topcoder.com/ tc?module=Static&d1=tutorials&d2=geometry3#pointinpolygon

To do this fast in DM, though, you would want to first test if an object is in the AABB bounding box of the triangle. You would find the aabb bounding box of a triangle:

var/bottom_left_x = min(point_a_x,point_b_x,point_c_x)
var/bottom_left_y = min(point_a_y,point_b_y,point_c_y)
var/top_right_x = max(point_a_x,point_b_x,point_c_x)
var/top_right_y = max(point_a_y,point_b_y,point_c_y)


Once you have the square bounding box, you can hijack BYOND's built-in collision testing to ensure another object's AABB bounding area intersects with this one. Then you apply the geometric formulas from the tutorial I linked to ensure that overlap is indeed happening manually.

This will save you quite a lot of speed, first testing the bounds with the built-in function before even attempting to test for collision of triangles.

I should also note that circles are incredibly easy. You just need to test that the center of the circle is within range of r+(squrt(a^2+b^2)/2) of the square bounding box, then you can test each individual point of any polygon within the bounding box to confirm that they are indeed in range.
I've spent more time with this, and I've come up with something far less computationally intense.

Within my game, I'm guaranteed to be using polygons with either 3 or 4 edges. The first edge is always going to be perfectly horizontal, running the entire width of the polygon.

The second line is always going to be of the form Y = aX + b. The third and forth lines will always be purely vertical, going straight up from the endpoints of the first line until they intersect the sloped line.

Therefore, in order to check whether a point is within the polygon, all I need to do is satisfy the following conditions:

Point.X in (BaseLine.Left to BaseLine.Right)
-and-
Point.Y >= Base.Y && Point.Y <= Slope.Y @ X -or- Point.Y <= Base.Y && Point.Y >= Slope.Y @ X
You should take a look at Hobnob's Pointing the Way to Vectors article.

Don't trap yourself in the small bubble of information you'd get from the BYOND community, though. There are many different ways to handle collision and physics in games, and BYOND is the last place you should be looking for this information.