2 * Copyright 2018 Jacob Lifshay
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in all
12 * copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 inline void putchar(int ch
)
32 __builtin_printf("\u2593");
35 __builtin_printf("\u2591");
38 __builtin_printf("%c", (char)ch
);
41 *reinterpret_cast<volatile char *>(0x80000000) = ch
;
45 inline void write_hex_digit(int value
)
47 putchar("0123456789ABCDEF"[value
]);
50 inline void write_hex_u8(std::uint8_t value
)
52 write_hex_digit(value
>> 4);
53 write_hex_digit(value
& 0xF);
56 inline void write_hex_u16(std::uint16_t value
)
58 write_hex_u8(value
>> 8);
59 write_hex_u8(value
& 0xFF);
62 inline void write_hex_u32(std::uint32_t value
)
64 write_hex_u16(value
>> 16);
65 write_hex_u16(value
& 0xFFFF);
68 inline std::uint32_t read_gpio()
73 return *reinterpret_cast<volatile std::uint32_t *>(0x80000010);
77 inline void write_gpio(std::uint32_t value
)
79 #ifndef EMULATE_TARGET
80 *reinterpret_cast<volatile std::uint32_t *>(0x80000010) = value
;
84 constexpr std::uint32_t switch_2_mask
= 0x200;
85 constexpr std::uint32_t switch_3_mask
= 0x400;
87 inline void puts(const char *str
)
93 constexpr std::size_t screen_x_size
= 800 / 8;
94 constexpr std::size_t screen_y_size
= 600 / 8;
97 struct get_double_length_type
;
100 struct get_double_length_type
<std::uint8_t>
102 typedef std::uint16_t type
;
106 struct get_double_length_type
<std::uint16_t>
108 typedef std::uint32_t type
;
112 struct get_double_length_type
<std::uint32_t>
114 typedef std::uint64_t type
;
118 struct get_double_length_type
<std::int8_t>
120 typedef std::int16_t type
;
124 struct get_double_length_type
<std::int16_t>
126 typedef std::int32_t type
;
130 struct get_double_length_type
<std::int32_t>
132 typedef std::int64_t type
;
135 template <typename T
>
136 constexpr T
bidirectional_shift_left(T value
, int amount
) noexcept
138 int max_shift
= std::numeric_limits
<T
>::digits
;
139 if(amount
<= -max_shift
)
140 return value
< 0 ? -1 : 0;
142 return value
>> -amount
;
143 return value
<< amount
;
146 template <typename T
>
147 constexpr T
bidirectional_shift_right(T value
, int amount
) noexcept
149 return bidirectional_shift_left(value
, -amount
);
152 template <typename T
= std::int32_t, std::size_t FractionalBits
= 16>
156 typedef T underlying_type
;
157 typedef typename get_double_length_type
<T
>::type double_length_type
;
158 static constexpr std::size_t total_bits
= std::numeric_limits
<T
>::digits
;
159 static constexpr std::size_t fractional_bits
= FractionalBits
;
160 static constexpr std::size_t integer_bits
= total_bits
- fractional_bits
;
161 static constexpr T fraction_mask
= (static_cast<T
>(1) << fractional_bits
) - 1;
162 static constexpr T integer_mask
= ~fraction_mask
;
163 static_assert(total_bits
>= fractional_bits
, "");
166 underlying_type value
;
169 constexpr Fixed() noexcept
: value(0)
172 constexpr Fixed(signed char v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
175 constexpr Fixed(short v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
178 constexpr Fixed(int v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
181 constexpr Fixed(long v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
184 constexpr Fixed(long long v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
187 constexpr Fixed(unsigned char v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
190 constexpr Fixed(char v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
193 constexpr Fixed(unsigned short v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
196 constexpr Fixed(unsigned v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
199 constexpr Fixed(unsigned long v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
202 constexpr Fixed(unsigned long long v
) noexcept
: value(static_cast<T
>(v
) << fractional_bits
)
205 constexpr Fixed(float v
) noexcept
206 : value(static_cast<T
>(static_cast<float>(1ULL << fractional_bits
) * v
))
209 constexpr Fixed(double v
) noexcept
210 : value(static_cast<T
>(static_cast<double>(1ULL << fractional_bits
) * v
))
213 constexpr explicit operator T() const noexcept
216 return (value
+ fraction_mask
) >> fractional_bits
;
217 return value
>> fractional_bits
;
219 constexpr explicit operator double() const noexcept
221 return value
* (1.0 / (1ULL << fractional_bits
));
223 static constexpr Fixed
make(T underlying_value
) noexcept
226 retval
.value
= underlying_value
;
229 constexpr Fixed
operator+() const noexcept
233 constexpr Fixed
operator-() const noexcept
237 friend constexpr Fixed
operator+(Fixed a
, Fixed b
) noexcept
239 return make(a
.value
+ b
.value
);
241 friend constexpr Fixed
operator-(Fixed a
, Fixed b
) noexcept
243 return make(a
.value
- b
.value
);
245 friend constexpr Fixed
operator*(Fixed a
, Fixed b
) noexcept
247 return make(static_cast<double_length_type
>(a
.value
) * b
.value
>> fractional_bits
);
249 friend constexpr Fixed
operator/(Fixed a
, Fixed b
) noexcept
251 return make((static_cast<double_length_type
>(a
.value
) << fractional_bits
) / b
.value
);
253 constexpr Fixed
&operator+=(Fixed rt
) noexcept
255 return *this = *this + rt
;
257 constexpr Fixed
&operator-=(Fixed rt
) noexcept
259 return *this = *this - rt
;
261 constexpr Fixed
&operator*=(Fixed rt
) noexcept
263 return *this = *this * rt
;
265 constexpr Fixed
&operator/=(Fixed rt
) noexcept
267 return *this = *this / rt
;
269 constexpr T
underlying_value() const noexcept
273 friend constexpr bool operator==(Fixed a
, Fixed b
) noexcept
275 return a
.value
== b
.value
;
277 friend constexpr bool operator!=(Fixed a
, Fixed b
) noexcept
279 return a
.value
!= b
.value
;
281 friend constexpr bool operator<=(Fixed a
, Fixed b
) noexcept
283 return a
.value
<= b
.value
;
285 friend constexpr bool operator>=(Fixed a
, Fixed b
) noexcept
287 return a
.value
>= b
.value
;
289 friend constexpr bool operator<(Fixed a
, Fixed b
) noexcept
291 return a
.value
< b
.value
;
293 friend constexpr bool operator>(Fixed a
, Fixed b
) noexcept
295 return a
.value
> b
.value
;
297 friend constexpr Fixed
floor(Fixed v
) noexcept
299 v
.value
&= integer_mask
;
302 friend constexpr Fixed
fracf(Fixed v
) noexcept
304 v
.value
&= fraction_mask
;
307 friend constexpr Fixed
ceil(Fixed v
) noexcept
309 v
.value
+= fraction_mask
;
312 friend constexpr Fixed
round(Fixed v
) noexcept
314 constexpr Fixed one_half
= 0.5;
318 friend constexpr T
floori(Fixed v
) noexcept
320 return v
.value
>> fractional_bits
;
322 friend constexpr T
ceili(Fixed v
) noexcept
324 v
.value
+= fraction_mask
;
327 friend constexpr T
roundi(Fixed v
) noexcept
329 constexpr Fixed one_half
= 0.5;
333 friend constexpr Fixed
abs(Fixed v
) noexcept
339 friend constexpr Fixed
sqrt(Fixed v
) noexcept
344 double_length_type guess_squared
= 0;
345 for(int bit_index
= (integer_bits
+ 1) / 2; bit_index
>= -static_cast<int>(fractional_bits
);
348 Fixed new_guess
= guess
+ make(static_cast<T
>(1) << (bit_index
+ fractional_bits
));
349 double_length_type new_guess_squared
= guess_squared
;
350 new_guess_squared
+= bidirectional_shift_left(
351 static_cast<double_length_type
>(guess
.value
), bit_index
+ 1);
352 new_guess_squared
+= bidirectional_shift_left(
353 static_cast<double_length_type
>(Fixed(1).value
), 2 * bit_index
);
354 if(new_guess_squared
< v
.value
)
357 guess_squared
= new_guess_squared
;
359 else if(new_guess_squared
== v
.value
)
366 enum class Block
: char
373 constexpr double constexpr_sin2pi(double x
) noexcept
375 x
-= static_cast<long long>(x
);
387 const double coefficients
[] = {
388 1.5873670538243229332222957023504872028033458258785e-8,
389 -3.2649283479971170585768247133750680886632233028762e-7,
390 5.8056524029499061679627827975252772363553363262495e-6,
391 -8.8235335992430051344844841671401871742374913922057e-5,
392 1.1309237482517961877702180414488525515732161905954e-3,
393 -1.2031585942120627233202567845286556653885737182738e-2,
394 1.0422916220813984117271044898760411097029995316417e-1,
395 -7.1812230177850051223174027860686238053986168884284e-1,
396 3.8199525848482821277337920673404661254406128731422,
397 -1.5094642576822990391826616232531520514481435107371e1
,
398 4.205869394489765314498681114813355254161277992845e1
,
399 -7.6705859753061385841630641093893125889966539055122e1
,
400 8.1605249276075054203397682678249495061413521767487e1
,
401 -4.1341702240399760233968420089468526936300384754514e1
,
402 6.2831853071795864769252867665590057683943387987502,
405 for(double coeff
: coefficients
)
410 constexpr double constexpr_cos2pi(double x
) noexcept
412 x
-= static_cast<long long>(x
);
414 return constexpr_sin2pi(x
);
417 template <std::size_t N
= 65>
420 static_assert(N
> 1, "");
421 constexpr std::size_t size() const noexcept
425 Fixed
<> sin_table
[N
];
426 constexpr SinCosList() noexcept
: sin_table
{}
428 for(std::size_t i
= 0; i
< N
; i
++)
430 double rotations
= i
/ (4.0 * (N
- 1));
431 sin_table
[i
] = constexpr_sin2pi(rotations
);
434 constexpr void get(Fixed
<> &sin_out
, Fixed
<> &cos_out
, Fixed
<> rotations
) const noexcept
436 rotations
= fracf(rotations
) * 4;
437 int quadrent
= floori(rotations
);
438 rotations
= (N
- 1) * fracf(rotations
);
439 auto int_part
= floori(rotations
);
440 auto fraction
= fracf(rotations
);
442 sin_table
[int_part
] + fraction
* (sin_table
[int_part
+ 1] - sin_table
[int_part
]);
444 sin_table
[N
- 1 - int_part
]
445 + fraction
* (sin_table
[N
- 1 - int_part
- 1] - sin_table
[N
- 1 - int_part
]);
450 cos_out
= -sin_value
;
453 sin_out
= -sin_value
;
454 cos_out
= -cos_value
;
457 sin_out
= -cos_value
;
466 constexpr Fixed
<> get_sin(Fixed
<> rotations
) const noexcept
469 get(sin
, cos
, rotations
);
472 constexpr Fixed
<> get_cos(Fixed
<> rotations
) const noexcept
475 get(sin
, cos
, rotations
);
480 constexpr auto sin_cos_list
= SinCosList
<>();
482 constexpr void rotate(Fixed
<> &x
, Fixed
<> &y
, Fixed
<> rotations
)
485 sin_cos_list
.get(sin
, cos
, rotations
);
486 auto new_x
= x
* cos
- y
* sin
;
487 auto new_y
= x
* sin
+ y
* cos
;
492 inline void write_fixed(Fixed
<> v
)
494 write_hex_u32(floori(v
));
496 write_hex_u16(floori(fracf(v
) * 0x10000));
499 template <typename T
>
502 typedef T element_type
;
504 constexpr Vec2D() noexcept
: x(), y()
507 constexpr explicit Vec2D(T v
) noexcept
: x(v
), y(v
)
510 constexpr Vec2D(T x
, T y
) noexcept
: x(x
), y(y
)
513 friend constexpr Vec2D
operator+(Vec2D a
, Vec2D b
) noexcept
515 return Vec2D(a
.x
+ b
.x
, a
.y
+ b
.y
);
517 friend constexpr Vec2D
operator-(Vec2D a
, Vec2D b
) noexcept
519 return Vec2D(a
.x
- b
.x
, a
.y
- b
.y
);
521 friend constexpr Vec2D
operator*(T a
, Vec2D b
) noexcept
523 return Vec2D(a
* b
.x
, a
* b
.y
);
525 friend constexpr Vec2D
operator*(Vec2D a
, T b
) noexcept
527 return Vec2D(a
.x
* b
, a
.y
* b
);
529 friend constexpr Vec2D
operator/(Vec2D a
, T b
) noexcept
531 return Vec2D(a
.x
/ b
, a
.y
/ b
);
533 constexpr Vec2D
&operator+=(Vec2D rt
) noexcept
535 return *this = *this + rt
;
537 constexpr Vec2D
&operator-=(Vec2D rt
) noexcept
539 return *this = *this - rt
;
541 constexpr Vec2D
&operator*=(T rt
) noexcept
543 return *this = *this * rt
;
545 constexpr Vec2D
&operator/=(T rt
) noexcept
547 return *this = *this / rt
;
551 constexpr Vec2D
<Fixed
<>> rotate(Vec2D
<Fixed
<>> v
, Fixed
<> rotations
) noexcept
553 rotate(v
.x
, v
.y
, rotations
);
557 constexpr void init_ray_cast_dimension(Fixed
<> ray_direction
,
558 Fixed
<> ray_start_position
,
559 std::int32_t current_position
,
562 std::int32_t &delta_position
)
564 if(ray_direction
== 0)
566 auto inverse_direction
= 1 / ray_direction
;
567 step_t
= abs(inverse_direction
);
568 std::int32_t target_position
{};
569 if(ray_direction
< 0)
571 target_position
= ceili(ray_start_position
) - 1;
576 target_position
= floori(ray_start_position
) + 1;
579 next_t
= (target_position
- ray_start_position
) * inverse_direction
;
584 Vec2D
<Fixed
<>> ray_start_position
;
585 Vec2D
<Fixed
<>> ray_direction
;
586 Vec2D
<std::int32_t> current_position
;
588 Vec2D
<Fixed
<>> next_t
;
589 Vec2D
<Fixed
<>> step_t
;
590 Vec2D
<std::int32_t> delta_position
;
591 int last_hit_dimension
= -1;
592 constexpr RayCaster(Vec2D
<Fixed
<>> ray_start_position
, Vec2D
<Fixed
<>> ray_direction
) noexcept
593 : ray_start_position(ray_start_position
),
594 ray_direction(ray_direction
),
595 current_position(floori(ray_start_position
.x
), floori(ray_start_position
.y
)),
596 current_t(Fixed
<>::make(1)),
601 init_ray_cast_dimension(ray_direction
.x
,
602 ray_start_position
.x
,
607 init_ray_cast_dimension(ray_direction
.y
,
608 ray_start_position
.y
,
614 constexpr void step() noexcept
616 if(ray_direction
.x
!= 0 && (ray_direction
.y
== 0 || next_t
.x
< next_t
.y
))
618 current_t
= next_t
.x
;
619 next_t
.x
+= step_t
.x
;
620 current_position
.x
+= delta_position
.x
;
621 last_hit_dimension
= 0;
623 else if(ray_direction
.y
!= 0)
625 current_t
= next_t
.y
;
626 next_t
.y
+= step_t
.y
;
627 current_position
.y
+= delta_position
.y
;
628 last_hit_dimension
= 1;
635 static std::uint8_t start_col
[screen_x_size
] = {}, end_col
[screen_x_size
] = {};
636 static char col_color
[screen_x_size
] = {};
637 constexpr std::size_t world_x_size
= 16, world_z_size
= 16;
638 static const char world
[world_x_size
][world_z_size
] = {
640 {'|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', 'X', 'X'},
641 {'|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|', ' ', ' ', ' ', 'X'},
642 {'|', ' ', '|', '|', '|', '|', '|', '|', '|', ' ', ' ', '|', ' ', ' ', ' ', 'X'},
643 {'|', ' ', ' ', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', '|', 'X', 'X'},
644 {'|', ' ', ' ', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', '|', '|', '|'},
645 {'|', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', ' ', '|'},
646 {'|', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', ' ', '|'},
647 {'|', ' ', '|', ' ', ' ', ' ', ' ', ' ', '|', ' ', ' ', '|', '|', '|', ' ', '|'},
648 {'|', ' ', '|', ' ', ' ', ' ', ' ', ' ', '|', ' ', ' ', '|', ' ', ' ', ' ', '|'},
649 {'|', ' ', '|', '|', '|', '|', '|', '|', '|', ' ', ' ', '|', ' ', ' ', ' ', '|'},
650 {'|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|', ' ', ' ', ' ', '|'},
651 {'|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|', ' ', ' ', ' ', '|'},
652 {'|', ' ', '|', '|', '|', '|', '|', '|', '|', ' ', ' ', '|', ' ', ' ', ' ', '|'},
653 {'|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'},
654 {'|', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '|'},
655 {'|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|', '|'},
658 Vec2D
<Fixed
<>> view_position(1.5, 1.5);
659 Fixed
<> view_angle(0);
660 std::uint32_t flash_counter
= 0;
661 constexpr std::uint32_t flash_period
= 10;
665 if(flash_counter
>= flash_period
)
667 if(read_gpio() & switch_2_mask
)
670 view_angle
= fracf(view_angle
);
672 if(read_gpio() & switch_3_mask
)
674 Vec2D
<Fixed
<>> forward(0, 0.05);
675 forward
= rotate(forward
, view_angle
);
676 auto new_view_position
= view_position
+ forward
;
677 Vec2D
<std::int32_t> new_block_position(floori(new_view_position
.x
),
678 floori(new_view_position
.y
));
680 auto block
= world
[new_block_position
.x
][new_block_position
.y
];
682 view_position
= new_view_position
;
684 Fixed
<> closest_distance(100);
685 for(int dx
= -1; dx
<= 1; dx
++)
687 for(int dy
= -1; dy
<= 1; dy
++)
689 auto block_position
= new_block_position
;
690 block_position
.x
+= dx
;
691 block_position
.y
+= dy
;
692 auto block
= world
[block_position
.x
][block_position
.y
];
695 auto closest_position
= new_view_position
;
696 if(closest_position
.x
< block_position
.x
)
697 closest_position
.x
= block_position
.x
;
698 else if(closest_position
.x
> block_position
.x
+ 1)
699 closest_position
.x
= block_position
.x
+ 1;
700 if(closest_position
.y
< block_position
.y
)
701 closest_position
.y
= block_position
.y
;
702 else if(closest_position
.y
> block_position
.y
+ 1)
703 closest_position
.y
= block_position
.y
+ 1;
704 auto current_distance_x
= abs(closest_position
.x
- block_position
.x
);
705 auto current_distance_y
= abs(closest_position
.y
- block_position
.y
);
706 auto current_distance
= current_distance_x
;
707 if(current_distance
< current_distance_y
)
708 current_distance
= current_distance_y
;
709 if(current_distance
< closest_distance
)
710 closest_distance
= current_distance
;
713 if(closest_distance
>= 0.1)
714 view_position
= new_view_position
;
717 for(std::size_t x
= 0; x
< screen_x_size
; x
++)
719 Vec2D
<Fixed
<>> ray_direction(
720 (Fixed
<>(x
) + (0.5 - screen_x_size
/ 2.0)) * (2.0 / screen_x_size
), 1);
721 ray_direction
= rotate(ray_direction
, view_angle
);
722 RayCaster
ray_caster(view_position
, ray_direction
);
723 auto hit_block
= world
[ray_caster
.current_position
.x
][ray_caster
.current_position
.y
];
724 while(hit_block
== ' ')
727 hit_block
= world
[ray_caster
.current_position
.x
][ray_caster
.current_position
.y
];
729 constexpr Fixed
<> max_height
= 10;
730 Fixed
<> height
= ray_caster
.current_t
!= Fixed
<>::make(1) ?
731 1 / ray_caster
.current_t
:
733 if(height
> max_height
)
735 height
*= screen_x_size
/ 2.0;
736 auto iheight
= roundi(height
);
737 if(iheight
> static_cast<int>(screen_y_size
))
738 iheight
= screen_y_size
;
741 start_col
[x
] = screen_y_size
/ 2 - iheight
/ 2;
742 end_col
[x
] = screen_y_size
/ 2 + (iheight
+ 1) / 2;
744 if(hit_block
== 'X' && flash_counter
>= flash_period
/ 2)
747 if(ray_caster
.last_hit_dimension
== 0)
750 else if(ray_caster
.last_hit_dimension
== 0)
756 for(std::size_t y
= 0; y
< screen_y_size
; y
++)
758 for(std::size_t x
= 0,
759 x_end
= (y
== screen_y_size
- 1 ? screen_x_size
- 1 : screen_x_size
);
765 else if(y
>= start_col
[x
])
766 putchar(col_color
[x
]);