path: root/src/raycastlib.h

#ifndef RAYCASTLIB_H
#define RAYCASTLIB_H

/**
  raycastlib (RCL) - Small C header-only raycasting library for embedded and
  low performance computers, such as Arduino. Only uses integer math and stdint
  standard library.

  Check the defines below to fine-tune accuracy vs performance! Don't forget
  to compile with optimizations.

  Before including the library define RCL_PIXEL_FUNCTION to the name of the
  function (with RCL_PixelFunction signature) that will render your pixels!

  - All public (and most private) library identifiers start with RCL_.
  - Game field's bottom left corner is at [0,0].
  - X axis goes right in the ground plane.
  - Y axis goes up in the ground plane.
  - Height means the Z (vertical) coordinate.
  - Each game square is RCL_UNITS_PER_SQUARE * RCL_UNITS_PER_SQUARE points.
  - Angles are in RCL_Units, 0 means pointing right (x+) and positively rotates
    clockwise. A full angle has RCL_UNITS_PER_SQUARE RCL_Units.
  - Most things are normalized with RCL_UNITS_PER_SQUARE (sin, cos, vector
    unit length, texture coordinates etc.).
  - Screen coordinates are normal: [0,0] = top left, x goes right, y goes down.

  author: Miloslav "drummyfish" Ciz
  license: CC0 1.0
  version: 0.908d

  Version numbering: major.minor[d], id 'd' is appended, this is a
  in-development version based on the previous stable major.minor version. Two
  'd' versions with the same version number, .e.g. 1.0d, may be different.
*/

#include <stdint.h>

#ifndef RCL_RAYCAST_TINY /** Turns on super efficient version of this library.
                             Only use if neccesarry, looks ugly. Also not done
                             yet. */
  #define RCL_UNITS_PER_SQUARE 1024 /**< Number of RCL_Units in a side of a
                                         spatial square. */
  typedef int32_t RCL_Unit; /**< Smallest spatial unit, there is
                                 RCL_UNITS_PER_SQUARE units in a square's
                                 length. This effectively serves the purpose of
                                 a fixed-point arithmetic. */
  #define RCL_INFINITY 2000000000
#else
  #define RCL_UNITS_PER_SQUARE 32
  typedef int16_t RCL_Unit;
  #define RCL_INFINITY 30000
  #define RCL_USE_DIST_APPROX 2
#endif

#ifndef RCL_COMPUTE_WALL_TEXCOORDS
#define RCL_COMPUTE_WALL_TEXCOORDS 1
#endif

#ifndef RCL_COMPUTE_FLOOR_TEXCOORDS
#define RCL_COMPUTE_FLOOR_TEXCOORDS 0
#endif

#ifndef RCL_FLOOR_TEXCOORDS_HEIGHT
#define RCL_FLOOR_TEXCOORDS_HEIGHT 0 /** If RCL_COMPUTE_FLOOR_TEXCOORDS == 1,
                                      this says for what height level the
                                      texture coords will be computed for
                                      (for simplicity/performance only one
                                      level is allowed). */
#endif

#ifndef RCL_USE_COS_LUT
#define RCL_USE_COS_LUT 0 /**< type of look up table for cos function:
                           0: none (compute)
                           1: 64 items
                           2: 128 items */
#endif

#ifndef RCL_USE_DIST_APPROX
#define RCL_USE_DIST_APPROX 0 /**< What distance approximation to use:
                            0: none (compute full Euclidean distance)
                            1: accurate approximation
                            2: octagonal approximation (LQ) */
#endif

#ifndef RCL_RECTILINEAR
#define RCL_RECTILINEAR 1 /**< Whether to use rectilinear perspective (normally
                              used), or curvilinear perspective (fish eye). */
#endif

#ifndef RCL_TEXTURE_VERTICAL_STRETCH
#define RCL_TEXTURE_VERTICAL_STRETCH 1 /**< Whether textures should be
                                       stretched to wall height (possibly
                                       slightly slower if on). */
#endif

