Programming Doomed

[@edgeeffect]

I've been doing software development for a wide range of tasks for a very very very long time and I'm still blown away by the "mathematical intensity" of the stuff you games developers do.

[@JamesSharmanExtras]

Glad we can entertain you edgeeffect!

[@GeorgeTsiros]

we need to take advantage of every symmetry, every common factor, every simplification, every shortcut available, otherwise the simplest thing would take too long to calculate

[@HypherNet]

It's really neat to see your years of game dev experience (and significant expertise) come through in this video. It's been fun following along with your journey into hardware, in which it appears that you're largely learning as you go (sorry if that's wrong, and you actually have an EE MS), which is similar to my experiences with hardware. Here, however, you're solidly in a domain you understand well, and it shows. Thanks again for all the well-paced and clear-headed explanations of your thinking and progress. I also appreciate your between-the-lines gentle side-eye at all the "Omg you wrote a raycaster on your custom cpu!!11" comments.

[@JamesSharmanExtras]

Thanks for the kind words! Yeah, the start of this project was the beginning of my electronics journey, I've been leaning on the low level programming experience a lot.

[@cem_kaya]

great explanation made me go down of a few rabbit holes of googling before the invideo explanation.

[@JamesSharmanExtras]

I’m pleased! Glad you found it interesting!

[@rauljvila]

This is awesome, I know of no other resource that shows "both sides" (hardware and software) together. In both cases built from scratch, explained in excellent detail and in a very entertaining way. Looking forward to whatever you like to do because I like everything :D Thanks

[@JamesSharmanExtras]

Cool, thanks! Glad you are enjoying!

[@paulwratt]

Ben Eaters breadboard computer ..

[@rauljvila]

@@paulwratt That was the obvious comparison, I also love Ben Eater's videos, but he's miles away from being able to show how to program something like this. It's just a different approach and this channel is exactly what I missed from Ben's.

[@AJMansfield1]

If you used an algorithm that uses portal crossings rather than spatial coordinates to determine the player's current region, an engine like this could do "impossible geometry" architecture where which room is at some x,y coordinates depends on which route the player took to get there.

[@JamesSharmanExtras]

I love doing engines like that, I've written a few over the years but it would have interfered with a few development shortcuts I used here to make the demo. My 4d graph paper is on back order!

[@jimmy21584]

I wrote a portal renderer for fun recently, to see how simple I could make a renderer without overdraw or z buffer. I used boundary crossing for determining the current cell - worked nicely.

[@LuaanTi]

Yeah, the BSP seems kind of unnecessary here. You already have sectors and portals, and the only thing you need BSP for is finding which sector you're in - which you don't really need to do, since it's easy enough to 1) iterate through all connected sectors, 2) iterate through all if previous step didn't get a sector. Which is pretty much what Build does, and it allows the maps to be very dynamic and interactable, unlike Doom's "after making a tiny tweak to the map, you need to build the BSP over a couple of hours on the NeXT" :D I've always preferred game engines that allow non-Euclidean geometry and dynamic changes to the map. Sure, static maps and Euclidean geometry allow a lot of optimizations, but at what cost? :D

[@RajelAran]

Lots of fun playing such levels in Descent as a little girl lol

[@whilykitt]

This is so cool! Glad to see more of it!

[@JamesSharmanExtras]

Pleased to you liked it!

[@Philip8888888]

For the left side of the top corridor, I wonder if you could reduce the partitioning by instead of having the diagonal division, having a horizontal division on the same axis as the door in the middle?

[@JamesSharmanExtras]

That would have made the BSP simpler, but you would have had an extra wall segment. In this case the extra check in the bsp is easier.

[@theforthdoctor7872]

Outstanding!

[@JamesSharmanExtras]

Thanks!

[@thebrakshow7415]

This was simply amazing! You have done an excellent job on your computer and explaining the process. I'm really glad to see the software side of it!

[@JamesSharmanExtras]

Glad you have found it interesting!

[@francoisdastardly4405]

I see the complete video. Is very interesting. thanks for your time !

