p is player position
c is corner position
root_TL_corner is (0,0)
root_BR_corner is (550, 400)
_root.getEndPoint = function (p, c) {
//direction vector
v = new Point2D(c.x-p.x,c.y-p.y);
//normalize
vXY = Math.abs(v.x) + Math.abs(v.y);
v.x /= vXY;
v.y /= vXY;
//now this is kind of unnecessary, but I don''t know how
//else to do it. i''m extending the ray past the bounds
//of the main movie
if (Math.abs(v.x) > Math.abs(v.y))
{
if (v.x > 0)
{
ratio = v.y / v.x;
v.x = highExtendX;
v.y = ratio * v.x;
}
else
{
ratio = v.y / v.x;
v.x = lowExtendX;
v.y = ratio * v.x;
}
}
else
{
if (v.y > 0)
{
ratio = v.x / v.y;
v.y = highExtendY;
v.x = ratio * v.y;
}
else
{
ratio = v.x / v.y;
v.y = lowExtendY;
v.x = ratio * v.y;
}
}
//get the vector into the reference frame of main movie
v.x += p.x;
v.y += p.y;
//this next line is sloppy. i should through math know
//exactly which line to test interception against.
v = _root.intersectLineRectangle(p, v, root_BR_corner, root_TL_corner);
return v;
}
2D Shadow Casting Optimization - Help!!
Author
Hey guys. I''m writing a little line of sight thing for Flash MX that you can see here:
http://www.goodliquid.com/signature/Los.html
So here''s my problem. This is supposed to be running at 18FPS, but without a powerful computer, there is no way this will hit this frame rate. Now, I know Flash MX is really slow, but that just gives me a chance to learn how to write some tight ass code. So here''s what I need help with.
Right now I''m extending two rays from every wall and clipping it at the bounds of the movie. To do this, I am testing the ray against the entire rectangle of the main movie, which I know is not necessary. I want to only test against one... how? Here''s the relevant code from the clipRay function.
So thats question #1. Here is #2:
I go through this entire process for every obstacle on screen, and I''m thinking that it might not be completely necessary. Here is the process.
1. get player->corner magnitudes
2. use dot product to find theta for each vector combination (finds which rays extend)
3. extend applicable rays
4. find corners and add to draw list
5. draw
6. repeat for each obstacle
Could I remove anything from this?
I''m thinking that maybe I could remove some calculations for obstacles that are already covered by other shadows, but would it be faster overall?
I like your demo, and for the 3 walls it runs somewhat smooth (15-16fps) on my Pentium II/1Ghz machine. It gives a very good sense of what you are trying to do!
I''m not really sure what your first question is. Are you asking how you can test the ray against just the correct edge of the movie rectangle? There is going to be some logic to make the decision. You know that your starting point is always inside the movie rectangle. If (x2, y2) lies outside of the rectangle, thne if x_left <= x2 <= x_right then the ray can only intersect either the top or bottom edge of the movie rectangle. If x_left <= x2 <= x_right and y2 < y_bottom then the ray can only possibly intersect the bottom edge, and the bottom edge is the one to test against. You can follow this simple type of logic to determine the exact edge to test in every case. But be aware that the logic to do the tests takes time, and you may not actually save much time.
As for question 2, you could save some time by approximating your obstacles as a 2-point line segment for purposes of LOS calcs. That would save half of your calculations and quite a bit of logic, since your two rays would always originate from the same 2 points for each obstacle. The 2 point approximation would be for the 2 midpoints at the narrow edges of the obstacle. This would not really work if your obstacle can be a full rectangle with an aspect ratio of close to 1 (width is nearly the same as length).
Of course, it really isn''t necessary to create a separate shadow area for obstacles that are completely hidden in the shadow of another object. You could partition your world into a quadtree structure, which can make it quites fast to find just which objects need to be considered for LOS. This would really only work well if you have a narrow field-of-view, rather than the full 360-degree field-of-view shown in your demo. You might also look into BSP (binary space partition) trees. A BSP tree can represent the shadowing for you. Calculating the BSP tree is a pre-process step that could nearly eliminate the need to do runtime calculation of LOS. You''d just be reading from precalculated data. A google search should give you plenty of results on BSP trees. BSP trees are probably only appropriate if your basic world is static with none of the visual obstacles or walls moving around.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
I''m not really sure what your first question is. Are you asking how you can test the ray against just the correct edge of the movie rectangle? There is going to be some logic to make the decision. You know that your starting point is always inside the movie rectangle. If (x2, y2) lies outside of the rectangle, thne if x_left <= x2 <= x_right then the ray can only intersect either the top or bottom edge of the movie rectangle. If x_left <= x2 <= x_right and y2 < y_bottom then the ray can only possibly intersect the bottom edge, and the bottom edge is the one to test against. You can follow this simple type of logic to determine the exact edge to test in every case. But be aware that the logic to do the tests takes time, and you may not actually save much time.
As for question 2, you could save some time by approximating your obstacles as a 2-point line segment for purposes of LOS calcs. That would save half of your calculations and quite a bit of logic, since your two rays would always originate from the same 2 points for each obstacle. The 2 point approximation would be for the 2 midpoints at the narrow edges of the obstacle. This would not really work if your obstacle can be a full rectangle with an aspect ratio of close to 1 (width is nearly the same as length).
Of course, it really isn''t necessary to create a separate shadow area for obstacles that are completely hidden in the shadow of another object. You could partition your world into a quadtree structure, which can make it quites fast to find just which objects need to be considered for LOS. This would really only work well if you have a narrow field-of-view, rather than the full 360-degree field-of-view shown in your demo. You might also look into BSP (binary space partition) trees. A BSP tree can represent the shadowing for you. Calculating the BSP tree is a pre-process step that could nearly eliminate the need to do runtime calculation of LOS. You''d just be reading from precalculated data. A google search should give you plenty of results on BSP trees. BSP trees are probably only appropriate if your basic world is static with none of the visual obstacles or walls moving around.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Author
Actually, I tried something interesting and got it up a couple frames per second (thought i haven't worked all the bugs out yet).
Instead of doing these two steps:
1. get player->corner magnitudes
2. use dot product to find theta for each vector combination (finds which rays extend)
I just found the slopes of each player->corner line and found what two lines had the greatest difference in slope, ie, the biggest angle.
[edited by - ScottyH on October 17, 2002 9:06:35 PM]
Instead of doing these two steps:
1. get player->corner magnitudes
2. use dot product to find theta for each vector combination (finds which rays extend)
I just found the slopes of each player->corner line and found what two lines had the greatest difference in slope, ie, the biggest angle.
[edited by - ScottyH on October 17, 2002 9:06:35 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
