News: My 2-Year Anniversary of Game Programming and Project Updates

Hello everyone,

This summer I am excited to announce I have finally been working on building my very own Java 2.5D Raycaster game engine with my friend Steven Bajmakovich. I can’t believe it has been two years since I began my game development journey with Steven, where we developed our very first game called X-Squadron from the ground up using the Unity game engine. I’m also super thrilled to announce that we will be releasing the updated X-Squadron game at the end of this summer with a whole new mission mode filled with waves of enemies and bosses! There will also be an information log in game to learn about the enemies and the lore behind the x-squadron team! The art has recently been vastly updated and greatly improved! With these things in mind, I’d like to post two very engaging videos about building a 2.5D Raycaster game engine. Many of the games from the 1990s such as Wolfenstein 3D, Doom, Duke Nukem 3D, and Elder Scrolls Arena, have been created with a Raycaster game engine.

Check out these videos! I’ll keep you guys posted on more updates as I go along. Plus, I will be updating my blog with new projects I’ve worked on in the past recently. I’ve done a lot of neat programs within the past year and I’d be happy to share these with all of you in the upcoming weeks.

The Build Engine: Part 2

I know it has been a while! I was really sick this whole past week, and I had a ton of schoolwork!

Anyway, the Build Engine utilizes two forms of storage for creating maps: an array of sectors and an array of walls.

In the Build Engine, the current sector the players are in have to be tracked after updating their positions. This is achieved by calling the updatesector(int newX, int newY, int* lastKnownSectorID) function in the code. The algorithm written to do this behavior pattern is as specified below:

1. The algorithm starts by assuming the player hasn’t moved much within the last update and will try and utilize the lastKnownSectorID to see if the player is in the last known sector.

2. If the algorithm fails to find the player in the last known Sector, it will check the neighboring sectors of the last known Sector by utilizing its portals.

3. If it fails to find the player in the neighboring sectors, then the algorithm will linearly search all of the sectors.

I think Fabien Sanglard’s website best explains this idea with the following picture

Retrieved from http://fabiensanglard.net/duke3d/build_engine_internals.php

The Build Engine: Part 1

Remember how the Doom Engine utilized Binary Space Partitioning to partition their maps? Well, the game Doom actually preprocessed and partitioned each map individually ahead of time with Binary Space Partitioning, which was a very time-consuming process at the time and even could take up to 30 minutes per map. However, Doom had the flexibility of sorting walls, determining the positions of sectors, and even collision detection. The walls in Doom could NOT move. 

However, Ken Silverman's Build engine removed this limitation of static walls by not implementing preprocessed maps. Build instead relies on what is known as a Portal System. Portal Systems are really useful and fast for eliminating regions of world geometry that are not within the player's view. The idea behind portal systems involves dividing the game world up into different zones that are connected by portals. Essentially, portals are represented by convex polygons from which one region (zone) of the world can be seen from another region (zone) of the world. Think of this as if you are standing in a room (a zone) and you are looking into the next room (another zone). The portals would be the doorways leading into the next rooms! Since game worlds can become massive, rendering the entire world all at once will really slow down your computer/device or possibly even crash them! However, since only certain regions of the world within the player's field of view need to be rendered, we can GREATLY speed up graphical processing and rendering! I'll provide a picture for extra clarification!

Portal System with Culling of regions to what is visible through the player's eyes. Everything that is white is not rendered!

Retrieved from https://www.panda3d.org/manual/index.php/Portal_Culling

Very detailed Portal System diagram., which is considered faster than BSP!

Retrieved from https://www.semanticscholar.org/paper/Portholes-and-planes%3A-faster-dynamic-evaluation-of-Roden-Parberry/54505db0eeab8b75a65d06818a295bd9b43172db

The Build Engine: A Very Brief Introduction

The Build Engine was created by Ken Silverman in the early to mid-1990s. The Build Engine was a huge step-up from the Doom Engine by providing many new features that were never seen before, such as destructible environments, sloped floors/ceilings, mirrors, looking up/down, flying/crouching/underwater, voxels and 3D immersion. However, the Build Engine is not a completely 3D game engine, since it utilized a 2D grid for world editing and added a height component for its sectors. This height component allowed each sector to have a different ceiling height and floor height! Floors and ceilings can hinge along one of the sector's walls to create slopes! Tomorrow I'll talk more about Build's Sectors and Portal System. I just wanted to quickly introduce this topic today since I've been busy setting up for school, hence the short posts recently!

Here is a video that overviews what the engine is capable of!

NOTE: The quality is low on this video though.

The Doom Game Engine: Part 4

The Doom engine renders walls by utilizing its Binary Space Partitioning (BSP). The engine renders the walls by traversing the nodes (which represent sectors/subsectors) in the Binary Tree, which draws these subsectors by order of distance from the camera; this means the closest segs (line segments of a wall) are drawn first. As segs are drawn, they are stored in a Linked List data structure. The Linked List is used to clip other segs AND the edges of sprites rendered later on. To reduce the burden on the engine's performance, there is a static limit of 256 segs that may be rendered at once. The excess segs are NOT drawn, leaving visible gaps where walls should be. However, because of the order in which segs are drawn, the gaps are out in the distance where they are less noticeable.

When the engine reaches a solid (one-sided) wall at a particular X coordinate, no more lines are drawn in that area. As this occurs, the engine creates a blueprint (or map) of the areas of the screen where solid walls have been reached. This implies that areas which are currently invisible to the player are clipped completely. Essentially this means that whatever the player is not looking at in the engine is NOT being rendered!