[@JamesSharmanExtras]

You are welcome!

[@LorisModenese]

Great video as always! Looking at the whole project, it could be interesting adding a DSP for handling floating point math and 2D/3D acceleration (ALU expansion). It could be an option for offloading video/audio effect from CPU. Many game systems during 90's use this acceleration method (TMS320 DSP chips was everywhere + custom chip for blittering and sprite overlay).

[@JamesSharmanExtras]

That would be an interesting challenge but it’s not for this project. I’m trying to build everything myself. An integer multiply would be more achievable and still offset some great performance gains.

[@LuaanTi]

The pre-Quake DOS 3D engines were usually done 100% with integer math, and it works great (though it needs a lot more maths tricks to get right; floating point is much easier on the developer). You don't even need integer division most of the time, and integer multiplication is not that hard to support.

[@RavenLuni]

love this kind of stuff (challenging projects with limited hardware).

[@JamesSharmanExtras]

This project is all about the challenge!

[@EnjoyCocaColaLight]

Could huge improvements be had with doors (portals) being closed and some sort of area-shift animation dealing with this?

[@JamesSharmanExtras]

I mention in the video you could gain some speed by having closed doors that effectively stopped being portals.

[@EnjoyCocaColaLight]

@@JamesSharmanExtras Yes, I reached that part after typing the comment, lol

[@garyliddon]

Great to see some software skills at play this time :)

[@JamesSharmanExtras]

Thanks Gaz! This is really taking me back to the earliest things I was doing in game dev.

[@jimmy21584]

By coincidence, I was looking at the original iD Software Hovertank rendering code this week, and comparing their renderer development all the way through to Doom. Doing a similar renderer but in 8-bit is just as ingenious!

[@JamesSharmanExtras]

Many of my decisions were influenced by register limitations.

[@R.Daneel]

I thumb-up'd so fast, I think I may have sprained something. (An aside- the "next video" card that pops up for me during the outro covers up the last 6 of your Patreons after a second or two. At least on PC/Edge.).

[@JamesSharmanExtras]

Thanks Al! I do need to plan the end screen better but I'm still an amateur at the youtube stuff!

[@R.Daneel]

@@JamesSharmanExtras Don't plan too hard. KZbin is watching and will move everything the moment you get it just right. If it's easy, I'd just randomize the list from time to time. Then no matter what mess KZbin makes of things, folks will get their day in the sun.

[@CeDoMain]

Really cool James!!!

[@JamesSharmanExtras]

Thanks Ce Do!

[@petermuller608]

Great video! One point I seem to be missing is the purpose of convex rooms + portals instead if allowing concave geometry. Is it used to reduce the number of collision tests during the ray casting phase? Doing the recursion on portals seems to be more expensive then doing direct checks on all walls

[@JamesSharmanExtras]

This is not a ray casting engine. In a convex space there is never overdraw.

[@petermuller608]

@@JamesSharmanExtras I thought ray casting was used for z-depth calculation? Convex spaces meaning no overdraw is clever, thanks for the insight!

[@LuaanTi]

@@JamesSharmanExtras I've got a Build-like software 3D renderer that has concave geometry with no overdraw, but it's certainly one of the very complex parts of the engine and not really worth it for the slight simplification it gives the level designer, especially for levels as simple as these. Of course, since my engine can load actual Build maps, I didn't have much of a choice - splitting the sectors automatically on load is even more complex than just handling wall ordering in a concave sector :D Even then, it's hard to overstate how amazing it is having virtually unlimited memory and dynamically allocated memory at that; a lot of the complex algorithms become very simple when you can use things like hash sets. In the modern day on modern CPUs, we're back to having the by far most bottlenecking part being memory access around pushing the pixels again :)

[@TrollingAround]

Really enjoyed this, thank you. Adding zone height and depth shouldn't be too tricky (and definitely worth doing now rather than later if your going to do it at all ;-) )

[@JamesSharmanExtras]

Glad you enjoyed it! But don't underestimate the effort of different heights. You loose some of the optimizations I was able to employ here.