#ifndef RCL_COMPUTE_FLOOR_DEPTH
#define RCL_COMPUTE_FLOOR_DEPTH 1 /**< Whether depth should be computed for
                                   floor pixels - turns this off if not
                                   needed. */
#endif

#ifndef RCL_COMPUTE_CEILING_DEPTH
#define RCL_COMPUTE_CEILING_DEPTH 1 /**< As RCL_COMPUTE_FLOOR_DEPTH but for
                                     ceiling. */
#endif

#ifndef RCL_ROLL_TEXTURE_COORDS
#define RCL_ROLL_TEXTURE_COORDS 1 /**< Says whether rolling doors should also
                                   roll the texture coordinates along (mostly
                                   desired for doors). */
#endif

#ifndef RCL_VERTICAL_FOV
#define RCL_VERTICAL_FOV (RCL_UNITS_PER_SQUARE / 3)
#endif

#define RCL_VERTICAL_FOV_TAN (RCL_VERTICAL_FOV * 4) ///< tan approximation

#ifndef RCL_HORIZONTAL_FOV
#define RCL_HORIZONTAL_FOV (RCL_UNITS_PER_SQUARE / 4)
#endif

#define RCL_HORIZONTAL_FOV_TAN (RCL_HORIZONTAL_FOV * 4)

#define RCL_HORIZONTAL_FOV_HALF (RCL_HORIZONTAL_FOV / 2)

#ifndef RCL_CAMERA_COLL_RADIUS
#define RCL_CAMERA_COLL_RADIUS RCL_UNITS_PER_SQUARE / 4
#endif

#ifndef RCL_CAMERA_COLL_HEIGHT_BELOW
#define RCL_CAMERA_COLL_HEIGHT_BELOW RCL_UNITS_PER_SQUARE
#endif 

#ifndef RCL_CAMERA_COLL_HEIGHT_ABOVE
#define RCL_CAMERA_COLL_HEIGHT_ABOVE (RCL_UNITS_PER_SQUARE / 3)
#endif

#ifndef RCL_CAMERA_COLL_STEP_HEIGHT
#define RCL_CAMERA_COLL_STEP_HEIGHT (RCL_UNITS_PER_SQUARE / 2)
#endif

#ifndef RCL_TEXTURE_INTERPOLATION_SCALE
  #define RCL_TEXTURE_INTERPOLATION_SCALE 1024 /**< This says scaling of fixed
                                             poit vertical texture coord
                                             computation. This should be power
                                             of two! Higher number can look more 
                                             accurate but may cause overflow. */
#endif

#define RCL_HORIZON_DEPTH (11 * RCL_UNITS_PER_SQUARE) /**< What depth the
                                                       horizon has (the floor
                                                       depth is only
                                                       approximated with the
                                                       help of this
                                                       constant). */
#ifndef RCL_VERTICAL_DEPTH_MULTIPLY
#define RCL_VERTICAL_DEPTH_MULTIPLY 2 /**< Defines a multiplier of height
                                       difference when approximating floor/ceil
                                       depth. */
#endif

#define RCL_min(a,b) ((a) < (b) ? (a) : (b))
#define RCL_max(a,b) ((a) > (b) ? (a) : (b))
#define RCL_nonZero(v) ((v) + ((v) == 0)) ///< To prevent zero divisions.
#define RCL_zeroClamp(x) ((x) * ((x) >= 0))
#define RCL_likely(cond)    __builtin_expect(!!(cond),1) 
#define RCL_unlikely(cond)  __builtin_expect(!!(cond),0) 

#define RCL_logV2D(v)\
  printf("[%d,%d]\n",v.x,v.y);

#define RCL_logRay(r){\
  printf("ray:\n");\
  printf("  start: ");\
  RCL_logV2D(r.start);\
  printf("  dir: ");\
  RCL_logV2D(r.direction);}

#define RCL_logHitResult(h){\
  printf("hit:\n");\
  printf("  square: ");\
  RCL_logV2D(h.square);\
  printf("  pos: ");\
  RCL_logV2D(h.position);\
  printf("  dist: %d\n", h.distance);\
  printf("  dir: %d\n", h.direction);\
  printf("  texcoord: %d\n", h.textureCoord);}

