DEV Community: KorigamiK

Raycasting Adventures

KorigamiK — Sat, 05 Nov 2022 19:49:11 +0000

Read the (better) PDF version of this blog here!

So, this is going to be more of a summary and some implementation details of
my first ever experience with computer graphics and making games.

You can find the itch-io page
with all the instructions and links to download and play the game (maybe
even give me a follow)

Two weeks ago, not knowing anything about computer graphics and game
development, I embarked on a journey down the rabbit hole of creating
one of the pioneering games of video game history, such as the OG Doom
and Wolfenstein 3D.

I decided to create a raycasting engine in C++ using the Simple
DirectMedia Layer graphics library. And for a beginner like me, it was
quite the challenge.

The whole idea of making this in a very bare-bones library and language
like SDL2 and C++ was because I wanted to create something that
would be truly cross-platform from the start. And by cross-platform I
mean cross-platform. The game would run on all desktop operating
systems (Linux, Windows, Apple) and all mobile operating systems
(Android, iOS, Raspberry Pi, Chrome)! And of course the
PSP. I could talk a lot about why the PSP, but I'll save
that for another time.

Introduction

Now you must be asking - \"Bruh, what even is a Raycaster\".

The simplest way to explain it is that it's a rendering technique to
create a 3D perspective from a 2D map, what we like to call as 2.5D.

Although this is about the making of a raycasting game engine, I had to
give a lot of thought on how game engines are structured in the first
place.

I wanted my project to follow the Object-Oriented design pattern as
well so that it would be easy to extend and plug in components without
touching a lot of code, enabling a deeper level of abstraction. I taught
me a lot about inheritance and composition in C++.

The Game Engine

I'll talk about the game architecture in this section.

The engine was written in C++ and then compiled using the CMake build
system, which enables me to go completely cross-platform.

The high level architecture of the engine looks something like:

I would've gone more into the design but TikZ is such a huge pain to
learn. Though, I might come back to this in the future.

Raycasting

What actually distinguishes my project from any other implementation
that you may find on the web is the fact that instead of dividing the
whole world into square grids, it defines all the objects and texture
rendering using their actual coordinates.

Looking back, using the 2D grid approach while being a lot easier to
implement, it's also quite a bit more efficient and accurate.

Having said that, it also restricts a lot of what can be actually
created in the game.

The biggest leap of faith I took for this engine was to create the
raycasting logic. So, here's how raycasting actually works.

We first need to define these terms:

Player direction : The direction that the player is currently facing.
Maximum view distance : The position of the player in the world.
Horizontal field of view : The visible field of view
the player sees in the horizontal direction. I assumed this to be,
100°.
Vertical field of view : This gives an idea of how high or low
can the person see. I assume this to be, 60°.
Number of rays : This is the number of rays that we cast from
the player's position. You can set this number a lot of ways, and
how high you set this will determine how accurate the raycasting
will be.

Now we are ready to tackle the actual casting of rays. What our aim is
to cast a ray from the player's position in the direction of the
player's direction and then check if it intersects with any of
the walls in the map. If it does, then we need to calculate the distance
between the player and the wall and then draw a slice of the player's
view corresponding to that ray.

So, consider this diagram of the player's situation:

This circle corresponds to the player's maximum view distance ( ).

It should be noted that half of the cast rays would be on the left side
of the player's field of view ( ) and the other half
would be on the right side.

Now, we can define the angle between each ray as:

We are going to construct the view of the player by drawing a slice of
the view for each ray. The rays would be equally spaced (suspending the
angle at the player) starting from point till

We'll calculate (distance taken from ) by using the
following formula:

So, the distance for any ray at angle would be:

Now, we can calculate the width of the slice ( ) for each ray as:

But, we cannot calculate the vertical height of the slice by using the
distance of the ray's end point from the player
directly.

This is the exact cause of the fish eye effect that you might have seen
from some cameras that looks very alien to your eyes. It looks something
like