[@paulwratt]

@@JamesSharmanExtras Told ya - "but can it run Crysis" :)

[@jimadams7765]

Resolution. Yes please. Have you experimented with the affect on frame rate? I think that would be an illuminating path. (or curve - frame rate versus rez???).

[@JamesSharmanExtras]

The effect is actually very predictable. The clipping and collision code would be unaffected. The various rasterisation steps would be multiplied up by a change in resolution proportionally.

[@DavidDrury90]

This could be an incredible introspective and helpful look at how to accomplish 3d like visuals with good performance on the 6502 or maybe even z80 based machines. Granted cycles are an order of magnitude slower but machines like the commander x16 that the 8-bit guy is doing which are essentially massively overclocked 6502s could benefit! From what I'm gathering with your implementation of your engine I feel like it has a little bit of Build DNA buried deep

[@JamesSharmanExtras]

Be cool if it’s handy to someone!

[@taiwanesestandardtime3388]

You're super fucking smart, there's no other way to say it

[@JamesSharmanExtras]

Thanks, hope you are finding it interesting!

[@TheEmbeddedHobbyist]

I was more advanced at school, instead of ax+b = Y we started with mx+c=y, see m and c are further up the alphabet than a and b. 🙂

[@JamesSharmanExtras]

If you use random Greek letter's it's even more advanced!

[@Bobbias]

@@JamesSharmanExtras I guess that makes APL the most advanced programming language

[@skilz8098]

@@JamesSharmanExtras Instead of y = mx + b we can use trig substitution: y = tan(t)x + b. It's the same equation as long as the angle t is the angle that is between the line y = mx+b and the +x axis. This is possible since m is defined as (y2-y1)/(x2-x1) which is the same as dy/dx. And dy/dx = sin(t)/cos(t) = tan(t). And the vertical asymptotes of tan(t) is the reason why y=mx+b can not draw, map or define vertical lines.

[@JamesSharmanExtras]

@@skilz8098 that still wouldn't map to fixed point arithmetic.

[@skilz8098]

@@JamesSharmanExtras I wasn't claiming that it would. I was just stating that mathematically you can.

[@LeeSmith-cf1vo]

Love a good binary chop 😄

[@JamesSharmanExtras]

Such a powerful yet simple technique!

[@fintux]

I hurt my jaw while dropping it watching this video.

[@JamesSharmanExtras]

Glad you liked it!

[@caspronauta]

Have you considered writing a compiler for the architecture?

[@JamesSharmanExtras]

It would be nice, but a lot of effort to generate good code

[@paulwratt]

Does this mean we might see "Blitter add-on Module" for the VGA board? (I cant remember if the CPU can do a GET _and_ PUT in the same cycle).

[@JamesSharmanExtras]

Only one memory access per cycle (But the vga has separate access to it's own memory).

[@u9vata]

Awsome algorithms. I actually use the simple a*x + b equation with special casing the verticals and I was shoked to find with that representation various optimizations can happen. But have no idea about the precision because I do that on new computers in a 3D web app where it is stable enough. Is there other issues with precision stability than the verticals and close to verticals? Because handing them as special cases actually make for algorithms where I can early-exit in ifs and run fewer computations (for example for intersection calculations) with added cost of more branching with reasonably good branch prediction being possible it seems. Just interested as maybe you can just tell that "regardless of special casing the verticals, the representation is still shit" or "in that case its ok"... Where to look for reading materials to get good at creating equations like you did here for the line equation version that is numerically more stable? Would never do these kind of things easily myself, but approximating like you did in the clipping I know for stability, but that is an algorithmical and not so much maths solution to the similar issue. Is it just creatively knowing calculus stuff to apply here or is there some lore with these kind of things to read around? Of course this video itself is such a lore ;-) Awsome work again!

[@JamesSharmanExtras]

I may have to do do a video at some point on mathematical precision and how to work around it.

[@BPJJohn]

Show this to John Carmack, I bet he would be impressed.

[@JamesSharmanExtras]

Be nice to know what he thought