#define RCL_logPixelInfo(p){\
  printf("pixel:\n");\
  printf("  position: ");\
  RCL_logV2D(p.position);\
  printf("  texCoord: ");\
  RCL_logV2D(p.texCoords);\
  printf("  depth: %d\n", p.depth);\
  printf("  height: %d\n", p.height);\
  printf("  wall: %d\n", p.isWall);\
  printf("  hit: ");\
  RCL_logHitResult(p.hit);\
  }

#define RCL_logCamera(c){\
  printf("camera:\n");\
  printf("  position: ");\
  RCL_logV2D(c.position);\
  printf("  height: %d\n",c.height);\
  printf("  direction: %d\n",c.direction);\
  printf("  shear: %d\n",c.shear);\
  printf("  resolution: %d x %d\n",c.resolution.x,c.resolution.y);\
  }

/// Position in 2D space.
typedef struct
{
  RCL_Unit x;
  RCL_Unit y;
} RCL_Vector2D;

typedef struct
{
  RCL_Vector2D start;
  RCL_Vector2D direction;
} RCL_Ray;

typedef struct
{
  RCL_Unit     distance; /**< Distance to the hit position, or -1 if no
                              collision happened. If RCL_RECTILINEAR != 0, then
                              the distance is perpendicular to the projection
                              plane (fish eye correction), otherwise it is
                              the straight distance to the ray start
                              position. */
  uint8_t      direction;    /**< Direction of hit. The convention for angle
                                  units is explained above. */
  RCL_Unit     textureCoord; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1)
                                  texture coordinate (horizontal). */
  RCL_Vector2D square;       ///< Collided square coordinates.
  RCL_Vector2D position;     ///< Exact collision position in RCL_Units.
  RCL_Unit     arrayValue;   /**  Value returned by array function (most often
                                  this will be the floor height). */
  RCL_Unit     type;         /**< Integer identifying type of square (number
                                  returned by type function, e.g. texture
                                  index).*/
  RCL_Unit     doorRoll;     ///< Holds value of door roll.
} RCL_HitResult;

typedef struct
{
  RCL_Vector2D position;
  RCL_Unit     direction;  // TODO: rename to "angle" to keep consistency
  RCL_Vector2D resolution;
  int16_t      shear; /**< Shear offset in pixels (0 => no shear), can simulate
                           looking up/down. */
  RCL_Unit     height;
} RCL_Camera;

/**
  Holds an information about a single rendered pixel (for a pixel function
  that works as a fragment shader).
*/
typedef struct
{
  RCL_Vector2D  position;  ///< On-screen position.
  int8_t        isWall;    ///< Whether the pixel is a wall or a floor/ceiling.
  int8_t        isFloor;   ///< Whether the pixel is floor or ceiling.
  int8_t        isHorizon; ///< If the pixel belongs to horizon segment.
  RCL_Unit      depth;     ///< Corrected depth.
  RCL_Unit      wallHeight;///< Only for wall pixels, says its height.
  RCL_Unit      height;    ///< World height (mostly for floor).
  RCL_HitResult hit;       ///< Corresponding ray hit.
  RCL_Vector2D  texCoords; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1)
                                texture coordinates. */
} RCL_PixelInfo;

void RCL_PIXEL_FUNCTION (RCL_PixelInfo *pixel);

typedef struct
{
  uint16_t maxHits;
  uint16_t maxSteps;
} RCL_RayConstraints;

/**
  Function used to retrieve some information about cells of the rendered scene.
  It should return a characteristic of given square as an integer (e.g. square
  height, texture index, ...) - between squares that return different numbers
  there is considered to be a collision.

  This function should be as fast as possible as it will typically be called
  very often.
*/ 
typedef RCL_Unit (*RCL_ArrayFunction)(int16_t x, int16_t y);
/*
  TODO: maybe array functions should be replaced by defines of funtion names
  like with pixelFunc? Could be more efficient than function pointers.
*/


RCL_Unit RCL_divRoundDown(RCL_Unit value, RCL_Unit divisor);

