Quake 3 engine in Rust | Hacker News Reader

Quake 3 engine in Rust

github.com

183 pointsluu69 comments

Does anyone know if type parameters in Rust can be integers so that you could write vec<3> and get an optimized unrolled implementation of three dimensional vectors without having to hard-code as in vec2, vec3 and vec4, etc?

[1] http://static.rust-lang.org/doc/rust.html#type-parameters

[2] https://github.com/Jeaye/q3/blob/master/src/math/vec2.rs

[3] https://github.com/Jeaye/q3/blob/master/src/math/vec3.rs

[4] https://github.com/Jeaye/q3/blob/master/src/math/vec4.rs

What you're actually asking for is dependent types, where instead of passing in a type argument you're passing in a value you're asking to have lifted to the type system.

C++ implements this in their templates because templates are rather more dumb than what a "proper" type system would do, because templates are essentially what C++ uses as a powerful macro system. A "Vec<3>" in C++ then is instantiated as a separate class/struct. A "Vector<Int>", if allowed to do it is separately compiled from a "Vector<Double>"[1] and this is what has given templates an uncanny power in C++ as a method of doing very powerful transformations of code, as used by libraries like Eigen to unroll very complex multiple-pass algorithms into a single fast loop. Very neat stuff.

I would be a little surprised, actually, to see Rust implement the same feature because the way C++ has done it is by a rather curious and roundabout[2] and it was just happenstance that made it one the first widely used implementations of dependent types. It's strange to think about, but templates are one way C++'s type system is more expressive than Haskell's. (Wow, that felt strange to write.)

The associated constant idea is kind of neat, but the implementation of associated constants wildly differs from associated functions[3] and I find it difficult to imagine the way they operate having anything, anything at all to do with one another.

If they do implement their associated constants proposal, it'd definitely be something worth following from a type systems perspective because, well, dependent types are one of those things that are curiously difficult to implement, and if they implement it as part of a general type system, it could even be undecidable[4].

[1] This may not be the case now, but it certainly was the case in the past. So this statement is only true to the extent of "very simple C++ compilers" and may not be true of more optimized compilation strategies. I'm not sure what the state of the art is here.

[2] And theoretically unsound, in that the macro/template language is be Turing complete. That's not really very desirable from the perspective of being able to share code or doing "compiler as a service" execution where someone could upload infinite loops or non-terminating templated types. http://ubietylab.net/ubigraph/content/Papers/pdf/CppTuring.p...

[3] In C#, they're called Extension Methods, and they're an instance of the compiler simply being smart enough to find functions that say they can work just like a method of a type, but only depend on an already public API. Extension methods are great because they let you turn regular C# generic types into Monads by adding implementations for Select, SelectMany, and so on and so forth. http://ericlippert.com/category/monads/

[4] Apologies for the link to wikipedia, but it's the most terse source on it that I can find. It should be noted that just because it's undecidable in some systems doesn't mean it's undecidable in all systems. Let us not make here the mistake of applying Gödel's Incompleteness Theorem to the reals. http://en.wikipedia.org/wiki/Type_system#Dependent_types

With ghc 7.4 onwards you can have that style of static dependent types very easily, and it's even nicer still in ghc 7.6 onwards. That particular flavor of dependent types is singleton types.

I'm actually leaning on the singleton types and type class machinery in ghc very very hard to write some numerical libraries with both a high level API and very strong code specialization guarantees.

A lot of the same stuff could be done with cpp Template programming, but I'd have to worry about a lot more code bloat, a much more inscrutable set of type error messages, and no hope of end users getting good type Inference.

There are a rich space of decidable type systems out there leverage some or all of dependent types. The work on idris is very exciting in my novice opinion.

There is not support for this at the moment, but one of core developers mentions one approach for starting to address this need in:

http://smallcultfollowing.com/babysteps/blog/2013/04/02/asso...

There would still have to be different hardcoded signatures and implementations for cross-product, transformations and "angleTo"-type methods that you would have to worry about, depending on how complicated your vector class gets. I don't know if there's really a good way to handle those cases generically. So keeping the classes separate might still make sense, even with that feature.

> There would still have to be different hardcoded signatures and implementations for cross-product, transformations and "angleTo"-type methods

You are right, those are great test cases for Rust.

The cross-product takes n-1 n-vectors are returns an n-vector (orthogonal to the n-1 inputs). The transformations are easy to generalize as affine or homogeneous transformations.

A nice features of Rust is that it has macros, so once it has dependent types creating these function with different signatures should be straight forward!

I'd hope that like C++, you would be able to add in any extra functions you'd need for specific dimensions.

I had the very same question. Why is the matrix type hard-coded 4x4 32-bit float?

