Monday, February 4, 2013

Retro-style Raycasting #1

I've decided to start a series of almost tutorial-like posts with information on retro-style raycasting.
More specifically, this series of posts will cover my previous, current and future work with writing Wolfenstein-3D-like 2D array based raycasting engines with various optimizations.

There have been little to no major optimizations in the area of 2D array based raycasting, presumably because all modern hardware is too powerful to need it.
I've spent the last couple of years on and off building and improving raycasting engines.
Most of my early work was in AS2.

Here's a brief overview of my history with the pseudo-3D:

Ye Olde AS2 engines:

I originally started off by porting the code from this tutorial to AS2.
My initial port had graphical errors and a lot of bugs, but worked as a proof-of-concept, which I did about two years ago.
This was my V1 engine.

The V2 engine started off as a complete re-port of the code.
The V2 engine was bug-free, and started off as a texture-less raycaster.
The first improvement I made to the V2 engine was the addition of "fog" which was used as a basic way to implement basic pseudo-lighting.
The second improvement was to draw each wall face as a gradient-filled square instead of a crap-ton of vertical lines, which greatly decreased the time it took to draw the frame.
The V2 engine was also the first engine to support textures, for which I made two drawing algorithms, neither of which were particularly effective.

V3 was my first attempt at implementing my "extra trig" raycasting engine. I'll go into more detail on extra trig raycasting in another post.
The V3 engine, although not a complete failure, required an incredibly buggy piece of code to run: my "edge fix". to put it simply, the edge fix works by using the height of the previous raycasted wall to work out how high the current wall-face edge height is. the edge fix is effectively an interpolation algorithm for the raycaster, it gives a better looking image for many less rays, however, it was unfinished and had many bugs.
The V3 engine was discontinued very early on.

With the partial failure of the V3 engine, I started development on the V3-2 engine, which was built off the V2 engine because the V3 engine was deemed too unstable and bugged.
The V3-2 engine got to be quite powerful after several optimizations.
The V3-2 engine was the first engine to support sprites and have working z-sorting (z-sorting was done per-wall instead of per-pixel, which later gave me the idea of my Left-Right z-sorting algorithm which I may cover in a later post)
Also included in V3-2 was an incredibly snazzy minimap and basic multiplayer support.
V3-2 did not support textures, but was as bug-free and stable as V2.

V4 was a second, more advanced attempt at implementing my "extra-trig" raycasting method, built off of V3-2.
It was filled with bugs and hack-y fixes, but was beginning to show promise before I stopped development.
I stopped development on V4 a little over a year ago.
This was my last iteration of my AS2 raycaster.

About three or four months after the discontinuation of V4, I wrote a full, working AS3 Maze War prototype with a full server running on Adobe Air.

After that, I wrote a quick-and-dirty pseudo-3d engines that used vector-based maps and worked by calculating line intersections and trigonometry, it worked to an extent however there were visual bugs with it.

I dabbled with some experiments and wrote my own basic pseudo-3D engine in C++ that used vector-based maps, A similar "rasterization" technique to my "extra trig" raycasting method and was drawn using SDL late last year in preparation for writing an implementation of my Flood-Fill Raycaster-Like engine, which hasn't been started yet.

So far, I've come up with 3 Wolfenstein-like algorithms for raycasting that are faster than the conventional methods:

Extra-Trig Raycasting:
typically would use less than 50 rays to calculate any scene likely to exist in a game, resolution of display has no effect on rays used or calculation time, however amount of walls on the screen does. uses significantly more maths than regular raycasting but many major operations can be done using precalculation and look-up tables.
Estimated speed VS traditional method:
Depends on resolution, at 640x480, estimated 2-10 times faster.

Binary Raycaster:
Hard to estimate how many rays it would use - however it would definitely use significantly less. at a screen width of 640, maybe around 50-200 rays would be likely. More processing would have to be done per ray, but most likely not much. increased resolution means more calculation, more walls on screen means more calculation. significantly easier to implement than extra-trig
Estimated speed VS traditional method:
estimated 2-10 times faster

Flood-Fill Raycaster
Technically not a raycaster as it doesn't use rays. FFRC is one step on from Extra-Trig. Each tile in view is only checked once, trigonometry is used to do almost everything. heavy use of precalc and look-up tables can greatly increase efficiency. Calculation needed to do is proportional to tiles in view, both empty and filled. Screen resolution has no effect on processing needed.
Estimated speed VS traditional method:
estimated 5-100 times faster.

I have also been working on another perspective-based rasterizer which I believe would be limited to maze-war-like maps, but would allow players to look in all directions and possibly have free movement while still being more efficient than any other method above.

And that concludes a rough overview of my work on pseudo-3D engines. at least all the interesting stuff.

1 comment:

thanh tùng said...

hi Bmanatee.
My name is Tung, I'm from Vietnam, you help yourself hack wedgame.home page
 I want to change the values ​​marked in the freezing do.thanks

ps: I use googletranste to translate