/**
  Function that renders a single pixel at the display. It is handed an info
  about the pixel it should draw.

  This function should be as fast as possible as it will typically be called
  very often.
*/
typedef void (*RCL_PixelFunction)(RCL_PixelInfo *info);

typedef void
  (*RCL_ColumnFunction)(RCL_HitResult *hits, uint16_t hitCount, uint16_t x,
   RCL_Ray ray);

/**
  Simple-interface function to cast a single ray.

  @return          The first collision result.
*/
RCL_HitResult RCL_castRay(RCL_Ray ray, RCL_ArrayFunction arrayFunc);

/**
  Casts a 3D ray in 3D environment with floor and optional ceiling
  (ceilingHeightFunc can be 0). This can be useful for hitscan shooting,
  visibility checking etc.

  @return normalized ditance (0 to RCL_UNITS_PER_SQUARE) along the ray at which
          the environment was hit, RCL_UNITS_PER_SQUARE means nothing was hit
*/
RCL_Unit RCL_castRay3D(
  RCL_Vector2D pos1, RCL_Unit height1, RCL_Vector2D pos2, RCL_Unit height2,
  RCL_ArrayFunction floorHeightFunc, RCL_ArrayFunction ceilingHeightFunc,
  RCL_RayConstraints constraints);

/**
  Maps a single point in the world to the screen (2D position + depth).
*/
RCL_PixelInfo RCL_mapToScreen(RCL_Vector2D worldPosition, RCL_Unit height,
  RCL_Camera camera);

/**
  Casts a single ray and returns a list of collisions.

  @param ray ray to be cast, if RCL_RECTILINEAR != 0 then the computed hit
         distance is divided by the ray direction vector length (to correct
         the fish eye effect)
  @param arrayFunc function that will be used to determine collisions (hits)
         with the ray (squares for which this function returns different values
         are considered to have a collision between them), this will typically
         be a function returning floor height
  @param typeFunc optional (can be 0) function - if provided, it will be used
         to mark the hit result with the number returned by this function
         (it can be e.g. a texture index)
  @param hitResults array in which the hit results will be stored (has to be
         preallocated with at space for at least as many hit results as
         maxHits specified with the constraints parameter)
  @param hitResultsLen in this variable the number of hit results will be
         returned
  @param constraints specifies constraints for the ray cast
*/
void RCL_castRayMultiHit(RCL_Ray ray, RCL_ArrayFunction arrayFunc,
  RCL_ArrayFunction typeFunc, RCL_HitResult *hitResults,
  uint16_t *hitResultsLen, RCL_RayConstraints constraints);

RCL_Vector2D RCL_angleToDirection(RCL_Unit angle);

/**
Cos function.

@param  input to cos in RCL_Units (RCL_UNITS_PER_SQUARE = 2 * pi = 360 degrees)
@return RCL_normalized output in RCL_Units (from -RCL_UNITS_PER_SQUARE to
        RCL_UNITS_PER_SQUARE)
*/
RCL_Unit RCL_cos(RCL_Unit input);

RCL_Unit RCL_sin(RCL_Unit input);

RCL_Unit RCL_tan(RCL_Unit input);

RCL_Unit RCL_ctg(RCL_Unit input);

/// Normalizes given vector to have RCL_UNITS_PER_SQUARE length.
RCL_Vector2D RCL_normalize(RCL_Vector2D v);

/// Computes a cos of an angle between two vectors.
RCL_Unit RCL_vectorsAngleCos(RCL_Vector2D v1, RCL_Vector2D v2);

uint16_t RCL_sqrt(RCL_Unit value);
RCL_Unit RCL_dist(RCL_Vector2D p1, RCL_Vector2D p2);
RCL_Unit RCL_len(RCL_Vector2D v);

/**
  Converts an angle in whole degrees to an angle in RCL_Units that this library
  uses.
*/   
RCL_Unit RCL_degreesToUnitsAngle(int16_t degrees);

///< Computes the change in size of an object due to perspective (vertical FOV).
RCL_Unit RCL_perspectiveScaleVertical(RCL_Unit originalSize, RCL_Unit distance);