If you are interested in reading further about BSP (Binary Space Partitioning) [1], check out the following chapters from Michael Abrash's Graphics Programming Black Book:

Chapter 59: The Idea of BSP Trees

http://downloads.gamedev.net/pdf/gpbb/gpbb59.pdf

Chapter 60: Compiling BSP Trees

http://downloads.gamedev.net/pdf/gpbb/gpbb60.pdf

Chapter 62: One Story, Two Rules, and a BSP Renderer

http://downloads.gamedev.net/pdf/gpbb/gpbb62.pdf

[1] https://en.wikipedia.org/wiki/Binary_space_partitioning

By the way, you can download Michael Abrash's Graphics Programming Black Book from here (it's out of print now): http://orangetide.com/graphics_programming_black_book/

There's also his Ramblings in Realtime here: http://www.bluesnews.com/abrash/

And gamedev.net also has the book here: http://www.gamedev.net/page/resources/_/technical/graphics-p...

Can someone comment whether if Abrash's Graphics Programming Black Book is still actual today? There are some reviews on amazon, from 1999/2000 mentioning that it is outdated. I guess some percentage could be still actual, of course. So I'm interested what percentage it is.

Some parts are still worth reading, but a lot of it is dealing with rendering without any real acceleration. Some of the low level parts on optimisation may still be worth reading, as are the BSP chapters, but you should read more modern books on optimising code, and on spatial indexing schemes of various types as well.

For the pure rendering side I'd say Real-Time Rendering (third edition) gives a good overview of techniques, but you'll want to look elsewhere if you want to see how those algorithms can be really optimised for a given API and GPU.

This is a great bit of nostalgia, not just for Quake 3 but because quite a while back (2000-2001-ish) I wrote a Q3 BSP format renderer for the Nebula Device open source engine, written in C++. Sadly the code seems to be somewhat lost at this point. I don't have a local copy of it and some cursory searches for it aren't finding much, I suspect it exists in some now-obsolete branch of an SVN repo on SourceForge, but don't care enough to really go looking. Surprisingly there is still a tripod page with screenshots:

http://gmcbay.tripod.com/

Anyway, great work so far! I am curious why you're doing BSP rendering if your goal is to have a destructible/voxelized-style world, since the two things are on opposite ends of the spectrum of mutability.

Thanks! I went with BSP loading first because I'd like to voxelize arbitrary Q3 maps. It's planned to be a feature of the game to be able to load in any Q3 or QL map and be able to destroy it.

I miss the Nebula Device. Nebula3 was really shaping up into something great.

Bruce Mitchener, I presume? I remember you from the days of hacking on Nebula!

I wasn't around by the time Nebula 3 came to pass, I actually didn't realize there was a Nebula 3 until I did a google search to see if I could find any of my old nebula code.

This is more like a renderer for the BSP map format. Still awesome stuff though, interesting to see how it progresses

Ah, thanks. From the title I thought that someone had single-handedly re-implemented all of Quake 3 in Rust, which seemed a bit implausible.

This is very cool, but I wonder why people are already inventing different indentation styles for Rust already. Guys, we have the canonical way all Rust code should look from the Rust compiler itself. Let's not all start using disparate styles just because we can like C/C++.

If you want One True Indentation Style for a language, then make it a part of the language, instead of leaving it to a style guide or an external program.

Having it externally can be an advantage in that it doesn't matter if you have an extraneous space when you type the code in because it will be cleaned up by the formatter, whereas making it part of the language makes that an error (and possible quite a confusing one).

It leaves space (pun intended) for bike shedding, or for inadvertently checking in code that voilates the coding standards. If you really want One True Format, then make it part of the language spec.

If a tool exists to format the code, it is of no consequence that a check in violates the formatting, as when that code is actually viewed it can (and should be) passed through that tool ahead of time such that the check in which violates the formatting guide lines is never actually viewed as such.

> Guys, we have the canonical way all Rust code should look from the Rust compiler itself.

The Rust compiler is in many different 'dialects' of Rust, since it's been around for so long. Parts of it haven't been touched in a while.

We're working on a general style guide here: https://github.com/mozilla/rust/wiki/Note-style-guide

