initial commit

1 files changed, 504 insertions, 0 deletions

diff --git a/src/raycastlib.h b/src/raycastlib.h
new file mode 100644
index 0000000..c882bfd
--- /dev/null
+++ b/src/raycastlib.h
@@ -0,0 +1,504 @@
+#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