Wall textures are stored as a bunch of vertical columns, which is useful to the renderer since it can render walls by drawing many vertical columns of textures. Since all the walls in the doom engine are drawn vertically, the player cannot look up or down realistically. It is possible to approximate looking up and down via "Y-shearing." Y-Shearing works by increasing the vertical resolution and then imagining a "viewing window" on that space. One can imagine the scene being rendered as a very tall image, in which a sliding window represents the player's view. Sliding the window upwards corresponds to looking upwards, and sliding the window downwards correspond to looking downwards. As the window moves up or down, it creates the illusion that the player is looking up or down. The view tends to become more distorted as the player looks further away from the horizon line.

http://doom.wikia.com/wiki/Doom_rendering_engine

Y-Shearing image representation

The Doom Game Engine: Intermission

Intermission time!

Here are some cool videos that discuss Doom 1 and its BSP system! These videos explain BSP pretty good!

The Doom Game Engine Part 3

Doom makes use of a system known as Binary Space Partitioning (BSP). Binary space partitioning (BSP) is a technique used for recursively subdividing a space into convex shapes by utilizing mathematical hyperplanes. This process can take quite some time for a large level. Because of BSP, it is not possible to move the walls in the Doom Engine. 

Each level is divided up into a data structure known as a Binary Tree. Each location in the Binary Tree is called a "node", where each node in the Doom Engine represents a certain area/region of the level. The root node (which is the first node at the top of the tree from which every other node originates) represents the entire level. At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. This dividing line also divides linedefs into line segments called "segs".

The leaves of the tree (the bottom-most nodes with no children nodes) are convex polygons. These convex polygons are referred to as subsectors (or "SSECTORS"), and these subsectors are bound to a specific sector. Each subsector has a list of line segments (segs) associated with it.

The BSP system sorts the subsectors into the correct rendering order by using an algorithm as stated:

1. Begin at the root node.

2. Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a Scanline algorithm. The Scanline algorithm works like this according to Wikipedia: "All of the polygons to be rendered are first sorted by the top y-coordinate at which they first appear. Then each row or scan line of the image is computed using the intersection of a scanline with the polygons on the front of the sorted list. This happens while the sorted list is updated to discard no-longer-visible polygons as the current scan line progresses down the picture."

3. Once a subsector has been found, draw it.

The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that objects that are not visible aren't drawn or rendered; this allows maps to become very large without much performance loss!

https://en.wikipedia.org/wiki/Scanline_rendering

https://en.wikipedia.org/wiki/Binary_space_partitioning

Binary Tree Data Structure

Scan-line algorithm example retrieved from https://en.wikipedia.org/wiki/Scanline_rendering#/media/File:Scan-line_algorithm.svg

The Doom Game Engine Part 2

Over this last weekend, I was moving into my new college apartment, so I was SUPER busy! 

But today is Doom Engine part 2! 

The level editor in the game engine consisted of basic objects, such as vertices to represent single 2D points in space. These vertices can be joined together to create lines, which are known as "linedefs" in the engine. Each of these "linedefs" could have either one or two sides, known as "sidedefs." The editor could group these sidedefs together to create 2D polygons, and the polygons in the game engine are called sectors, which represent certain areas/rooms in a given level. One-sided linedefs represent a solid wall in the engine, while two-sided linedefs represent connections between two different sectors. Sidedefs are used to store wall textures, which are completely separate from the floor texture and ceiling texture.  

Every sector has a certain number of properties:

• a floor height,

• a ceiling height,

• a light level,

• a floor texture,

• and a ceiling texture.

What's interesting is that each sector only has ONE light level, so if you want to change the level of the lighting, you'd have to create a whole new sector and alter the light level of that sector! Sidedefs are used to store wall textures, which are completely separate from the floor texture and ceiling texture. Each sidedef can have up to 3 textures: the lower, middle and upper textures. With one-sided linedefs (i.e. solid walls), it is only possible to use the middle texture for the entire wall! But with two-sided linedefs (i.e. connections between sectors), the lower and upper textures are used to fill the gaps where adjacent sectors have different floor and ceiling heights. For example, the lower textures would be used to represent stairs. Most sidedefs don't utilize the middle texture often, even though they technically could. However, the middle texture is only really useful for hanging textures in mid-air. An example of a middle texture would be a transparent bar texture that appears to form a cage on a two-sided linedef!

The Doom Game Engine Part 1

Today I'm going to start discussing the Doom game engine, also known as id Tech 1. One quick thing I should mention too is that I will be starting college again soon. So, I'm probably only going to be doing shorter posts every day, or I'll do a couple of posts a week from now on.

id Tech 1 was written by John Carmack, with an initial release in December, 1993. The engine was used to make the games Doom, Doom II, Heretic, Hexen: Beyond Heretic, Strife: Quest for the Sigil, and a few others.  

While the engine appears to render a 3D space, the space is actually projected from a 2D floor plan. The player's line of sight was always parallel with the floor, and the walls had to be perpendicular to the floors because of how the engine would construct these 3D environments from a 2D projection. Thus the Doom engine wasn't exactly "3D", as the player couldn't look up or down at all. This meant that the engine could NOT be used to create multiple floors stacked on top of one another (i.e. it didn't support room-over-room) and it couldn't have sloped floors/ceilings either. However, id Tech 1 was revolutionary for its time because it had the ability to provide fast texture-mapped pseudo-3D environment on modern hardware at the time! 

Because the engine really projects from a 2D floor plan, the engine itself contains a super helpful "map mode", which represents a grid-like system for seeing a birds-eye view of the level you're currently editing; this allows the user of the engine to make simple edits and easily see the player and walls of a given room or area of the level (also known as "sectors").

Doom engine "Map Mode" (level editor) view

Retrieved from https://en.wikipedia.org/wiki/Doom_engine#/media/File:Doom-map-format-map.svg