>We're working on a general style guide here: https://github.com/mozilla/rust/wiki/Note-style-guide*
Better than that would be a goftm like tool, that applies the style guide.
People (including me) love that about Go. (I've actually never read a negative comment about it and many possitives).
It puts an end to all issues with formatting, really.
I don't know how reusable the parse is -- it would make something like this even easier.

There exists one of these built into the Rust compiler, but it's not very good right now. The process of creating an "official" style guide as per the above wiki page might help build the momentum needed to actually make the pretty printer usable.

Please see my comment upthread about rustc --pretty.
You can't figure out what a pretty printer should pretty print until the style is figured out.

This is inevitable with any language that looks like C. As there are already numerous styles for C/C++/Java that people have strong feelings for and they'll just carry them over to Rust.
My C++ style is identical to the first Draft ANSI C++ book I read. I've carried that style to Java and even to C (I hated pre-ISO K&R though mine looks now nearly identical to 1TBS). Heck, even when playing with Go, I used that style (gofmt be damned).
Now if Rust looked more like Python...

>This is inevitable with any language that looks like C. As there are already numerous styles for C/C++/Java that people have strong feelings for and they'll just carry them over to Rust.
Not really. Go solves this with gofmt.
You might insist on your own style (as you say) but for most people it's a command line away to format it in the standard way, and all GitHub projects etc will be gofmt'ed anyway.

Is it a new style? It seems inconsistent within itself... for example sometimes the code starts one a new line after the opening brace, sometimes it starts on the same line, sometimes the closing brace is on the same line sometimes it's not. I don't know enough of Rust to know whether this means anything or the coder is just being sloppy.

It's true; I fall victim of my C++ habits. A style guide is floating around the Rust mailing list; I see no reason why further code couldn't follow it more closely.

Good point. Need a rustfmt like gofmt in go.

We do have a pretty printer that we're planning on growing into a gofmt-like tool, but we still have a ways to go with it before we will be comfortable using it in an automatic fashion like Go.

I, too, feel that perfectly uniform brace positioning is one of the critical technical challenges facing any new language today. There is no longer any excuse to get such an important and fundamental advance wrong.

Sarcasm?
It may not be a "critical technical challenge" but if you are writing a new language there is really no excuse to not cement things like that down before it is too late.

No no, give developers something cosmetic to argue about!
If you don't they'll find something fundamental to be dissatisfied with. E.g., the lack of full TCO or a Turing complete type system.

Why do you want to force people to use your style? That's pretty much against the hacker mindset.

>That's pretty much against the hacker mindset.
I see how you would think so, but I lean in the opposite direction. If all programs in X language are written in the same style, you never have to pause to think about how to style something. This also means that you can quickly read other programs without being thrown by differences in style, and it's a great use-case for a tool that does the formatting for you. You can just write a quick example, run the formatting tool, and you won't have to pause next time. If you really can't afford the interruption, you can just skip formatting and run the formatting tool later-- though this is the sort of use-case that only occurs early in your relationship with the language.

Why do you want to force people to whatever style you want to read in?
There is a strong case for having one style: namely that now it becomes easy to understand aspects of a program at a glance (e.g. structure of flow, where you can gloss over for now, and where you have complexity) and also helps identify errors and on right away. Sometimes it's imperfect, but consistency is more important than "looks pretty".
Besides, if we're talking about the hacker mindset:
1) there are other languages
2) you can do amazingly complex and deep things with your brain, but you can't adapt to a style?
3) consistency and correctness is more important than "what I whimsically decide is neat looking today, no matter how many errors it is hiding".

My style? Not my style, a style.
And there would be no "forced" unless the reference implementation were to error when un-standard styles were used. I see absolutely nothing particularly "un-hackerish" about this. We standardize syntax and keywords, why not syntactical style?
You know what does seem hackerish though? Having tools that do mundane tasks (for example, formatting) for you so that you don't have to. Lisp, and lisp pretty-printers, also strike me as pretty hackerish.

Hackers are about creating things.
Arguing about "using your own style" with regards to braces and such is not hacking, it's bike-shedding.

So suddenly you decide what hacking should mean to me?
Sorry, but this thread smells of authoritarian people. I'm not really compatible with that.

>So suddenly you decide what hacking should mean to me?
Did you start this sub-thread saying: "Why do you want to force people to use your style? That's pretty much against the hacker mindset", ie telling us what hacking should mean to us?
To answer your question: no.
I merely restated what hacking means for everybody. Words have meanings built-in, individuals don't get to decide "what it means to them" and have that be accepted by other people (Else why even use the common word in the first place? Invent your own).
So, if hacking means "no standard syntax rules" to you (among other things of course), that doesn't mean squat to the general hacking population. Guido Van Rossum, for example, is as much a hacker as anybody, as are Python users, hacking in a language where indenting is enforced.
"Bike-shedding" is also well known, and is well known that syntax-style, brace wars and such fall under bike-shedding and/or yak shaving in Hacker culture, along with Emacs/Vi etc.
>Sorry, but this thread smells of authoritarian people.
Yes. Either that or people who couldn't give a flying duck for brace/common style wars, and have found by experience that not arguing about such things and having language standards make them more productive.
People that know that your "rebellion" and "creativity" have millions of interesting avenues to be exhibiting in the things you CREATE with your code, instead of in your brace style and such.
It's as if saying "I cannot be creative in this company/school" because they have a dress code. As if wearing some lame t-shirt or whatever makes one more creative.