RCL_Unit RCL_perspectiveScaleVerticalInverse(RCL_Unit originalSize,
  RCL_Unit scaledSize);

RCL_Unit
  RCL_perspectiveScaleHorizontal(RCL_Unit originalSize, RCL_Unit distance);

RCL_Unit RCL_perspectiveScaleHorizontalInverse(RCL_Unit originalSize,
  RCL_Unit scaledSize);

/**
  Casts rays for given camera view and for each hit calls a user provided
  function.
*/
void RCL_castRaysMultiHit(RCL_Camera cam, RCL_ArrayFunction arrayFunc,
  RCL_ArrayFunction typeFunction, RCL_ColumnFunction columnFunc,
  RCL_RayConstraints constraints);

/**
  Using provided functions, renders a complete complex (multilevel) camera
  view.

  This function should render each screen pixel exactly once.

  function rendering summary:
  - performance:            slower
  - accuracy:               higher
  - wall textures:          yes
  - different wall heights: yes
  - floor/ceiling textures: no
  - floor geometry:         yes, multilevel
  - ceiling geometry:       yes (optional), multilevel
  - rolling door:           no
  - camera shearing:        yes
  - rendering order:        left-to-right, not specifically ordered vertically

  @param cam camera whose view to render
  @param floorHeightFunc function that returns floor height (in RCL_Units)
  @param ceilingHeightFunc same as floorHeightFunc but for ceiling, can also be
                           0 (no ceiling will be rendered)
  @param typeFunction function that says a type of square (e.g. its texture
                     index), can be 0 (no type in hit result)
  @param pixelFunc callback function to draw a single pixel on screen
  @param constraints constraints for each cast ray
*/
void RCL_renderComplex(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
  RCL_ArrayFunction ceilingHeightFunc, RCL_ArrayFunction typeFunction,
  RCL_RayConstraints constraints);

/**
  Renders given camera view, with help of provided functions. This function is
  simpler and faster than RCL_renderComplex(...) and is meant to be rendering
  flat levels.

  function rendering summary:
  - performance:            faster
  - accuracy:               lower
  - wall textures:          yes
  - different wall heights: yes
  - floor/ceiling textures: yes (only floor, you can mirror it for ceiling)
  - floor geometry:         no (just flat floor, with depth information)
  - ceiling geometry:       no (just flat ceiling, with depth information)
  - rolling door:           yes
  - camera shearing:        no
  - rendering order:        left-to-right, top-to-bottom

  Additionally this function supports rendering rolling doors.

  This function should render each screen pixel exactly once.

  @param rollFunc function that for given square says its door roll in
         RCL_Units (0 = no roll, RCL_UNITS_PER_SQUARE = full roll right,
         -RCL_UNITS_PER_SQUARE = full roll left), can be zero (no rolling door,
         rendering should also be faster as fewer intersections will be tested)
*/
void RCL_renderSimple(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
  RCL_ArrayFunction typeFunc, RCL_ArrayFunction rollFunc,
  RCL_RayConstraints constraints);

/**
  Function that moves given camera and makes it collide with walls and
  potentially also floor and ceilings. It's meant to help implement player
  movement.

  @param camera camera to move
  @param planeOffset offset to move the camera in
  @param heightOffset height offset to move the camera in
  @param floorHeightFunc function used to retrieve the floor height
  @param ceilingHeightFunc function for retrieving ceiling height, can be 0
                           (camera won't collide with ceiling)
  @param computeHeight whether to compute height - if false (0), floor and
                       ceiling functions won't be used and the camera will
                       only collide horizontally with walls (good for simpler
                       game, also faster)
  @param force if true, forces to recompute collision even if position doesn't
               change
*/
void RCL_moveCameraWithCollision(RCL_Camera *camera, RCL_Vector2D planeOffset,
  RCL_Unit heightOffset, RCL_ArrayFunction floorHeightFunc,
  RCL_ArrayFunction ceilingHeightFunc, int8_t computeHeight, int8_t force);

void RCL_initCamera(RCL_Camera *camera);
void RCL_initRayConstraints(RCL_RayConstraints *constraints);

#endif