raycastlib.h

   1 #ifndef RAYCASTLIB_H
   2 #define RAYCASTLIB_H
   3
   4 /**
   5   raycastlib (RCL) - Small C header-only raycasting library for embedded and
   6   low performance computers, such as Arduino. Only uses integer math and stdint
   7   standard library.
   8
   9   Check the defines below to fine-tune accuracy vs performance! Don't forget
  10   to compile with optimizations.
  11
  12   Before including the library define RCL_PIXEL_FUNCTION to the name of the
  13   function (with RCL_PixelFunction signature) that will render your pixels!
  14
  15   - All public (and most private) library identifiers start with RCL_.
  16   - Game field's bottom left corner is at [0,0].
  17   - X axis goes right in the ground plane.
  18   - Y axis goes up in the ground plane.
  19   - Height means the Z (vertical) coordinate.
  20   - Each game square is RCL_UNITS_PER_SQUARE * RCL_UNITS_PER_SQUARE points.
  21   - Angles are in RCL_Units, 0 means pointing right (x+) and positively rotates
  22     clockwise. A full angle has RCL_UNITS_PER_SQUARE RCL_Units.
  23   - Most things are normalized with RCL_UNITS_PER_SQUARE (sin, cos, vector
  24     unit length, texture coordinates etc.).
  25   - Screen coordinates are normal: [0,0] = top left, x goes right, y goes down.
  26
  27   author: Miloslav "drummyfish" Ciz
  28   license: CC0 1.0
  29   version: 0.902
  30 */
  31
  32 #include <stdint.h>
  33
  34 #ifndef RCL_RAYCAST_TINY /** Turns on super efficient version of this library.
  35                              Only use if neccesarry, looks ugly. Also not done
  36                              yet. */
  37   #define RCL_UNITS_PER_SQUARE 1024 /**< Number of RCL_Units in a side of a
  38                                          spatial square. */
  39   typedef int32_t RCL_Unit; /**< Smallest spatial unit, there is
  40                                  RCL_UNITS_PER_SQUARE units in a square's
  41                                  length. This effectively serves the purpose of
  42                                  a fixed-point arithmetic. */
  43   #define RCL_INFINITY 2000000000
  44 #else
  45   #define RCL_UNITS_PER_SQUARE 32
  46   typedef int16_t RCL_Unit;
  47   #define RCL_INFINITY 30000
  48   #define RCL_USE_DIST_APPROX 2
  49 #endif
  50
  51 #ifndef RCL_COMPUTE_WALL_TEXCOORDS
  52 #define RCL_COMPUTE_WALL_TEXCOORDS 1
  53 #endif
  54
  55 #ifndef RCL_COMPUTE_FLOOR_TEXCOORDS
  56 #define RCL_COMPUTE_FLOOR_TEXCOORDS 0
  57 #endif
  58
  59 #ifndef RCL_FLOOR_TEXCOORDS_HEIGHT
  60 #define RCL_FLOOR_TEXCOORDS_HEIGHT 0 /** If RCL_COMPUTE_FLOOR_TEXCOORDS == 1,
  61                                       this says for what height level the
  62                                       texture coords will be computed for
  63                                       (for simplicity/performance only one
  64                                       level is allowed). */
  65 #endif
  66
  67 #ifndef RCL_USE_COS_LUT
  68 #define RCL_USE_COS_LUT 0 /**< type of look up table for cos function:
  69                            0: none (compute)
  70                            1: 64 items
  71                            2: 128 items */
  72 #endif
  73
  74 #ifndef RCL_USE_DIST_APPROX
  75 #define RCL_USE_DIST_APPROX 0 /**< What distance approximation to use:
  76                             0: none (compute full Euclidean distance)
  77                             1: accurate approximation
  78                             2: octagonal approximation (LQ) */
  79 #endif
  80
  81 #ifndef RCL_RECTILINEAR
  82 #define RCL_RECTILINEAR 1 /**< Whether to use rectilinear perspective (normally
  83                               used), or curvilinear perspective (fish eye). */
  84 #endif
  85
  86 #ifndef RCL_TEXTURE_VERTICAL_STRETCH
  87 #define RCL_TEXTURE_VERTICAL_STRETCH 1 /**< Whether textures should be
  88                                        stretched to wall height (possibly
  89                                        slightly slower if on). */
  90 #endif
  91
  92 #ifndef RCL_COMPUTE_FLOOR_DEPTH
  93 #define RCL_COMPUTE_FLOOR_DEPTH 1 /**< Whether depth should be computed for
  94                                    floor pixels - turns this off if not
  95                                    needed. */
  96 #endif
  97
  98 #ifndef RCL_COMPUTE_CEILING_DEPTH
  99 #define RCL_COMPUTE_CEILING_DEPTH 1 /**< As RCL_COMPUTE_FLOOR_DEPTH but for
 100                                      ceiling. */
 101 #endif
 102
 103 #ifndef RCL_ROLL_TEXTURE_COORDS
 104 #define RCL_ROLL_TEXTURE_COORDS 1 /**< Says whether rolling doors should also
 105                                    roll the texture coordinates along (mostly
 106                                    desired for doors). */
 107 #endif
 108
 109 #ifndef RCL_VERTICAL_FOV
 110 #define RCL_VERTICAL_FOV (RCL_UNITS_PER_SQUARE / 2)
 111 #endif
 112
 113 #ifndef RCL_HORIZONTAL_FOV
 114 #define RCL_HORIZONTAL_FOV (RCL_UNITS_PER_SQUARE / 4)
 115 #endif
 116
 117 #define RCL_HORIZONTAL_FOV_HALF (RCL_HORIZONTAL_FOV / 2)
 118
 119 #ifndef RCL_CAMERA_COLL_RADIUS
 120 #define RCL_CAMERA_COLL_RADIUS RCL_UNITS_PER_SQUARE / 4
 121 #endif
 122
 123 #ifndef RCL_CAMERA_COLL_HEIGHT_BELOW
 124 #define RCL_CAMERA_COLL_HEIGHT_BELOW RCL_UNITS_PER_SQUARE
 125 #endif
 126
 127 #ifndef RCL_CAMERA_COLL_HEIGHT_ABOVE
 128 #define RCL_CAMERA_COLL_HEIGHT_ABOVE (RCL_UNITS_PER_SQUARE / 3)
 129 #endif
 130
 131 #ifndef RCL_CAMERA_COLL_STEP_HEIGHT
 132 #define RCL_CAMERA_COLL_STEP_HEIGHT (RCL_UNITS_PER_SQUARE / 2)
 133 #endif
 134
 135 #ifndef RCL_TEXTURE_INTERPOLATION_SCALE
 136   #define RCL_TEXTURE_INTERPOLATION_SCALE 1024 /**< This says scaling of fixed
 137                                              poit vertical texture coord
 138                                              computation. This should be power
 139                                              of two! Higher number can look more
 140                                              accurate but may cause overflow. */
 141 #endif
 142
 143 #define RCL_HORIZON_DEPTH (11 * RCL_UNITS_PER_SQUARE) /**< What depth the
 144                                                        horizon has (the floor
 145                                                        depth is only
 146                                                        approximated with the
 147                                                        help of this
 148                                                        constant). */
 149 #ifndef RCL_VERTICAL_DEPTH_MULTIPLY
 150 #define RCL_VERTICAL_DEPTH_MULTIPLY 2 /**< Defines a multiplier of height
 151                                        difference when approximating floor/ceil
 152                                        depth. */
 153 #endif
 154
 155 #define RCL_min(a,b) ((a) < (b) ? (a) : (b))
 156 #define RCL_max(a,b) ((a) > (b) ? (a) : (b))
 157 #define RCL_nonZero(v) ((v) + ((v) == 0)) ///< To prevent zero divisions.
 158 #define RCL_zeroClamp(x) ((x) * ((x) >= 0))
 159 #define RCL_likely(cond)    __builtin_expect(!!(cond),1)
 160 #define RCL_unlikely(cond)  __builtin_expect(!!(cond),0)
 161
 162 #define RCL_logV2D(v)\
 163   printf("[%d,%d]\n",v.x,v.y);
 164
 165 #define RCL_logRay(r){\
 166   printf("ray:\n");\
 167   printf("  start: ");\
 168   RCL_logV2D(r.start);\
 169   printf("  dir: ");\
 170   RCL_logV2D(r.direction);}
 171
 172 #define RCL_logHitResult(h){\
 173   printf("hit:\n");\
 174   printf("  square: ");\
 175   RCL_logV2D(h.square);\
 176   printf("  pos: ");\
 177   RCL_logV2D(h.position);\
 178   printf("  dist: %d\n", h.distance);\
 179   printf("  dir: %d\n", h.direction);\
 180   printf("  texcoord: %d\n", h.textureCoord);}
 181
 182 #define RCL_logPixelInfo(p){\
 183   printf("pixel:\n");\
 184   printf("  position: ");\
 185   RCL_logV2D(p.position);\
 186   printf("  texCoord: ");\
 187   RCL_logV2D(p.texCoords);\
 188   printf("  depth: %d\n", p.depth);\
 189   printf("  height: %d\n", p.height);\
 190   printf("  wall: %d\n", p.isWall);\
 191   printf("  hit: ");\
 192   RCL_logHitResult(p.hit);\
 193   }
 194
 195 #define RCL_logCamera(c){\
 196   printf("camera:\n");\
 197   printf("  position: ");\
 198   RCL_logV2D(c.position);\
 199   printf("  height: %d\n",c.height);\
 200   printf("  direction: %d\n",c.direction);\
 201   printf("  shear: %d\n",c.shear);\
 202   printf("  resolution: %d x %d\n",c.resolution.x,c.resolution.y);\
 203   }
 204
 205 /// Position in 2D space.
 206 typedef struct
 207 {
 208   RCL_Unit x;
 209   RCL_Unit y;
 210 } RCL_Vector2D;
 211
 212 typedef struct
 213 {
 214   RCL_Vector2D start;
 215   RCL_Vector2D direction;
 216 } RCL_Ray;
 217
 218 typedef struct
 219 {
 220   RCL_Unit     distance; /**< Distance to the hit position, or -1 if no
 221                               collision happened. If RCL_RECTILINEAR != 0, then
 222                               the distance is perpendicular to the projection
 223                               plane (fish eye correction), otherwise it is
 224                               the straight distance to the ray start
 225                               position. */
 226   uint8_t      direction;    /**< Direction of hit. The convention for angle
 227                                   units is explained above. */
 228   RCL_Unit     textureCoord; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1)
 229                                   texture coordinate (horizontal). */
 230   RCL_Vector2D square;       ///< Collided square coordinates.
 231   RCL_Vector2D position;     ///< Exact collision position in RCL_Units.
 232   RCL_Unit     arrayValue;   /**  Value returned by array function (most often
 233                                   this will be the floor height). */
 234   RCL_Unit     type;         /**< Integer identifying type of square (number
 235                                   returned by type function, e.g. texture
 236                                   index).*/
 237   RCL_Unit     doorRoll;     ///< Holds value of door roll.
 238 } RCL_HitResult;
 239
 240 typedef struct
 241 {
 242   RCL_Vector2D position;
 243   RCL_Unit     direction;
 244   RCL_Vector2D resolution;
 245   int16_t      shear; /**< Shear offset in pixels (0 => no shear), can simulate
 246                            looking up/down. */
 247   RCL_Unit     height;
 248 } RCL_Camera;
 249
 250 /**
 251   Holds an information about a single rendered pixel (for a pixel function
 252   that works as a fragment shader).
 253 */
 254 typedef struct
 255 {
 256   RCL_Vector2D  position;  ///< On-screen position.
 257   int8_t        isWall;    ///< Whether the pixel is a wall or a floor/ceiling.
 258   int8_t        isFloor;   ///< Whether the pixel is floor or ceiling.
 259   int8_t        isHorizon; ///< If the pixel belongs to horizon segment.
 260   RCL_Unit      depth;     ///< Corrected depth.
 261   RCL_Unit      wallHeight;///< Only for wall pixels, says its height.
 262   RCL_Unit      height;    ///< World height (mostly for floor).
 263   RCL_HitResult hit;       ///< Corresponding ray hit.
 264   RCL_Vector2D  texCoords; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1)
 265                                 texture coordinates. */
 266 } RCL_PixelInfo;
 267
 268 void RCL_PIXEL_FUNCTION (RCL_PixelInfo *pixel);
 269
 270 typedef struct
 271 {
 272   uint16_t maxHits;
 273   uint16_t maxSteps;
 274 } RCL_RayConstraints;
 275
 276 /**
 277   Function used to retrieve some information about cells of the rendered scene.
 278   It should return a characteristic of given square as an integer (e.g. square
 279   height, texture index, ...) - between squares that return different numbers
 280   there is considered to be a collision.
 281
 282   This function should be as fast as possible as it will typically be called
 283   very often.
 284 */
 285 typedef RCL_Unit (*RCL_ArrayFunction)(int16_t x, int16_t y);
 286 /*
 287   TODO: maybe array functions should be replaced by defines of funtion names
 288   like with pixelFunc? Could be more efficient than function pointers.
 289 */
 290
 291 /**
 292   Function that renders a single pixel at the display. It is handed an info
 293   about the pixel it should draw.
 294
 295   This function should be as fast as possible as it will typically be called
 296   very often.
 297 */
 298 typedef void (*RCL_PixelFunction)(RCL_PixelInfo *info);
 299
 300 typedef void
 301   (*RCL_ColumnFunction)(RCL_HitResult *hits, uint16_t hitCount, uint16_t x,
 302    RCL_Ray ray);
 303
 304 /**
 305   Simple-interface function to cast a single ray.
 306   @return          The first collision result.
 307 */
 308 RCL_HitResult RCL_castRay(RCL_Ray ray, RCL_ArrayFunction arrayFunc);
 309
 310 /**
 311   Maps a single point in the world to the screen (2D position + depth).
 312 */
 313 RCL_PixelInfo RCL_mapToScreen(RCL_Vector2D worldPosition, RCL_Unit height,
 314   RCL_Camera camera);
 315
 316 /**
 317   Casts a single ray and returns a list of collisions.
 318
 319   @param ray ray to be cast, if RCL_RECTILINEAR != 0 then the computed hit
 320          distance is divided by the ray direction vector length (to correct
 321          the fish eye effect)
 322   @param arrayFunc function that will be used to determine collisions (hits)
 323          with the ray (squares for which this function returns different values
 324          are considered to have a collision between them), this will typically
 325          be a function returning floor height
 326   @param typeFunc optional (can be 0) function - if provided, it will be used
 327          to mark the hit result with the number returned by this function
 328          (it can be e.g. a texture index)
 329   @param hitResults array in which the hit results will be stored (has to be
 330          preallocated with at space for at least as many hit results as
 331          maxHits specified with the constraints parameter)
 332   @param hitResultsLen in this variable the number of hit results will be
 333          returned
 334   @param constraints specifies constraints for the ray cast
 335 */
 336 void RCL_castRayMultiHit(RCL_Ray ray, RCL_ArrayFunction arrayFunc,
 337   RCL_ArrayFunction typeFunc, RCL_HitResult *hitResults,
 338   uint16_t *hitResultsLen, RCL_RayConstraints constraints);
 339
 340 RCL_Vector2D RCL_angleToDirection(RCL_Unit angle);
 341
 342 /**
 343 Cos function.
 344
 345 @param  input to cos in RCL_Units (RCL_UNITS_PER_SQUARE = 2 * pi = 360 degrees)
 346 @return RCL_normalized output in RCL_Units (from -RCL_UNITS_PER_SQUARE to
 347         RCL_UNITS_PER_SQUARE)
 348 */
 349 RCL_Unit RCL_cosInt(RCL_Unit input);
 350
 351 RCL_Unit RCL_sinInt(RCL_Unit input);
 352
 353 /// Normalizes given vector to have RCL_UNITS_PER_SQUARE length.
 354 RCL_Vector2D RCL_normalize(RCL_Vector2D v);
 355
 356 /// Computes a cos of an angle between two vectors.
 357 RCL_Unit RCL_vectorsAngleCos(RCL_Vector2D v1, RCL_Vector2D v2);
 358
 359 uint16_t RCL_sqrtInt(RCL_Unit value);
 360 RCL_Unit RCL_dist(RCL_Vector2D p1, RCL_Vector2D p2);
 361 RCL_Unit RCL_len(RCL_Vector2D v);
 362
 363 /**
 364   Converts an angle in whole degrees to an angle in RCL_Units that this library
 365   uses.
 366 */
 367 RCL_Unit RCL_degreesToUnitsAngle(int16_t degrees);
 368
 369 ///< Computes the change in size of an object due to perspective.
 370 RCL_Unit RCL_perspectiveScale(RCL_Unit originalSize, RCL_Unit distance);
 371
 372 RCL_Unit RCL_perspectiveScaleInverse(RCL_Unit originalSize,
 373   RCL_Unit scaledSize);
 374
 375 /**
 376   Casts rays for given camera view and for each hit calls a user provided
 377   function.
 378 */
 379 void RCL_castRaysMultiHit(RCL_Camera cam, RCL_ArrayFunction arrayFunc,
 380   RCL_ArrayFunction typeFunction, RCL_ColumnFunction columnFunc,
 381   RCL_RayConstraints constraints);
 382
 383 /**
 384   Using provided functions, renders a complete complex (multilevel) camera
 385   view.
 386
 387   This function should render each screen pixel exactly once.
 388
 389   function rendering summary:
 390   - performance:            slower
 391   - accuracy:               higher
 392   - wall textures:          yes
 393   - different wall heights: yes
 394   - floor/ceiling textures: no
 395   - floor geometry:         yes, multilevel
 396   - ceiling geometry:       yes (optional), multilevel
 397   - rolling door:           no
 398   - camera shearing:        yes
 399   - rendering order:        left-to-right, not specifically ordered vertically
 400
 401   @param cam camera whose view to render
 402   @param floorHeightFunc function that returns floor height (in RCL_Units)
 403   @param ceilingHeightFunc same as floorHeightFunc but for ceiling, can also be
 404                            0 (no ceiling will be rendered)
 405   @param typeFunction function that says a type of square (e.g. its texture
 406                      index), can be 0 (no type in hit result)
 407   @param pixelFunc callback function to draw a single pixel on screen
 408   @param constraints constraints for each cast ray
 409 */
 410 void RCL_renderComplex(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
 411   RCL_ArrayFunction ceilingHeightFunc, RCL_ArrayFunction typeFunction,
 412   RCL_RayConstraints constraints);
 413
 414 /**
 415   Renders given camera view, with help of provided functions. This function is
 416   simpler and faster than RCL_renderComplex(...) and is meant to be rendering
 417   flat levels.
 418
 419   function rendering summary:
 420   - performance:            faster
 421   - accuracy:               lower
 422   - wall textures:          yes
 423   - different wall heights: yes
 424   - floor/ceiling textures: yes (only floor, you can mirror it for ceiling)
 425   - floor geometry:         no (just flat floor, with depth information)
 426   - ceiling geometry:       no (just flat ceiling, with depth information)
 427   - rolling door:           yes
 428   - camera shearing:        no
 429   - rendering order:        left-to-right, top-to-bottom
 430
 431   Additionally this function supports rendering rolling doors.
 432
 433   This function should render each screen pixel exactly once.
 434
 435   @param rollFunc function that for given square says its door roll in
 436          RCL_Units (0 = no roll, RCL_UNITS_PER_SQUARE = full roll right,
 437          -RCL_UNITS_PER_SQUARE = full roll left), can be zero (no rolling door,
 438          rendering should also be faster as fewer intersections will be tested)
 439 */
 440 void RCL_renderSimple(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
 441   RCL_ArrayFunction typeFunc, RCL_ArrayFunction rollFunc,
 442   RCL_RayConstraints constraints);
 443
 444 /**
 445   Function that moves given camera and makes it collide with walls and
 446   potentially also floor and ceilings. It's meant to help implement player
 447   movement.
 448
 449   @param camera camera to move
 450   @param planeOffset offset to move the camera in
 451   @param heightOffset height offset to move the camera in
 452   @param floorHeightFunc function used to retrieve the floor height
 453   @param ceilingHeightFunc function for retrieving ceiling height, can be 0
 454                            (camera won't collide with ceiling)
 455   @param computeHeight whether to compute height - if false (0), floor and
 456                        ceiling functions won't be used and the camera will
 457                        only collide horizontally with walls (good for simpler
 458                        game, also faster)
 459   @param force if true, forces to recompute collision even if position doesn't
 460                change
 461 */
 462 void RCL_moveCameraWithCollision(RCL_Camera *camera, RCL_Vector2D planeOffset,
 463   RCL_Unit heightOffset, RCL_ArrayFunction floorHeightFunc,
 464   RCL_ArrayFunction ceilingHeightFunc, int8_t computeHeight, int8_t force);
 465
 466 void RCL_initCamera(RCL_Camera *camera);
 467 void RCL_initRayConstraints(RCL_RayConstraints *constraints);
 468
 469 //=============================================================================
 470 // privates
 471
 472 #define _RCL_UNUSED(what) (void)(what);
 473
 474 // global helper variables, for precomputing stuff etc.
 475 RCL_Camera _RCL_camera;
 476 RCL_Unit _RCL_horizontalDepthStep = 0;
 477 RCL_Unit _RCL_startFloorHeight = 0;
 478 RCL_Unit _RCL_startCeil_Height = 0;
 479 RCL_Unit _RCL_camResYLimit = 0;
 480 RCL_Unit _RCL_middleRow = 0;
 481 RCL_ArrayFunction _RCL_floorFunction = 0;
 482 RCL_ArrayFunction _RCL_ceilFunction = 0;
 483 RCL_Unit _RCL_fHorizontalDepthStart = 0;
 484 RCL_Unit _RCL_cHorizontalDepthStart = 0;
 485 int16_t _RCL_cameraHeightScreen = 0;
 486 RCL_ArrayFunction _RCL_rollFunction = 0; // says door rolling
 487 RCL_Unit *_RCL_floorPixelDistances = 0;
 488
 489 #ifdef RCL_PROFILE
 490   // function call counters for profiling
 491   uint32_t profile_RCL_sqrtInt = 0;
 492   uint32_t profile_RCL_clamp = 0;
 493   uint32_t profile_RCL_cosInt = 0;
 494   uint32_t profile_RCL_angleToDirection = 0;
 495   uint32_t profile_RCL_dist = 0;
 496   uint32_t profile_RCL_len = 0;
 497   uint32_t profile_RCL_pointIsLeftOfRay = 0;
 498   uint32_t profile_RCL_castRayMultiHit = 0;
 499   uint32_t profile_RCL_castRay = 0;
 500   uint32_t profile_RCL_absVal = 0;
 501   uint32_t profile_RCL_normalize = 0;
 502   uint32_t profile_RCL_vectorsAngleCos = 0;
 503   uint32_t profile_RCL_perspectiveScale = 0;
 504   uint32_t profile_RCL_wrap = 0;
 505   uint32_t profile_RCL_divRoundDown = 0;
 506   #define RCL_profileCall(c) profile_##c += 1
 507
 508   #define printProfile() {\
 509     printf("profile:\n");\
 510     printf("  RCL_sqrtInt: %d\n",profile_RCL_sqrtInt);\
 511     printf("  RCL_clamp: %d\n",profile_RCL_clamp);\
 512     printf("  RCL_cosInt: %d\n",profile_RCL_cosInt);\
 513     printf("  RCL_angleToDirection: %d\n",profile_RCL_angleToDirection);\
 514     printf("  RCL_dist: %d\n",profile_RCL_dist);\
 515     printf("  RCL_len: %d\n",profile_RCL_len);\
 516     printf("  RCL_pointIsLeftOfRay: %d\n",profile_RCL_pointIsLeftOfRay);\
 517     printf("  RCL_castRayMultiHit : %d\n",profile_RCL_castRayMultiHit);\
 518     printf("  RCL_castRay: %d\n",profile_RCL_castRay);\
 519     printf("  RCL_normalize: %d\n",profile_RCL_normalize);\
 520     printf("  RCL_vectorsAngleCos: %d\n",profile_RCL_vectorsAngleCos);\
 521     printf("  RCL_absVal: %d\n",profile_RCL_absVal);\
 522     printf("  RCL_perspectiveScale: %d\n",profile_RCL_perspectiveScale);\
 523     printf("  RCL_wrap: %d\n",profile_RCL_wrap);\
 524     printf("  RCL_divRoundDown: %d\n",profile_RCL_divRoundDown); }
 525 #else
 526   #define RCL_profileCall(c)
 527 #endif
 528
 529 RCL_Unit RCL_clamp(RCL_Unit value, RCL_Unit valueMin, RCL_Unit valueMax)
 530 {
 531   RCL_profileCall(RCL_clamp);
 532
 533   if (value >= valueMin)
 534   {
 535     if (value <= valueMax)
 536       return value;
 537     else
 538       return valueMax;
 539   }
 540   else
 541     return valueMin;
 542 }
 543
 544 static inline RCL_Unit RCL_absVal(RCL_Unit value)
 545 {
 546   RCL_profileCall(RCL_absVal);
 547
 548   return value * (((value >= 0) << 1) - 1);
 549 }
 550
 551 /// Like mod, but behaves differently for negative values.
 552 static inline RCL_Unit RCL_wrap(RCL_Unit value, RCL_Unit mod)
 553 {
 554   RCL_profileCall(RCL_wrap);
 555   RCL_Unit cmp = value < 0;
 556   return cmp * mod + (value % mod) - cmp;
 557 }
 558
 559 /// Performs division, rounding down, NOT towards zero.
 560 static inline RCL_Unit RCL_divRoundDown(RCL_Unit value, RCL_Unit divisor)
 561 {
 562   RCL_profileCall(RCL_divRoundDown);
 563
 564   return value / divisor - ((value >= 0) ? 0 : 1);
 565 }
 566
 567 // Bhaskara's cosine approximation formula
 568 #define trigHelper(x) (((RCL_Unit) RCL_UNITS_PER_SQUARE) *\
 569   (RCL_UNITS_PER_SQUARE / 2 * RCL_UNITS_PER_SQUARE / 2 - 4 * (x) * (x)) /\
 570   (RCL_UNITS_PER_SQUARE / 2 * RCL_UNITS_PER_SQUARE / 2 + (x) * (x)))
 571
 572 #if RCL_USE_COS_LUT == 1
 573
 574   #ifdef RCL_RAYCAST_TINY
 575   const RCL_Unit cosLUT[64] =
 576   {
 577     16,14,11,6,0,-6,-11,-14,-15,-14,-11,-6,0,6,11,14
 578   };
 579   #else
 580   const RCL_Unit cosLUT[64] =
 581   {
 582     1024,1019,1004,979,946,903,851,791,724,649,568,482,391,297,199,100,0,-100,
 583     -199,-297,-391,-482,-568,-649,-724,-791,-851,-903,-946,-979,-1004,-1019,
 584     -1023,-1019,-1004,-979,-946,-903,-851,-791,-724,-649,-568,-482,-391,-297,
 585     -199,-100,0,100,199,297,391,482,568,649,724,791,851,903,946,979,1004,1019
 586   };
 587   #endif
 588
 589 #elif RCL_USE_COS_LUT == 2
 590 const RCL_Unit cosLUT[128] =
 591 {
 592   1024,1022,1019,1012,1004,993,979,964,946,925,903,878,851,822,791,758,724,
 593   687,649,609,568,526,482,437,391,344,297,248,199,150,100,50,0,-50,-100,-150,
 594   -199,-248,-297,-344,-391,-437,-482,-526,-568,-609,-649,-687,-724,-758,-791,
 595   -822,-851,-878,-903,-925,-946,-964,-979,-993,-1004,-1012,-1019,-1022,-1023,
 596   -1022,-1019,-1012,-1004,-993,-979,-964,-946,-925,-903,-878,-851,-822,-791,
 597   -758,-724,-687,-649,-609,-568,-526,-482,-437,-391,-344,-297,-248,-199,-150,
 598   -100,-50,0,50,100,150,199,248,297,344,391,437,482,526,568,609,649,687,724,
 599   758,791,822,851,878,903,925,946,964,979,993,1004,1012,1019,1022
 600 };
 601 #endif
 602
 603 RCL_Unit RCL_cosInt(RCL_Unit input)
 604 {
 605   RCL_profileCall(RCL_cosInt);
 606
 607   input = RCL_wrap(input,RCL_UNITS_PER_SQUARE);
 608
 609 #if RCL_USE_COS_LUT == 1
 610
 611   #ifdef RCL_RAYCAST_TINY
 612     return cosLUT[input];
 613   #else
 614     return cosLUT[input / 16];
 615   #endif
 616
 617 #elif RCL_USE_COS_LUT == 2
 618   return cosLUT[input / 8];
 619 #else
 620   if (input < RCL_UNITS_PER_SQUARE / 4)
 621     return trigHelper(input);
 622   else if (input < RCL_UNITS_PER_SQUARE / 2)
 623     return -1 * trigHelper(RCL_UNITS_PER_SQUARE / 2 - input);
 624   else if (input < 3 * RCL_UNITS_PER_SQUARE / 4)
 625     return -1 * trigHelper(input - RCL_UNITS_PER_SQUARE / 2);
 626   else
 627     return trigHelper(RCL_UNITS_PER_SQUARE - input);
 628 #endif
 629 }
 630
 631 #undef trigHelper
 632
 633 RCL_Unit RCL_sinInt(RCL_Unit input)
 634 {
 635   return RCL_cosInt(input - RCL_UNITS_PER_SQUARE / 4);
 636 }
 637
 638 RCL_Vector2D RCL_angleToDirection(RCL_Unit angle)
 639 {
 640   RCL_profileCall(RCL_angleToDirection);
 641
 642   RCL_Vector2D result;
 643
 644   result.x = RCL_cosInt(angle);
 645   result.y = -1 * RCL_sinInt(angle);
 646
 647   return result;
 648 }
 649
 650 uint16_t RCL_sqrtInt(RCL_Unit value)
 651 {
 652   RCL_profileCall(RCL_sqrtInt);
 653
 654 #ifdef RCL_RAYCAST_TINY
 655   uint16_t result = 0;
 656   uint16_t a = value;
 657   uint16_t b = 1u << 14;
 658 #else
 659   uint32_t result = 0;
 660   uint32_t a = value;
 661   uint32_t b = 1u << 30;
 662 #endif
 663
 664   while (b > a)
 665     b >>= 2;
 666
 667   while (b != 0)
 668   {
 669     if (a >= result + b)
 670     {
 671       a -= result + b;
 672       result = result +  2 * b;
 673     }
 674
 675     b >>= 2;
 676     result >>= 1;
 677   }
 678
 679   return result;
 680 }
 681
 682 RCL_Unit RCL_dist(RCL_Vector2D p1, RCL_Vector2D p2)
 683 {
 684   RCL_profileCall(RCL_dist);
 685
 686   RCL_Unit dx = p2.x - p1.x;
 687   RCL_Unit dy = p2.y - p1.y;
 688
 689 #if RCL_USE_DIST_APPROX == 2
 690   // octagonal approximation
 691
 692   dx = RCL_absVal(dx);
 693   dy = RCL_absVal(dy);
 694
 695   return dy > dx ? dx / 2 + dy : dy / 2 + dx;
 696 #elif RCL_USE_DIST_APPROX == 1
 697   // more accurate approximation
 698
 699   RCL_Unit a, b, result;
 700
 701   dx = ((dx < 0) * 2 - 1) * dx;
 702   dy = ((dy < 0) * 2 - 1) * dy;
 703
 704   if (dx < dy)
 705   {
 706      a = dy;
 707      b = dx;
 708   }
 709   else
 710   {
 711      a = dx;
 712      b = dy;
 713   }
 714
 715   result = a + (44 * b) / 102;
 716
 717   if (a < (b << 4))
 718     result -= (5 * a) / 128;
 719
 720   return result;
 721 #else
 722   dx = dx * dx;
 723   dy = dy * dy;
 724
 725   return RCL_sqrtInt((RCL_Unit) (dx + dy));
 726 #endif
 727 }
 728
 729 RCL_Unit RCL_len(RCL_Vector2D v)
 730 {
 731   RCL_profileCall(RCL_len);
 732
 733   RCL_Vector2D zero;
 734   zero.x = 0;
 735   zero.y = 0;
 736
 737   return RCL_dist(zero,v);
 738 }
 739
 740 static inline int8_t RCL_pointIsLeftOfRay(RCL_Vector2D point, RCL_Ray ray)
 741 {
 742   RCL_profileCall(RCL_pointIsLeftOfRay);
 743
 744   RCL_Unit dX    = point.x - ray.start.x;
 745   RCL_Unit dY    = point.y - ray.start.y;
 746   return (ray.direction.x * dY - ray.direction.y * dX) > 0;
 747          // ^ Z component of cross-product
 748 }
 749
 750 void RCL_castRayMultiHit(RCL_Ray ray, RCL_ArrayFunction arrayFunc,
 751   RCL_ArrayFunction typeFunc, RCL_HitResult *hitResults,
 752   uint16_t *hitResultsLen, RCL_RayConstraints constraints)
 753 {
 754   RCL_profileCall(RCL_castRayMultiHit);
 755
 756   RCL_Vector2D currentPos = ray.start;
 757   RCL_Vector2D currentSquare;
 758
 759   currentSquare.x = RCL_divRoundDown(ray.start.x,RCL_UNITS_PER_SQUARE);
 760   currentSquare.y = RCL_divRoundDown(ray.start.y,RCL_UNITS_PER_SQUARE);
 761
 762   *hitResultsLen = 0;
 763
 764   RCL_Unit squareType = arrayFunc(currentSquare.x,currentSquare.y);
 765
 766   // DDA variables
 767   RCL_Vector2D nextSideDist; // dist. from start to the next side in given axis
 768   RCL_Vector2D delta;
 769   RCL_Vector2D step;         // -1 or 1 for each axis
 770   int8_t stepHorizontal = 0; // whether the last step was hor. or vert.
 771
 772   nextSideDist.x = 0;
 773   nextSideDist.y = 0;
 774
 775   RCL_Unit dirVecLengthNorm = RCL_len(ray.direction) * RCL_UNITS_PER_SQUARE;
 776
 777   delta.x = RCL_absVal(dirVecLengthNorm / RCL_nonZero(ray.direction.x));
 778   delta.y = RCL_absVal(dirVecLengthNorm / RCL_nonZero(ray.direction.y));
 779
 780   // init DDA
 781
 782   if (ray.direction.x < 0)
 783   {
 784     step.x = -1;
 785     nextSideDist.x = (RCL_wrap(ray.start.x,RCL_UNITS_PER_SQUARE) * delta.x) /
 786                        RCL_UNITS_PER_SQUARE;
 787   }
 788   else
 789   {
 790     step.x = 1;
 791     nextSideDist.x =
 792       ((RCL_wrap(RCL_UNITS_PER_SQUARE - ray.start.x,RCL_UNITS_PER_SQUARE)) *
 793         delta.x) / RCL_UNITS_PER_SQUARE;
 794   }
 795
 796   if (ray.direction.y < 0)
 797   {
 798     step.y = -1;
 799     nextSideDist.y = (RCL_wrap(ray.start.y,RCL_UNITS_PER_SQUARE) * delta.y) /
 800                        RCL_UNITS_PER_SQUARE;
 801   }
 802   else
 803   {
 804     step.y = 1;
 805     nextSideDist.y =
 806       ((RCL_wrap(RCL_UNITS_PER_SQUARE - ray.start.y,RCL_UNITS_PER_SQUARE)) *
 807         delta.y) / RCL_UNITS_PER_SQUARE;
 808   }
 809
 810   // DDA loop
 811
 812   #define RECIP_SCALE 65536
 813
 814   RCL_Unit rayDirXRecip = RECIP_SCALE / RCL_nonZero(ray.direction.x);
 815   RCL_Unit rayDirYRecip = RECIP_SCALE / RCL_nonZero(ray.direction.y);
 816   // ^ we precompute reciprocals to avoid divisions in the loop
 817
 818   for (uint16_t i = 0; i < constraints.maxSteps; ++i)
 819   {
 820     RCL_Unit currentType = arrayFunc(currentSquare.x,currentSquare.y);
 821
 822     if (RCL_unlikely(currentType != squareType))
 823     {
 824       // collision
 825
 826       RCL_HitResult h;
 827
 828       h.arrayValue = currentType;
 829       h.doorRoll = 0;
 830       h.position = currentPos;
 831       h.square   = currentSquare;
 832
 833       if (stepHorizontal)
 834       {
 835         h.position.x = currentSquare.x * RCL_UNITS_PER_SQUARE;
 836         h.direction = 3;
 837
 838         if (step.x == -1)
 839         {
 840           h.direction = 1;
 841           h.position.x += RCL_UNITS_PER_SQUARE;
 842         }
 843
 844         RCL_Unit diff = h.position.x - ray.start.x;
 845
 846         h.position.y = // avoid division by multiplying with reciprocal
 847           ray.start.y + ((ray.direction.y * diff) * rayDirXRecip) / RECIP_SCALE;
 848
 849 #if RCL_RECTILINEAR
 850         /* Here we compute the fish eye corrected distance (perpendicular to
 851         the projection plane) as the Euclidean distance divided by the length
 852         of the ray direction vector. This can be computed without actually
 853         computing Euclidean distances as a hypothenuse A (distance) divided
 854         by hypothenuse B (length) is equal to leg A (distance along one axis)
 855         divided by leg B (length along the same axis). */
 856
 857         h.distance =
 858           (((h.position.x - ray.start.x) / 4) *
 859           RCL_UNITS_PER_SQUARE * rayDirXRecip)
 860           / (RECIP_SCALE / 4);
 861
 862           // ^ / 4 is here to prevent overflow
 863 #endif
 864       }
 865       else
 866       {
 867         h.position.y = currentSquare.y * RCL_UNITS_PER_SQUARE;
 868         h.direction = 2;
 869
 870         if (step.y == -1)
 871         {
 872           h.direction = 0;
 873           h.position.y += RCL_UNITS_PER_SQUARE;
 874         }
 875
 876         RCL_Unit diff = h.position.y - ray.start.y;
 877
 878         h.position.x =
 879           ray.start.x + ((ray.direction.x * diff) * rayDirYRecip) / RECIP_SCALE;
 880
 881 #if RCL_RECTILINEAR
 882         h.distance =
 883           (((h.position.y - ray.start.y) / 4) *
 884           RCL_UNITS_PER_SQUARE * rayDirYRecip)
 885           / (RECIP_SCALE / 4);
 886
 887           // ^ / 4 is here to prevent overflow
 888 #endif
 889       }
 890
 891 #if !RCL_RECTILINEAR
 892       h.distance = RCL_dist(h.position,ray.start);
 893 #endif
 894
 895       if (typeFunc != 0)
 896         h.type = typeFunc(currentSquare.x,currentSquare.y);
 897
 898 #if RCL_COMPUTE_WALL_TEXCOORDS == 1
 899       switch (h.direction)
 900       {
 901         case 0: h.textureCoord =
 902           RCL_wrap(-1 * h.position.x,RCL_UNITS_PER_SQUARE); break;
 903
 904         case 1: h.textureCoord =
 905           RCL_wrap(h.position.y,RCL_UNITS_PER_SQUARE); break;
 906
 907         case 2: h.textureCoord =
 908           RCL_wrap(h.position.x,RCL_UNITS_PER_SQUARE); break;
 909
 910         case 3: h.textureCoord =
 911           RCL_wrap(-1 * h.position.y,RCL_UNITS_PER_SQUARE); break;
 912
 913         default: h.textureCoord = 0; break;
 914       }
 915
 916       if (_RCL_rollFunction != 0)
 917       {
 918         h.doorRoll = _RCL_rollFunction(currentSquare.x,currentSquare.y);
 919
 920         if (h.direction == 0 || h.direction == 1)
 921           h.doorRoll *= -1;
 922       }
 923
 924 #else
 925       h.textureCoord = 0;
 926 #endif
 927
 928       hitResults[*hitResultsLen] = h;
 929
 930       *hitResultsLen += 1;
 931
 932       squareType = currentType;
 933
 934       if (*hitResultsLen >= constraints.maxHits)
 935         break;
 936     }
 937
 938     // DDA step
 939
 940     if (nextSideDist.x < nextSideDist.y)
 941     {
 942       nextSideDist.x += delta.x;
 943       currentSquare.x += step.x;
 944       stepHorizontal = 1;
 945     }
 946     else
 947     {
 948       nextSideDist.y += delta.y;
 949       currentSquare.y += step.y;
 950       stepHorizontal = 0;
 951     }
 952   }
 953 }
 954
 955 RCL_HitResult RCL_castRay(RCL_Ray ray, RCL_ArrayFunction arrayFunc)
 956 {
 957   RCL_profileCall(RCL_castRay);
 958
 959   RCL_HitResult result;
 960   uint16_t RCL_len;
 961   RCL_RayConstraints c;
 962
 963   c.maxSteps = 1000;
 964   c.maxHits = 1;
 965
 966   RCL_castRayMultiHit(ray,arrayFunc,0,&result,&RCL_len,c);
 967
 968   if (RCL_len == 0)
 969     result.distance = -1;
 970
 971   return result;
 972 }
 973
 974 void RCL_castRaysMultiHit(RCL_Camera cam, RCL_ArrayFunction arrayFunc,
 975   RCL_ArrayFunction typeFunction, RCL_ColumnFunction columnFunc,
 976   RCL_RayConstraints constraints)
 977 {
 978   RCL_Vector2D dir1 =
 979     RCL_angleToDirection(cam.direction - RCL_HORIZONTAL_FOV_HALF);
 980
 981   RCL_Vector2D dir2 =
 982     RCL_angleToDirection(cam.direction + RCL_HORIZONTAL_FOV_HALF);
 983
 984   RCL_Unit dX = dir2.x - dir1.x;
 985   RCL_Unit dY = dir2.y - dir1.y;
 986
 987   RCL_HitResult hits[constraints.maxHits];
 988   uint16_t hitCount;
 989
 990   RCL_Ray r;
 991   r.start = cam.position;
 992
 993   RCL_Unit currentDX = 0;
 994   RCL_Unit currentDY = 0;
 995
 996   for (int16_t i = 0; i < cam.resolution.x; ++i)
 997   {
 998     /* Here by linearly interpolating the direction vector its length changes,
 999     which in result achieves correcting the fish eye effect (computing
1000     perpendicular distance). */
1001
1002     r.direction.x = dir1.x + currentDX / cam.resolution.x;
1003     r.direction.y = dir1.y + currentDY / cam.resolution.x;
1004
1005     RCL_castRayMultiHit(r,arrayFunc,typeFunction,hits,&hitCount,constraints);
1006
1007     columnFunc(hits,hitCount,i,r);
1008
1009     currentDX += dX;
1010     currentDY += dY;
1011   }
1012 }
1013
1014 /**
1015   Helper function that determines intersection with both ceiling and floor.
1016 */
1017 RCL_Unit _RCL_floorCeilFunction(int16_t x, int16_t y)
1018 {
1019   RCL_Unit f = _RCL_floorFunction(x,y);
1020
1021   if (_RCL_ceilFunction == 0)
1022     return f;
1023
1024   RCL_Unit c = _RCL_ceilFunction(x,y);
1025
1026 #ifndef RCL_RAYCAST_TINY
1027   return ((f & 0x0000ffff) << 16) | (c & 0x0000ffff);
1028 #else
1029   return ((f & 0x00ff) << 8) | (c & 0x00ff);
1030 #endif
1031 }
1032
1033 RCL_Unit _floorHeightNotZeroFunction(int16_t x, int16_t y)
1034 {
1035   return _RCL_floorFunction(x,y) == 0 ? 0 :
1036     RCL_nonZero((x & 0x00FF) | ((y & 0x00FF) << 8));
1037     // ^ this makes collisions between all squares - needed for rolling doors
1038 }
1039
1040 RCL_Unit RCL_adjustDistance(RCL_Unit distance, RCL_Camera *camera,
1041   RCL_Ray *ray)
1042 {
1043   /* FIXME/TODO: The adjusted (=orthogonal, camera-space) distance could
1044      possibly be computed more efficiently by not computing Euclidean
1045      distance at all, but rather compute the distance of the collision
1046      point from the projection plane (line). */
1047
1048   RCL_Unit result =
1049     (distance *
1050      RCL_vectorsAngleCos(RCL_angleToDirection(camera->direction),
1051      ray->direction)) / RCL_UNITS_PER_SQUARE;
1052
1053   return RCL_nonZero(result);
1054       // ^ prevent division by zero
1055 }
1056
1057 /// Helper for drawing floor or ceiling. Returns the last drawn pixel position.
1058 static inline int16_t _RCL_drawHorizontalColumn(
1059   RCL_Unit yCurrent,
1060   RCL_Unit yTo,
1061   RCL_Unit limit1, // TODO: int16_t?
1062   RCL_Unit limit2,
1063   RCL_Unit verticalOffset,
1064   int16_t increment,
1065   int8_t computeDepth,
1066   int8_t computeCoords,
1067   int16_t depthIncrementMultiplier,
1068   RCL_Ray *ray,
1069   RCL_PixelInfo *pixelInfo
1070 )
1071 {
1072   _RCL_UNUSED(ray);
1073
1074   RCL_Unit depthIncrement;
1075   RCL_Unit dx;
1076   RCL_Unit dy;
1077
1078   pixelInfo->isWall = 0;
1079
1080   int16_t limit = RCL_clamp(yTo,limit1,limit2);
1081
1082   RCL_Unit depth = 0; /* TODO: this is for clamping depth to 0 so that we don't
1083                          have negative depths, but we should do it more
1084                          elegantly and efficiently */
1085
1086   _RCL_UNUSED(depth);
1087
1088   /* for performance reasons have different version of the critical loop
1089      to be able to branch early */
1090   #define loop(doDepth,doCoords)\
1091   {\
1092     if (doDepth) /*constant condition - compiler should optimize it out*/\
1093     {\
1094       depth = pixelInfo->depth + RCL_absVal(verticalOffset) *\
1095         RCL_VERTICAL_DEPTH_MULTIPLY;\
1096       depthIncrement = depthIncrementMultiplier *\
1097         _RCL_horizontalDepthStep;\
1098     }\
1099     if (doCoords) /*constant condition - compiler should optimize it out*/\
1100     {\
1101       dx = pixelInfo->hit.position.x - _RCL_camera.position.x;\
1102       dy = pixelInfo->hit.position.y - _RCL_camera.position.y;\
1103     }\
1104     for (int16_t i = yCurrent + increment;\
1105          increment == -1 ? i >= limit : i <= limit; /* TODO: is efficient? */\
1106          i += increment)\
1107     {\
1108       pixelInfo->position.y = i;\
1109       if (doDepth)  /*constant condition - compiler should optimize it out*/\
1110       {\
1111         depth += depthIncrement;\
1112         pixelInfo->depth = RCL_zeroClamp(depth); \
1113         /* ^ int comparison is fast, it is not braching! (= test instr.) */\
1114       }\
1115       if (doCoords) /*constant condition - compiler should optimize it out*/\
1116       {\
1117         RCL_Unit d = _RCL_floorPixelDistances[i];\
1118         RCL_Unit d2 = RCL_nonZero(pixelInfo->hit.distance);\
1119         pixelInfo->texCoords.x =\
1120           _RCL_camera.position.x + ((d * dx) / d2);\
1121         pixelInfo->texCoords.y =\
1122           _RCL_camera.position.y + ((d * dy) / d2);\
1123       }\
1124       RCL_PIXEL_FUNCTION(pixelInfo);\
1125     }\
1126   }
1127
1128   if (computeDepth) // branch early
1129   {
1130     if (!computeCoords)
1131       loop(1,0)
1132     else
1133       loop(1,1)
1134   }
1135   else
1136   {
1137     if (!computeCoords)
1138       loop(0,0)
1139     else
1140       loop(1,1)
1141   }
1142
1143   #undef loop
1144
1145   return limit;
1146 }
1147
1148 /// Helper for drawing walls. Returns the last drawn pixel position.
1149 static inline int16_t _RCL_drawWall(
1150   RCL_Unit yCurrent,
1151   RCL_Unit yFrom,
1152   RCL_Unit yTo,
1153   RCL_Unit limit1, // TODO: int16_t?
1154   RCL_Unit limit2,
1155   RCL_Unit height,
1156   int16_t increment,
1157   RCL_PixelInfo *pixelInfo
1158   )
1159 {
1160   _RCL_UNUSED(height)
1161
1162   height = RCL_absVal(height);
1163
1164   pixelInfo->isWall = 1;
1165
1166   RCL_Unit limit = RCL_clamp(yTo,limit1,limit2);
1167
1168   RCL_Unit wallLength = RCL_nonZero(RCL_absVal(yTo - yFrom - 1));
1169
1170   RCL_Unit wallPosition = RCL_absVal(yFrom - yCurrent) - increment;
1171
1172   RCL_Unit heightScaled = height * RCL_TEXTURE_INTERPOLATION_SCALE;
1173   _RCL_UNUSED(heightScaled);
1174
1175   RCL_Unit coordStepScaled = RCL_COMPUTE_WALL_TEXCOORDS ?
1176 #if RCL_TEXTURE_VERTICAL_STRETCH == 1
1177     ((RCL_UNITS_PER_SQUARE * RCL_TEXTURE_INTERPOLATION_SCALE) / wallLength)
1178 #else
1179     (heightScaled / wallLength)
1180 #endif
1181     : 0;
1182
1183   pixelInfo->texCoords.y = RCL_COMPUTE_WALL_TEXCOORDS ?
1184     (wallPosition * coordStepScaled) : 0;
1185
1186   if (increment < 0)
1187   {
1188     coordStepScaled *= -1;
1189     pixelInfo->texCoords.y =
1190 #if RCL_TEXTURE_VERTICAL_STRETCH == 1
1191       (RCL_UNITS_PER_SQUARE * RCL_TEXTURE_INTERPOLATION_SCALE)
1192       - pixelInfo->texCoords.y;
1193 #else
1194       heightScaled - pixelInfo->texCoords.y;
1195 #endif
1196   }
1197   else
1198   {
1199     // with floor wall, don't start under 0
1200     pixelInfo->texCoords.y = RCL_zeroClamp(pixelInfo->texCoords.y);
1201   }
1202
1203   RCL_Unit textureCoordScaled = pixelInfo->texCoords.y;
1204
1205   for (RCL_Unit i = yCurrent + increment;
1206        increment == -1 ? i >= limit : i <= limit; // TODO: is efficient?
1207        i += increment)
1208   {
1209     pixelInfo->position.y = i;
1210
1211 #if RCL_COMPUTE_WALL_TEXCOORDS == 1
1212     pixelInfo->texCoords.y =
1213       textureCoordScaled / RCL_TEXTURE_INTERPOLATION_SCALE;
1214
1215     textureCoordScaled += coordStepScaled;
1216 #endif
1217
1218     RCL_PIXEL_FUNCTION(pixelInfo);
1219   }
1220
1221   return limit;
1222 }
1223
1224 /// Fills a RCL_HitResult struct with info for a hit at infinity.
1225 static inline void _RCL_makeInfiniteHit(RCL_HitResult *hit, RCL_Ray *ray)
1226 {
1227   hit->distance = RCL_UNITS_PER_SQUARE * RCL_UNITS_PER_SQUARE;
1228   /* ^ horizon is at infinity, but we can't use too big infinity
1229        (RCL_INFINITY) because it would overflow in the following mult. */
1230   hit->position.x = (ray->direction.x * hit->distance) / RCL_UNITS_PER_SQUARE;
1231   hit->position.y = (ray->direction.y * hit->distance) / RCL_UNITS_PER_SQUARE;
1232
1233   hit->direction = 0;
1234   hit->textureCoord = 0;
1235   hit->arrayValue = 0;
1236   hit->doorRoll = 0;
1237   hit->type = 0;
1238 }
1239
1240 void _RCL_columnFunctionComplex(RCL_HitResult *hits, uint16_t hitCount, uint16_t x,
1241   RCL_Ray ray)
1242 {
1243   // last written Y position, can never go backwards
1244   RCL_Unit fPosY = _RCL_camera.resolution.y;
1245   RCL_Unit cPosY = -1;
1246
1247   // world coordinates (relative to camera height though)
1248   RCL_Unit fZ1World = _RCL_startFloorHeight;
1249   RCL_Unit cZ1World = _RCL_startCeil_Height;
1250
1251   RCL_PixelInfo p;
1252   p.position.x = x;
1253   p.height = 0;
1254   p.wallHeight = 0;
1255   p.texCoords.x = 0;
1256   p.texCoords.y = 0;
1257
1258   // we'll be simulatenously drawing the floor and the ceiling now
1259   for (RCL_Unit j = 0; j <= hitCount; ++j)
1260   {                    // ^ = add extra iteration for horizon plane
1261     int8_t drawingHorizon = j == hitCount;
1262
1263     RCL_HitResult hit;
1264     RCL_Unit distance = 1;
1265
1266     RCL_Unit fWallHeight = 0, cWallHeight = 0;
1267     RCL_Unit fZ2World = 0,    cZ2World = 0;
1268     RCL_Unit fZ1Screen = 0,   cZ1Screen = 0;
1269     RCL_Unit fZ2Screen = 0,   cZ2Screen = 0;
1270
1271     if (!drawingHorizon)
1272     {
1273       hit = hits[j];
1274       distance = RCL_nonZero(hit.distance);
1275       p.hit = hit;
1276
1277       fWallHeight = _RCL_floorFunction(hit.square.x,hit.square.y);
1278       fZ2World = fWallHeight - _RCL_camera.height;
1279       fZ1Screen = _RCL_middleRow - RCL_perspectiveScale(
1280         (fZ1World * _RCL_camera.resolution.y) /
1281         RCL_UNITS_PER_SQUARE,distance);
1282       fZ2Screen = _RCL_middleRow - RCL_perspectiveScale(
1283         (fZ2World * _RCL_camera.resolution.y) /
1284         RCL_UNITS_PER_SQUARE,distance);
1285
1286       if (_RCL_ceilFunction != 0)
1287       {
1288         cWallHeight = _RCL_ceilFunction(hit.square.x,hit.square.y);
1289         cZ2World = cWallHeight - _RCL_camera.height;
1290         cZ1Screen = _RCL_middleRow - RCL_perspectiveScale(
1291           (cZ1World * _RCL_camera.resolution.y) /
1292           RCL_UNITS_PER_SQUARE,distance);
1293         cZ2Screen = _RCL_middleRow - RCL_perspectiveScale(
1294           (cZ2World * _RCL_camera.resolution.y) /
1295           RCL_UNITS_PER_SQUARE,distance);
1296       }
1297     }
1298     else
1299     {
1300       fZ1Screen = _RCL_middleRow;
1301       cZ1Screen = _RCL_middleRow + 1;
1302       _RCL_makeInfiniteHit(&p.hit,&ray);
1303     }
1304
1305     RCL_Unit limit;
1306
1307     p.isWall = 0;
1308     p.isHorizon = drawingHorizon;
1309
1310     // draw floor until wall
1311     p.isFloor = 1;
1312     p.height = fZ1World + _RCL_camera.height;
1313     p.wallHeight = 0;
1314
1315 #if RCL_COMPUTE_FLOOR_DEPTH == 1
1316     p.depth = (_RCL_fHorizontalDepthStart - fPosY) * _RCL_horizontalDepthStep;
1317 #else
1318     p.depth = 0;
1319 #endif
1320
1321     limit = _RCL_drawHorizontalColumn(fPosY,fZ1Screen,cPosY + 1,
1322      _RCL_camera.resolution.y,fZ1World,-1,RCL_COMPUTE_FLOOR_DEPTH,
1323      // ^ purposfully allow outside screen bounds
1324        RCL_COMPUTE_FLOOR_TEXCOORDS && p.height == RCL_FLOOR_TEXCOORDS_HEIGHT,
1325        1,&ray,&p);
1326
1327     if (fPosY > limit)
1328       fPosY = limit;
1329
1330     if (_RCL_ceilFunction != 0 || drawingHorizon)
1331     {
1332       // draw ceiling until wall
1333       p.isFloor = 0;
1334       p.height = cZ1World + _RCL_camera.height;
1335
1336 #if RCL_COMPUTE_CEILING_DEPTH == 1
1337       p.depth = (cPosY - _RCL_cHorizontalDepthStart) *
1338         _RCL_horizontalDepthStep;
1339 #endif
1340
1341       limit = _RCL_drawHorizontalColumn(cPosY,cZ1Screen,
1342         -1,fPosY - 1,cZ1World,1,RCL_COMPUTE_CEILING_DEPTH,0,1,&ray,&p);
1343       // ^ purposfully allow outside screen bounds here
1344
1345       if (cPosY < limit)
1346         cPosY = limit;
1347     }
1348
1349     if (!drawingHorizon) // don't draw walls for horizon plane
1350     {
1351       p.isWall = 1;
1352       p.depth = distance;
1353       p.isFloor = 1;
1354       p.texCoords.x = hit.textureCoord;
1355       p.height = fZ1World + _RCL_camera.height;
1356       p.wallHeight = fWallHeight;
1357
1358       // draw floor wall
1359
1360       if (fPosY > 0)  // still pixels left?
1361       {
1362         p.isFloor = 1;
1363
1364         limit = _RCL_drawWall(fPosY,fZ1Screen,fZ2Screen,cPosY + 1,
1365                   _RCL_camera.resolution.y,
1366                   // ^ purposfully allow outside screen bounds here
1367 #if RCL_TEXTURE_VERTICAL_STRETCH == 1
1368                   RCL_UNITS_PER_SQUARE
1369 #else
1370                   fZ2World - fZ1World
1371 #endif
1372                   ,-1,&p);
1373
1374
1375         if (fPosY > limit)
1376           fPosY = limit;
1377
1378         fZ1World = fZ2World; // for the next iteration
1379       }               // ^ purposfully allow outside screen bounds here
1380
1381       // draw ceiling wall
1382
1383       if (_RCL_ceilFunction != 0 && cPosY < _RCL_camResYLimit) // pixels left?
1384       {
1385         p.isFloor = 0;
1386         p.height = cZ1World + _RCL_camera.height;
1387         p.wallHeight = cWallHeight;
1388
1389         limit = _RCL_drawWall(cPosY,cZ1Screen,cZ2Screen,
1390                   -1,fPosY - 1,
1391                 // ^ puposfully allow outside screen bounds here
1392 #if RCL_TEXTURE_VERTICAL_STRETCH == 1
1393                   RCL_UNITS_PER_SQUARE
1394 #else
1395                   cZ1World - cZ2World
1396 #endif
1397                   ,1,&p);
1398
1399         if (cPosY < limit)
1400           cPosY = limit;
1401
1402         cZ1World = cZ2World; // for the next iteration
1403       }              // ^ puposfully allow outside screen bounds here
1404     }
1405   }
1406 }
1407
1408 void _RCL_columnFunctionSimple(RCL_HitResult *hits, uint16_t hitCount,
1409   uint16_t x, RCL_Ray ray)
1410 {
1411   RCL_Unit y = 0;
1412   RCL_Unit wallHeightScreen = 0;
1413   RCL_Unit wallStart = _RCL_middleRow;
1414   RCL_Unit heightOffset = 0;
1415
1416   RCL_Unit dist = 1;
1417
1418   RCL_PixelInfo p;
1419   p.position.x = x;
1420   p.wallHeight = RCL_UNITS_PER_SQUARE;
1421
1422   if (hitCount > 0)
1423   {
1424     RCL_HitResult hit = hits[0];
1425
1426     uint8_t goOn = 1;
1427
1428     if (_RCL_rollFunction != 0 && RCL_COMPUTE_WALL_TEXCOORDS == 1)
1429     {
1430       if (hit.arrayValue == 0)
1431       {
1432         // standing inside door square, looking out => move to the next hit
1433
1434         if (hitCount > 1)
1435           hit = hits[1];
1436         else
1437           goOn = 0;
1438       }
1439       else
1440       {
1441         // normal hit, check the door roll
1442
1443         RCL_Unit texCoordMod = hit.textureCoord % RCL_UNITS_PER_SQUARE;
1444
1445         int8_t unrolled = hit.doorRoll >= 0 ?
1446           (hit.doorRoll > texCoordMod) :
1447           (texCoordMod > RCL_UNITS_PER_SQUARE + hit.doorRoll);
1448
1449         if (unrolled)
1450         {
1451           goOn = 0;
1452
1453           if (hitCount > 1) /* should probably always be true (hit on square
1454                                exit) */
1455           {
1456             if (hit.direction % 2 != hits[1].direction % 2)
1457             {
1458               // hit on the inner side
1459               hit = hits[1];
1460               goOn = 1;
1461             }
1462             else if (hitCount > 2)
1463             {
1464               // hit on the opposite side
1465               hit = hits[2];
1466               goOn = 1;
1467             }
1468           }
1469         }
1470       }
1471     }
1472
1473     p.hit = hit;
1474
1475     if (goOn)
1476     {
1477       dist = hit.distance;
1478
1479       int16_t wallHeightWorld = _RCL_floorFunction(hit.square.x,hit.square.y);
1480
1481       wallHeightScreen = RCL_perspectiveScale((wallHeightWorld *
1482         _RCL_camera.resolution.y) / RCL_UNITS_PER_SQUARE,dist);
1483
1484       int16_t RCL_normalizedWallHeight = wallHeightWorld != 0 ?
1485         ((RCL_UNITS_PER_SQUARE * wallHeightScreen) / wallHeightWorld) : 0;
1486
1487       heightOffset = RCL_perspectiveScale(_RCL_cameraHeightScreen,dist);
1488
1489       wallStart = _RCL_middleRow - wallHeightScreen + heightOffset +
1490                   RCL_normalizedWallHeight;
1491     }
1492   }
1493   else
1494   {
1495     _RCL_makeInfiniteHit(&p.hit,&ray);
1496   }
1497
1498   // draw ceiling
1499
1500   p.isWall = 0;
1501   p.isFloor = 0;
1502   p.isHorizon = 1;
1503   p.depth = 1;
1504   p.height = RCL_UNITS_PER_SQUARE;
1505
1506   y = _RCL_drawHorizontalColumn(-1,wallStart,-1,_RCL_middleRow,_RCL_camera.height,1,
1507     RCL_COMPUTE_CEILING_DEPTH,0,1,&ray,&p);
1508
1509   // draw wall
1510
1511   p.isWall = 1;
1512   p.isFloor = 1;
1513   p.depth = dist;
1514   p.height = 0;
1515
1516 #if RCL_ROLL_TEXTURE_COORDS == 1 && RCL_COMPUTE_WALL_TEXCOORDS == 1
1517   p.hit.textureCoord -= p.hit.doorRoll;
1518 #endif
1519
1520   p.texCoords.x = p.hit.textureCoord;
1521   p.texCoords.y = 0;
1522
1523   RCL_Unit limit = _RCL_drawWall(y,wallStart,wallStart + wallHeightScreen - 1,
1524     -1,_RCL_camResYLimit,p.hit.arrayValue,1,&p);
1525
1526   y = RCL_max(y,limit); // take max, in case no wall was drawn
1527   y = RCL_max(y,wallStart);
1528
1529   // draw floor
1530
1531   p.isWall = 0;
1532
1533 #if RCL_COMPUTE_FLOOR_DEPTH == 1
1534   p.depth = (_RCL_camera.resolution.y - y) * _RCL_horizontalDepthStep + 1;
1535 #endif
1536
1537   _RCL_drawHorizontalColumn(y,_RCL_camResYLimit,-1,_RCL_camResYLimit,
1538     _RCL_camera.height,1,RCL_COMPUTE_FLOOR_DEPTH,RCL_COMPUTE_FLOOR_TEXCOORDS,
1539     -1,&ray,&p);
1540 }
1541
1542 /**
1543   Precomputes a distance from camera to the floor at each screen row into an
1544   array (must be preallocated with sufficient (camera.resolution.y) length).
1545 */
1546 static inline void _RCL_precomputeFloorDistances(RCL_Camera camera,
1547   RCL_Unit *dest, uint16_t startIndex)
1548 {
1549   RCL_Unit camHeightScreenSize =
1550     (camera.height * camera.resolution.y) / RCL_UNITS_PER_SQUARE;
1551
1552   for (uint16_t i = startIndex; i < camera.resolution.y; ++i)
1553     dest[i] = RCL_perspectiveScaleInverse(camHeightScreenSize,
1554              RCL_absVal(i - _RCL_middleRow));
1555 }
1556
1557 void RCL_renderComplex(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
1558   RCL_ArrayFunction ceilingHeightFunc, RCL_ArrayFunction typeFunction,
1559   RCL_RayConstraints constraints)
1560 {
1561   _RCL_floorFunction = floorHeightFunc;
1562   _RCL_ceilFunction = ceilingHeightFunc;
1563   _RCL_camera = cam;
1564   _RCL_camResYLimit = cam.resolution.y - 1;
1565
1566   uint16_t halfResY = cam.resolution.y / 2;
1567
1568   _RCL_middleRow = halfResY + cam.shear;
1569
1570   _RCL_fHorizontalDepthStart = _RCL_middleRow + halfResY;
1571   _RCL_cHorizontalDepthStart = _RCL_middleRow - halfResY;
1572
1573   _RCL_startFloorHeight = floorHeightFunc(
1574     RCL_divRoundDown(cam.position.x,RCL_UNITS_PER_SQUARE),
1575     RCL_divRoundDown(cam.position.y,RCL_UNITS_PER_SQUARE)) -1 * cam.height;
1576
1577   _RCL_startCeil_Height =
1578     ceilingHeightFunc != 0 ?
1579       ceilingHeightFunc(
1580         RCL_divRoundDown(cam.position.x,RCL_UNITS_PER_SQUARE),
1581         RCL_divRoundDown(cam.position.y,RCL_UNITS_PER_SQUARE)) -1 * cam.height
1582       : RCL_INFINITY;
1583
1584   _RCL_horizontalDepthStep = RCL_HORIZON_DEPTH / cam.resolution.y;
1585
1586 #if RCL_COMPUTE_FLOOR_TEXCOORDS == 1
1587   RCL_Unit floorPixelDistances[cam.resolution.y];
1588   _RCL_precomputeFloorDistances(cam,floorPixelDistances,0);
1589   _RCL_floorPixelDistances = floorPixelDistances; // pass to column function
1590 #endif
1591
1592   RCL_castRaysMultiHit(cam,_RCL_floorCeilFunction,typeFunction,
1593     _RCL_columnFunctionComplex,constraints);
1594 }
1595
1596 void RCL_renderSimple(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc,
1597   RCL_ArrayFunction typeFunc, RCL_ArrayFunction rollFunc,
1598   RCL_RayConstraints constraints)
1599 {
1600   _RCL_floorFunction = floorHeightFunc;
1601   _RCL_camera = cam;
1602   _RCL_camResYLimit = cam.resolution.y - 1;
1603   _RCL_middleRow = cam.resolution.y / 2;
1604   _RCL_rollFunction = rollFunc;
1605
1606   _RCL_cameraHeightScreen =
1607     (_RCL_camera.resolution.y * (_RCL_camera.height - RCL_UNITS_PER_SQUARE)) /
1608     RCL_UNITS_PER_SQUARE;
1609
1610   _RCL_horizontalDepthStep = RCL_HORIZON_DEPTH / cam.resolution.y;
1611
1612   constraints.maxHits =
1613     _RCL_rollFunction == 0 ?
1614       1 : // no door => 1 hit is enough
1615       3;  // for correctly rendering rolling doors we'll need 3 hits (NOT 2)
1616
1617 #if RCL_COMPUTE_FLOOR_TEXCOORDS == 1
1618   RCL_Unit floorPixelDistances[cam.resolution.y];
1619   _RCL_precomputeFloorDistances(cam,floorPixelDistances,_RCL_middleRow);
1620   _RCL_floorPixelDistances = floorPixelDistances; // pass to column function
1621 #endif
1622
1623   RCL_castRaysMultiHit(cam,_floorHeightNotZeroFunction,typeFunc,
1624     _RCL_columnFunctionSimple, constraints);
1625
1626 #if RCL_COMPUTE_FLOOR_TEXCOORDS == 1
1627   _RCL_floorPixelDistances = 0;
1628 #endif
1629 }
1630
1631 RCL_Vector2D RCL_normalize(RCL_Vector2D v)
1632 {
1633   RCL_profileCall(RCL_normalize);
1634
1635   RCL_Vector2D result;
1636   RCL_Unit l = RCL_len(v);
1637   l = RCL_nonZero(l);
1638
1639   result.x = (v.x * RCL_UNITS_PER_SQUARE) / l;
1640   result.y = (v.y * RCL_UNITS_PER_SQUARE) / l;
1641
1642   return result;
1643 }
1644
1645 RCL_Unit RCL_vectorsAngleCos(RCL_Vector2D v1, RCL_Vector2D v2)
1646 {
1647   RCL_profileCall(RCL_vectorsAngleCos);
1648
1649   v1 = RCL_normalize(v1);
1650   v2 = RCL_normalize(v2);
1651
1652   return (v1.x * v2.x + v1.y * v2.y) / RCL_UNITS_PER_SQUARE;
1653 }
1654
1655 RCL_PixelInfo RCL_mapToScreen(RCL_Vector2D worldPosition, RCL_Unit height,
1656   RCL_Camera camera)
1657 {
1658   RCL_PixelInfo result;
1659
1660   RCL_Vector2D toPoint;
1661
1662   toPoint.x = worldPosition.x - camera.position.x;
1663   toPoint.y = worldPosition.y - camera.position.y;
1664
1665   RCL_Unit middleColumn = camera.resolution.x / 2;
1666
1667   // rotate the point
1668
1669   RCL_Unit cos = RCL_cosInt(camera.direction);
1670   RCL_Unit sin = RCL_sinInt(camera.direction);
1671
1672   RCL_Unit tmp = toPoint.x;
1673
1674   toPoint.x = (toPoint.x * cos - toPoint.y * sin) / RCL_UNITS_PER_SQUARE;
1675   toPoint.y = (tmp * sin + toPoint.y * cos) / RCL_UNITS_PER_SQUARE;
1676
1677   result.depth = toPoint.x;
1678
1679   result.position.x =
1680     middleColumn + (-1 * toPoint.y * middleColumn) / RCL_nonZero(result.depth);
1681
1682   result.position.y = camera.resolution.y / 2 -
1683 (((3 * camera.resolution.y) / 4 ) *
1684 //    ((camera.resolution.y / 2) *
1685      RCL_perspectiveScale(height - camera.height,result.depth))
1686      / RCL_UNITS_PER_SQUARE + camera.shear;
1687
1688   return result;
1689 }
1690
1691 RCL_Unit RCL_degreesToUnitsAngle(int16_t degrees)
1692 {
1693   return (degrees * RCL_UNITS_PER_SQUARE) / 360;
1694 }
1695
1696 RCL_Unit RCL_perspectiveScale(RCL_Unit originalSize, RCL_Unit distance)
1697 {
1698   RCL_profileCall(RCL_perspectiveScale);
1699
1700   return distance != 0 ?
1701    (originalSize * RCL_UNITS_PER_SQUARE) /
1702       ((RCL_VERTICAL_FOV * 2 * distance) / RCL_UNITS_PER_SQUARE)
1703    : 0;
1704 }
1705
1706 RCL_Unit RCL_perspectiveScaleInverse(RCL_Unit originalSize,
1707   RCL_Unit scaledSize)
1708 {
1709   return scaledSize != 0 ?
1710     (originalSize * RCL_UNITS_PER_SQUARE + RCL_UNITS_PER_SQUARE / 2) /
1711                                            // ^ take the middle
1712       ((RCL_VERTICAL_FOV * 2 * scaledSize) / RCL_UNITS_PER_SQUARE)
1713     : RCL_INFINITY;
1714 }
1715
1716 void RCL_moveCameraWithCollision(RCL_Camera *camera, RCL_Vector2D planeOffset,
1717   RCL_Unit heightOffset, RCL_ArrayFunction floorHeightFunc,
1718   RCL_ArrayFunction ceilingHeightFunc, int8_t computeHeight, int8_t force)
1719 {
1720   int8_t movesInPlane = planeOffset.x != 0 || planeOffset.y != 0;
1721   int16_t xSquareNew, ySquareNew;
1722
1723   if (movesInPlane || force)
1724   {
1725     RCL_Vector2D corner; // BBox corner in the movement direction
1726     RCL_Vector2D cornerNew;
1727
1728     int16_t xDir = planeOffset.x > 0 ? 1 : -1;
1729     int16_t yDir = planeOffset.y > 0 ? 1 : -1;
1730
1731     corner.x = camera->position.x + xDir * RCL_CAMERA_COLL_RADIUS;
1732     corner.y = camera->position.y + yDir * RCL_CAMERA_COLL_RADIUS;
1733
1734     int16_t xSquare = RCL_divRoundDown(corner.x,RCL_UNITS_PER_SQUARE);
1735     int16_t ySquare = RCL_divRoundDown(corner.y,RCL_UNITS_PER_SQUARE);
1736
1737     cornerNew.x = corner.x + planeOffset.x;
1738     cornerNew.y = corner.y + planeOffset.y;
1739
1740     xSquareNew = RCL_divRoundDown(cornerNew.x,RCL_UNITS_PER_SQUARE);
1741     ySquareNew = RCL_divRoundDown(cornerNew.y,RCL_UNITS_PER_SQUARE);
1742
1743     RCL_Unit bottomLimit = -1 * RCL_INFINITY;
1744     RCL_Unit topLimit = RCL_INFINITY;
1745
1746     if (computeHeight)
1747     {
1748       bottomLimit = camera->height - RCL_CAMERA_COLL_HEIGHT_BELOW +
1749         RCL_CAMERA_COLL_STEP_HEIGHT;
1750
1751       topLimit = camera->height + RCL_CAMERA_COLL_HEIGHT_ABOVE;
1752     }
1753
1754     // checks a single square for collision against the camera
1755     #define collCheck(dir,s1,s2)\
1756     if (computeHeight)\
1757     {\
1758       RCL_Unit height = floorHeightFunc(s1,s2);\
1759       if (height > bottomLimit)\
1760         dir##Collides = 1;\
1761       else if (ceilingHeightFunc != 0)\
1762       {\
1763         RCL_Unit height2 = ceilingHeightFunc(s1,s2);\
1764         if ((height2 < topLimit) || ((height2 - height) < \
1765           (RCL_CAMERA_COLL_HEIGHT_ABOVE + RCL_CAMERA_COLL_HEIGHT_BELOW)))\
1766           dir##Collides = 1;\
1767       }\
1768     }\
1769     else\
1770       dir##Collides = floorHeightFunc(s1,s2) > RCL_CAMERA_COLL_STEP_HEIGHT;
1771
1772     // check a collision against non-diagonal square
1773     #define collCheckOrtho(dir,dir2,s1,s2,x)\
1774     if (dir##SquareNew != dir##Square)\
1775     {\
1776       collCheck(dir,s1,s2)\
1777     }\
1778     if (!dir##Collides)\
1779     { /* now also check for coll on the neighbouring square */ \
1780       int16_t dir2##Square2 = RCL_divRoundDown(corner.dir2 - dir2##Dir *\
1781         RCL_CAMERA_COLL_RADIUS * 2,RCL_UNITS_PER_SQUARE);\
1782       if (dir2##Square2 != dir2##Square)\
1783       {\
1784         if (x)\
1785           collCheck(dir,dir##SquareNew,dir2##Square2)\
1786         else\
1787           collCheck(dir,dir2##Square2,dir##SquareNew)\
1788       }\
1789     }
1790
1791     int8_t xCollides = 0;
1792     collCheckOrtho(x,y,xSquareNew,ySquare,1)
1793
1794     int8_t yCollides = 0;
1795     collCheckOrtho(y,x,xSquare,ySquareNew,0)
1796
1797     #define collHandle(dir)\
1798     if (dir##Collides)\
1799       cornerNew.dir = (dir##Square) * RCL_UNITS_PER_SQUARE +\
1800       RCL_UNITS_PER_SQUARE / 2 + dir##Dir * (RCL_UNITS_PER_SQUARE / 2) -\
1801       dir##Dir;\
1802
1803     if (!xCollides && !yCollides) /* if non-diagonal collision happend, corner
1804                                      collision can't happen */
1805     {
1806       if (xSquare != xSquareNew && ySquare != ySquareNew) // corner?
1807       {
1808         int8_t xyCollides = 0;
1809         collCheck(xy,xSquareNew,ySquareNew)
1810
1811         if (xyCollides)
1812         {
1813           // normally should slide, but let's KISS
1814           cornerNew = corner;
1815         }
1816       }
1817     }
1818
1819     collHandle(x)
1820     collHandle(y)
1821
1822     #undef collCheck
1823     #undef collHandle
1824
1825     camera->position.x = cornerNew.x - xDir * RCL_CAMERA_COLL_RADIUS;
1826     camera->position.y = cornerNew.y - yDir * RCL_CAMERA_COLL_RADIUS;
1827   }
1828
1829   if (computeHeight && (movesInPlane || heightOffset != 0 || force))
1830   {
1831     camera->height += heightOffset;
1832
1833     int16_t xSquare1 = RCL_divRoundDown(camera->position.x -
1834       RCL_CAMERA_COLL_RADIUS,RCL_UNITS_PER_SQUARE);
1835
1836     int16_t xSquare2 = RCL_divRoundDown(camera->position.x +
1837       RCL_CAMERA_COLL_RADIUS,RCL_UNITS_PER_SQUARE);
1838
1839     int16_t ySquare1 = RCL_divRoundDown(camera->position.y -
1840       RCL_CAMERA_COLL_RADIUS,RCL_UNITS_PER_SQUARE);
1841
1842     int16_t ySquare2 = RCL_divRoundDown(camera->position.y +
1843       RCL_CAMERA_COLL_RADIUS,RCL_UNITS_PER_SQUARE);
1844
1845     RCL_Unit bottomLimit = floorHeightFunc(xSquare1,ySquare1);
1846     RCL_Unit topLimit = ceilingHeightFunc != 0 ?
1847       ceilingHeightFunc(xSquare1,ySquare1) : RCL_INFINITY;
1848
1849     RCL_Unit height;
1850
1851     #define checkSquares(s1,s2)\
1852     {\
1853       height = floorHeightFunc(xSquare##s1,ySquare##s2);\
1854       bottomLimit = RCL_max(bottomLimit,height);\
1855       height = ceilingHeightFunc != 0 ?\
1856         ceilingHeightFunc(xSquare##s1,ySquare##s2) : RCL_INFINITY;\
1857       topLimit = RCL_min(topLimit,height);\
1858     }
1859
1860     if (xSquare2 != xSquare1)
1861       checkSquares(2,1)
1862
1863     if (ySquare2 != ySquare1)
1864       checkSquares(1,2)
1865
1866     if (xSquare2 != xSquare1 && ySquare2 != ySquare1)
1867       checkSquares(2,2)
1868
1869     camera->height = RCL_clamp(camera->height,
1870       bottomLimit + RCL_CAMERA_COLL_HEIGHT_BELOW,
1871       topLimit - RCL_CAMERA_COLL_HEIGHT_ABOVE);
1872
1873     #undef checkSquares
1874   }
1875 }
1876
1877 void RCL_initCamera(RCL_Camera *camera)
1878 {
1879   camera->position.x = 0;
1880   camera->position.y = 0;
1881   camera->direction = 0;
1882   camera->resolution.x = 20;
1883   camera->resolution.y = 15;
1884   camera->shear = 0;
1885   camera->height = RCL_UNITS_PER_SQUARE;
1886 }
1887
1888 void RCL_initRayConstraints(RCL_RayConstraints *constraints)
1889 {
1890   constraints->maxHits = 1;
1891   constraints->maxSteps = 20;
1892 }
1893
1894 #endif