I hope I am detecting sarcasm. I say use whatever the consensus is, but TCO is a much bigger issue IMHO.

Not perfect, but it exists:
$ cat > hello.rs fn main() { core::io::println("Hello"); } $ rustc hello.rs --pretty normal fn main() { core::io::println("Hello"); }

Why maintain the extra line?

It's a bug.

So from what I gather this is basically a wrapper around some libraries that renders a quake map, I've been browsing through and found very little code, which seems implausible for a game of such complexity.
EDIT: was there something wrong with what I wrote? This seems very simple for Quake 3 engine (based on my knowledge of 3D code and skimming the documentation). I've seen code is calling a lot into glfw and opengles libraries.

You are correct that it is very simple for a Quake 3 engine - the submission's title is misleading. Calling it "basically a wrapper around some libraries" is a bit harsh though. It's not like it's loading up libloadandrenderaquake3map.so! From a quick glance at the code it implements opening a .bsp file, representing it in memory, and rendering it with direct OpenGL calls. This is pretty close to the metal, so to speak.

It looks like pretty good progress! Are you going to be implementing the Quake Virtual Machine (QVM) architecture so that your engine can run the Quake 3 game and its mods?

The goal is to create a Quake 3 like game, but with a destructible voxelized world (Ace of Spades doesn't do it for me). As you can see, and as others have commented, this is currently only a rough BSP renderer with almost-complete TTF rendering. Q3 is the inspiration, but my goal is for this is to be a different game.

If your goal is a voxelized world, what's your reasoning for starting with the Q3 BSP strategy, and not something more like Voxlap?

I went with BSP loading first because I'd like to voxelize arbitrary Q3 maps. It's planned to be a feature of the game to be able to load in any Q3 or QL map and be able to destroy it.

Have you looked at how the Sauerbraten engine works?

I've not. I will though.

Any tips for rendering text? I'm doing a similar project for Quake 2 with Julia[1]. I haven't tackled text yet, but I probably will need to soon.
[1]: https://github.com/jayschwa/Quake2.jl

I highly recommend looking at signed distance maps for text rendering. Relatively easy to implement and gives very good results even when drastically scaling the text to different sizes.
Potentially useful links:
http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_...
http://www.gamedev.net/topic/491938-signed-distance-bitmap-f...
https://github.com/OpenGLInsights/OpenGLInsightsCode/tree/ma...

My TTF rendering code is based off the examples provided here: http://en.wikibooks.org/wiki/OpenGL_Programming

I will be keeping an eye on this for sure now.

Was anyone able to build this?
I got rustc 0.6 built and installed on my amd64 linux machine, but seems that this q3 codebase triggers some bug in the compiler ..

not 100% on topic, but as the author is doing his mod because he likes to have a voxelized and fully destrutable word: I remember Red Faction. Is there any in-depth review/interview on the technology they used at the time? Looked like "simply" carving out destructed structures from a polygon model; But would be interested in the details...

Why is this interesting?

Why is this comment necessary? You don't have to read code or links if you don't want to. This is even worse than the "how is this topic relevant to hacker news" style comment.
I found it interesting because it is a nice example of real, non-toy, code in rust. I presume others find it interesting because it is a good progress mark of rust.

The comment could be out of a genuine desire to understand what makes the code interesting. The brevity makes it a bit ambiguous.

No, the comment seems like the author being a jackass.
A genuine desire to understand would have used different questions altogether.

It is actually a pretty neutral and dry comment, which is not necessary a "jackassness". Also, this is not a one-to-one conversation, other people read these threads as well. So some of them, which are genuinely interested, could benefit from detailed answers.

>It is actually a pretty neutral and dry comment, which is not necessary a "jackassness".
Not really convinced. Even something like "In what ways is this interesting? Can you explain?" would be way more neutral than the current one.
If he was perplexed by something on the article he would ask more specific questions.
As it stands, it's identical to tons of other dismissive comments that follow every announcement. It wants to imply the author is "too technical" for this, e.g "hmm, a yet another 3D engine just done on some new language this time? who cares" or "why is this on top of HN".

Because its an interesting example of the status of the Rust language, which some of us may or may not be familiar with, and with such a starting point as a quake3 renderer, newcomers to Rust may indeed be encouraged to explore the features of the language.

Thanks!

Reply on news.ycombinator.com