/******************************************************************************* * apps/graphics/traveler/src/trv_rayavoid.c * This file contains the logic which determines if the desired player motion * would cause a collision with various walls or if the motion would cause * the player to change his vertical position in the world. This collision * avoidance logic is also used to determine if there is a door in front of * the player. * * Copyright (C) 2014 Gregory Nutt. All rights reserved. * Author: Gregory Nutt * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * 3. Neither the name NuttX nor the names of its contributors may be * used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * ****************************************************************************/ /***************************************************************************** * Included files ****************************************************************************/ #include "trv_types.h" #include "trv_trigtbl.h" #include "trv_plane.h" #include "trv_world.h" #include "trv_rayavoid.h" /***************************************************************************** * Pre-processor Definitions ****************************************************************************/ /* This is the closest that we will allow the player to approach a wall */ #define MIN_APPROACH_DISTANCE (64/4) /* One quarter cell */ /***************************************************************************** * Private Data ****************************************************************************/ /* The rayClipPlayX/YMotion functions have the side effect of saving the * pointer to the wall with which the player collided in the following * private variable. This gives a "back door" mechanism which is used * to handle door processing. */ static struct trv_rect_data_s *g_clip_rect; /***************************************************************************** * Public Functions ****************************************************************************/ /***************************************************************************** * Name: trv_ray_test_xplane * * Description: * * This function tests if there is an X plane within the supplied distance * from the player at the supplied angle. This function is used to * determine in there is a door in front of the player. NOTE: This * function exploits the normal collision detection logic in * trv_rayclip_player_xmotion and depends on the side-effect setting of * g_clip_rect. * *****************************************************************************/ FAR struct trv_rect_data_s *trv_ray_test_xplane(FAR struct trv_camera_s *pov, trv_coord_t dist, int16_t yaw, trv_coord_t height) { (void) trv_rayclip_player_xmotion(pov, dist, yaw, height); return g_clip_rect; } /***************************************************************************** * Name: trv_rayclip_player_xmotion * * Description: * This function calculates the acceptable change in the player's position * along the X component of the specified yaw angle which would not cause * a collision with an X plane. This logic is essentially a modified X * ray cast. * *****************************************************************************/ trv_coord_t trv_rayclip_player_xmotion(FAR struct trv_camera_s *pov, trv_coord_t dist, int16_t yaw, trv_coord_t height) { FAR struct trv_rect_list_s *list; /* Points to the current X plane rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t reqdeltax; trv_coord_t standoff; trv_coord_t footlevel; trv_coord_t relx; /* Relative position of the X plane */ trv_coord_t absy; /* Absolute Y position at relx given yaw */ trv_coord_t lastrelx = -1; /* Last relative X position processed */ /* Decompose the desired move distance into its X component */ reqdeltax = tTOs(g_cos_table[ yaw ] * dist); /* Assume that no clipping will be performed */ g_clip_rect = NULL; /* Perform X raycasting based on the quadrant of the yaw angle */ /* The first and fourth quadrants correspond to the positive X * direction (excluding angles 90 and 270). */ if (yaw < ANGLE_90 || yaw > ANGLE_270) { /* Calculate the requested distance along the (positive) X axis (adding * a little to how close the play can come to a wall */ standoff = reqdeltax + MIN_APPROACH_DISTANCE; /* This is the position of the player's feet */ footlevel = pov->z - height; /* Look at every rectangle lying in the X plane */ for (list = g_xplane.head; list; list = list->flink) { rect = &list->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > pov->x) { /* Get the X distance to the plane. This is an order list: if * the distance to the plane is larger then the requested step * then the requested step is acceptable. */ relx = rect->plane - pov->x; if (relx >= standoff) { return reqdeltax; } /* The distance to the plane is smaller that the requested step. * It may be possible to collide with the plane. Check if a * collision due to the height of the player is possible first * (its easier to compute) */ if (footlevel >= rect->vstart && pov->z <= rect->vend) { /* A collision is possible based on the players height. * Now, we'll have to check if a collision is possible * due to the player's Y position. We can skip this * step if we are processing another rectangle at the * same relx distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The tangent is equal to the rate of change of Y with * respect to the X-axis. The tangent is stored at * double the the "normal" scaling -- so deltay is * "triple" precision */ deltay = TAN(yaw) * ((int32_t)relx); absy = tTOs(deltay) + pov->y; /* back to "single" */ lastrelx = relx; } /* Check if this Y position intersects the rectangle */ if (absy >= rect->hstart && absy <= rect->hend) { /* It collides -- Check, maybe we can walk through * this wall */ if (!IS_PASSABLE(rect)) { /* Nope... return a clipped value for the new * player position (which includes the a stand-off * constant) * NOTE: This returned value could be negative! */ g_clip_rect = rect; return relx - MIN_APPROACH_DISTANCE; } } } } } } /* The second and third quadrants correspond to the negative X * direction (excluding angles 90 and 270). */ else if (yaw > ANGLE_90 && yaw < ANGLE_270) { /* Calculate the requested distance along the (negative) X axis * (adding a little to how close the play can come to a wall) */ standoff = MIN_APPROACH_DISTANCE - reqdeltax; /* This is the position of the player's feet */ footlevel = pov->z - height; /* Look at every rectangle lying in the X plane */ for (list = g_xplane.tail; list; list = list->blink) { rect = &list->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < pov->x) { /* Get the X distance to the plane. This is an order list: * if the distance to the plane is larger then the requested * step then the requested step is acceptable. */ relx = pov->x - rect->plane; if (relx >= standoff) { return reqdeltax; } /* The distance to the plane is smaller that the requested * step. It may be possible to collide with the plane. Check * if a collision due to the height of the player is possible * first (its easier to compute) */ if (footlevel >= rect->vstart && pov->z <= rect->vend) { /* A collision is possible based on the players height. * Now, we'll have to check if a collision is possible due * to the player's Y position. We can skip this step if * we are processing another rectangle at the same relx * distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The negative tangent is equal to the rate of change * of Y with respect to the X-axis.The tangent is * stored at double the the "normal" scaling -- so * deltay is "triple" precision */ deltay = -TAN(yaw) * ((int32_t)relx); absy = tTOs(deltay) + pov->y; /* back to "single" */ lastrelx = relx; } /* Check if this Y position intersects the rectangle */ if (absy >= rect->hstart && absy <= rect->hend) { /* It collides -- Check, maybe we can walk through * this wall? */ if (!IS_PASSABLE(rect)) { /* Nope -- return a clipped value for the new * player position (which includes the a stand-off * constant) * NOTE: This returned value could be positive! */ g_clip_rect = rect; return MIN_APPROACH_DISTANCE - relx; } } } } } } /* If we got there, then no collisions were found. Just return the * requested step value */ return reqdeltax; } /***************************************************************************** * Name: trv_ray_test_yplane * * Description: * This function tests if there is an Y plane within the supplied distance * from the player at the supplied angle. This function is used to * determine in there is a door in front of the player. NOTE: This * function exploits the normal collision detection logic in * trv_rayclip_player_ymotion and depends on the side-effect setting of * g_clip_rect. * ****************************************************************************/ FAR struct trv_rect_data_s *trv_ray_test_yplane(FAR struct trv_camera_s *pov, trv_coord_t dist, int16_t yaw, trv_coord_t height) { (void)trv_rayclip_player_ymotion(pov, dist, yaw, height); return g_clip_rect; } /***************************************************************************** * Name: trv_rayclip_player_ymotion * * Description: * This function calculates the acceptable change in the player's position * along the Y component of the specified yaw angle which would not cause * a collision with a Y plane. This logic is essentially a modified X * ray cast. * ****************************************************************************/ trv_coord_t trv_rayclip_player_ymotion(FAR struct trv_camera_s *pov, trv_coord_t dist, int16_t yaw, trv_coord_t height) { FAR struct trv_rect_list_s *list; /* Points to the current Y plane rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t reqdeltay; trv_coord_t standoff; trv_coord_t footlevel; trv_coord_t rely; /* Relative position of the Y plane */ trv_coord_t absx; /* Absolute X position at rely given yaw */ trv_coord_t lastrely = -1; /* Last relative Y position processed */ /* Decompose the desired move distance into its Y component */ reqdeltay = tTOs(g_sin_table[ yaw ] * dist); /* Assume that no clipping will be performed */ g_clip_rect = NULL; /* Perform Y raycasting based on the quadrant of the yaw angle */ /* The first and second quadrants correspond to the positive Y * direction (excluding angles 0 and 180). */ if (yaw > ANGLE_0 && yaw < ANGLE_180) { /* Calculate the requested distance along the (positive) X axis * (adding a little to how close the play can come to a wall) */ standoff = reqdeltay + MIN_APPROACH_DISTANCE; /* This is the position of the player's feet */ footlevel = pov->z - height; /* Look at every rectangle lying in a Y plane */ for (list = g_yplane.head; list; list = list->flink) { rect = &list->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > pov->y) { /* Get the Y distance to the plane. This is an order list: * If the distance to the plane is larger then the requested * step then the requested step is acceptable. */ rely = rect->plane - pov->y; if (rely >= standoff) { return reqdeltay; } /* The distance to the plane is smaller that the requested * step. It may be possible to collide with the plane. * Check if a collision due to the height of the player is * possible first (its easier to compute) */ if (footlevel >= rect->vstart && pov->z <= rect->vend) { /* A collision is possible based on the players height. * Now, we'll have to check if a collision is possible * due to the player's X position. We can skip this * step if we are processing another rectangle at the * same relx distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The inverted tangent is equal to the rate of change * of X with respect to the Y-axis. The cotangent is * stored at double the the "normal" scaling -- so * deltax is "triple" precision */ deltax = g_cot_table(yaw) * ((int32_t)rely); absx = tTOs(deltax) + pov->x; /* back to "single" */ lastrely = rely; } /* Check if this X position intersects the rectangle */ if (absx >= rect->hstart && absx <= rect->hend) { /* It collides -- Check, maybe we can walk through * this wall? */ if (!IS_PASSABLE(rect)) { /* Nope -- return a clipped value for the new * player position (which includes the a stand-off * constant) * NOTE: This returned value could be negative! */ g_clip_rect = rect; return rely - MIN_APPROACH_DISTANCE; } } } } } } /* The third and fourth quadrants correspond to the negative Y * direction (excluding angles 0 and 180). */ else if (yaw > ANGLE_180) { /* Calculate the requested distance along the (negative) X axis * (adding a little to how close the play can come to a wall) */ standoff = MIN_APPROACH_DISTANCE - reqdeltay; /* This is the position of the player's feet */ footlevel = pov->z - height; /* Look at every rectangle lying in the X plane */ for (list = g_yplane.tail; list; list = list->blink) { rect = &list->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < pov->y) { /* Get the X distance to the plane. This is an order list: if * the distance to the plane is larger then the requested step * then the requested step is acceptable. */ rely = pov->y - rect->plane; if (rely >= standoff) { return reqdeltay; } /* The distance to the plane is smaller that the requested * step. It may be possible to collide with the plane. Check * if a collision due to the height of the player is possible * first (its easier to compute) */ if (footlevel >= rect->vstart && pov->z <= rect->vend) { /* A collision is possible based on the players height. * Now, we'll have to check if a collision is possible due * to the player's X position. We can skip this step if * we are processing another rectangle at the same relx * distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The negative inverted tangent is equal to the rate * of change of X with respect to the Y-axis. The * cotangent is stored at double the the "normal" * scaling -- so deltax is "triple" precision */ deltax = -g_cot_table(yaw - ANGLE_180) * ((int32_t)rely); absx = tTOs(deltax) + pov->x; /* back to "single" */ lastrely = rely; } /* Check if this X position intersects the rectangle */ if (absx >= rect->hstart && absx <= rect->hend) { /* It collides -- Check, maybe we can walk through * this wall */ if (!IS_PASSABLE(rect)) { /* It collides -- return a clipped value for the * new player position (which includes the a * stand-off constant) * NOTE: This returned value could be positive! */ g_clip_rect = rect; return MIN_APPROACH_DISTANCE - rely; } } } } } } /* Return the clipped value */ return reqdeltay; } /***************************************************************************** * Name: trv_ray_adjust_zpos * * Description: * Make sure that the player is standing on something! * ****************************************************************************/ trv_coord_t trv_ray_adjust_zpos(FAR struct trv_camera_s *pov, trv_coord_t height) { struct trv_rect_list_s *list; /* Points to the current Z plane rectangle */ struct trv_rect_data_s *rect; /* Points to the rectangle data */ /* We will place the player's feet at the largest Z plane * which is lower the the player's eye level. We traverse * the the g_zplane list in order of increase Z values */ for (list = g_zplane.head; list; list = list->flink) { rect = &list->d; /* The Z plane list is an ordered list. If the next * plane is over the player's head, then the player * must be standing at "ground zero." */ if (rect->plane >= pov->z) { return height - pov->z; } /* Check if this plane if under the player */ if (pov->x >= rect->hstart && pov->x <= rect->hend && pov->y >= rect->vstart && pov->y <= rect->vend) { /* We have the the smallest Z plane under the player * which is below the player's eye level (pov->z). * Determine the approach delta Z value to return */ return height + rect->plane - pov->z; } } /* No plane was found under the player. Set him at his * height above the "bottom" of the world */ return height - pov->z; }