We can correct for the fish eye effect by taking the length of the ray
from the plane of the camera.

Thus, we calculate the height of the slice based on this:

Nice! The fish-eye effect is no more.

Phew! That was a lot of math. But, we are almost done.

Another thing that we can calculate is the brightness of an individual
slice:

This means that farther objects will appear darker than when they're
closer. You could probably play around here and find a way to do fog or
mist, but I'll leave that up to you.

The last thing left for us to do (at least on this blog) is to figure
out a way to map the image textures onto the actual walls.

The method is pretty simple,
- The width and height of the textures remain the same.
- The start of the texture can be calculated by taking into account the distance of the ray along the line.

The remainder operator will repeat the texture when the length of the
wall is greater than the texture itself.

Conclusion

That's it, Congrats, you made it to the end. The raycasting is working,
and you're now a game developer.

I hope you enjoyed the journey with me as much as I did making and
writing this. Maybe you'll even feel inclined to contribute and fix the
inevitably many bugs I have in my code.

Thank you Kueeing! (king + queen let's make this go mainstream)

Bags with Balls

KorigamiK — Tue, 16 Aug 2022 10:50:00 +0000

This post is my first experience in solving a "hard" problem on CodeForces.

As I logged in to CodeForces for the first time, I went to the Problemset
section hoping to solve some question. I was blissfully unaware how the
difficulty rating system worked. I picked the first problem in the list and
tried to have a go.

The question

There are n bags, each bag contains m balls with numbers from 1 to m. For
every
∈[1, m], there is exactly one ball with number

in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for
example, taking the ball 1 from the first bag and the ball 2 from the second bag
is not the same as taking the ball 2 from the first bag and the ball 1 from the
second bag). After that, you calculate the number of balls with odd numbers
among the ones you have taken. Let the number of these balls be

Your task is to calculate the sum of

over all possible ways to take n balls, one from each bag.

Initial Thoughts

So when I saw the notation for

I thought this supposed to refer to a
Multi-index n-tuple
where

was a tuple of all the odd index selected balls.

But that was stupid, it's just the regular exponent. Still it was pretty
interesting of them to ask the sum of the number of balls to
the

power.

The working

I was definitely stuck on this. There weren't even any solutions on the internet
either. But I was able to find some similar problems and that's where
WolframAlpha gave me the key to solve this problem.

Formulating the solution

We can consider the number of was to pick i odd balls from n bags each
containing m balls. This can be found out by:

We basically choose i boxes which we want the odd balls from and each of the
i boxes has m+1/2 choices, and then we want to choose even balls from the
n-i remaining bags which have m/2 choices each.

To make the expressions easier to maintain we will

So the final answer can be formulated as

Where we sum through all the number of odd balls which can be selected (from 0
to n) each contributes

to answer.

Now the challenge was the simplify this expression, as it is now it will be way
over the O(n) complexity that is required to solve these "hard" problems.

It seems awfully close to the well known binomial formula but the pesky

makes it almost impossible to simplify further.

Luckily after research on this a little, WolframAlpha taught me about the
existense of the
Stirling numbers which are
denoted by the { a b } bracketes like the binomial coefficient.

They have the interesting property that:

Which will help us to do something about the the exponent. I present to you the
steps to the simplification:

Therefore, the answer can be simplified into

The first term can be precomputed into a 2-D dp array. The final complexity of
the program should be ~ O(n + c)

Conclusion

I hope you found this thread interesting. I still don't think I will be able to
give much time to the competitive coding side of things. For me, it's similar to
a Sudoku or a puzzle that I would solve once in a while but not spend all my
brain power on just doing them.

Hello world!

KorigamiK — Mon, 15 Aug 2022 19:15:18 +0000

This is my first blog post!

$$ x_1 = 54 $$

int main(int argc, const char ** argv) {
    return 0;
}

print('hello')

const x: string = 'hi';
console.log(x)

x_2 = 21