[@GeorgeTsiros]

Are you considering a bigger cpu later on?

[@JamesSharmanExtras]

I actually have plans for a couple of future devices. I’ll probably do another smaller build before doing a big one.

[@GeorgeTsiros]

@@JamesSharmanExtras it is very difficult to go above 8bit for homebrew. You _may_ want to take a look at the internal architecture (well, "architecture" is not really the right word) of the CPU used in the hewlett packard hp28, hp48 and hp49 calculators, the Saturn. It has _64_ bit registers but only a _four_ bit wide data bus and a 20 bit address bus. So while it can do 4, 8, 20 and 64bit wide integer arithmetic in registers, it's basically like... moving the loop you would do in assembler if you only had tiny registers... inside of it. I have an altera de1 from my days at the university. _if_ I manage to make quartus work on windows 11, I just might start experimenting. (Yes, I know it is wildly different from what you are doing)

[@JamesSharmanExtras]

Join us on Discord: discord.gg/jmf6M3z7XS Support the channel on Patreon: www.patreon.com/JamesSharman Check out the original “Will it Run Doom” here: kzbin.info/www/bejne/hXqZgmSoZrmrq6M

[@paulwratt]

pinn this and delete "this"

[@paulwratt]

I can see a few "nerds" making that src into a complete game :) Hell, I can see someone trying to apply Z Height to the map - "But can it run Crysis" :) _And_ if there is a way to network 2 or more simulators, Mulit-Player (ala Midi Maze) .. Hell, maybe some one might even try to figure out a map data compression algorythm (ala Elite) to allow a Map Pack. "The future's so bright, I gotta wear 8bit shaders" :)

[@JamesSharmanExtras]

I did pull a lot of tricks to get this working, significant rework would be a lot of effort.

[@holderbee7811]

From my experience, a jankier environment simply requires a little jankier solution

[@JamesSharmanExtras]

It works!

[@Jkauppa]

have you tried an fpga version

[@Jkauppa]

use proper ray casting

[@Jkauppa]

corrected eye rays, not angular stepping, pixel stepping

[@Jkauppa]

any shape drawn with vertical lines, even floors, ceilings

[@Jkauppa]

z-buffer to render overlapping primitives (with vertical lines)

[@Jkauppa]

vertex uv textures stepping in the vertical line

[@twobob]

2d portal bits smells like quake.

[@twobob]

yeah excellent job.

[@JamesSharmanExtras]

I do have the advantage of 20:20 hindsight on all the various techniques used in games over the last 40 years.

[@twobob]

@@JamesSharmanExtras You are chucking around a really lot of stuff on very little. It was hardcore innovating like this that made modern games even possible. My hat is fully doffed.

[@EnjoyCocaColaLight]

What language is this?

[@JamesSharmanExtras]

The programming? Assembly language.

[@EnjoyCocaColaLight]

@@JamesSharmanExtras You write directly to assembly? Not C, python, Java... just straight up assembly? How tho?!

[@mikafoxx2717]

It's his own homemade cpu.. a C compiler would be a LOT more work to write.​@@EnjoyCocaColaLight

[@csongorszecska]

Holy cow, you are putting way too much effort into making these videos! I like it, but kinda worried that you'll burn out from this.

[@JamesSharmanExtras]

Thanks! I’ll be ok, I’ve slowed down a bit to make it manageable.

[@twobob]

I wish claim my Warranty on your faulty spelling of waranty. Presuming it was [sic] ;)

[@JamesSharmanExtras]

I'm Dyslexic, you have to accept the odd misspelling from me

[@twobob]

@@JamesSharmanExtras I did actually know that and almost (being spectrum myself) deleted the comment fearing upset (I seem to be able to upset people without even trying) but you misspelled Warranty and that was just plain Funny given the context :) Hopefully I didn't effortlessly manage to upset yet another person :D

[@paulwratt]

Some might say Computers are Dislexic Friendly - you, me, and that guy over there programming games and creating hardware from scratch ..

[@twobob]

@@paulwratt yeah, and very hard to offend :)