It‘s still interesting to see how certain challenges have been solved back in the day.
Or as a case study in what _not_ to do today. For example, Quake‘s ingame console commands were stored in a linked list. I believe looking up a command was a linear search through that list. You wouldn‘t do it like that today.
> For example, Quake‘s ingame console commands were stored in a linked list. I believe looking up a command was a linear search through that list. You wouldn‘t do it like that today.
Sure you would! You think those dinosaurs like Carmack didn't know about tree-like structures and hash tables back in the 90s? They did, it is just that (I assume) their main goal was to optimize something that is computed every frame, not once in a blue moon when player inputs a console command, which latency doesn't matter that much anyway whether is is 1ms or 10ms. In fact, toying with advanced data structures for console optimization sound like something junior engineer would get reprimanded for by seniors, if caught up wasting time on it.
I don’t know about quake, but in quake 2 it consisted of a big list of:
else if (strcmp(cmd, “somecmd”) == 0)
somecmd()
I remember reading it at the time and being inspired by the simplicity of it. It didn’t need to be more complicated than it was, and so Carmack didn’t make it more complicated. That was in stark contrast to a lot of the object oriented c++ design stuff that I was also reading at the time.
So much of the quake 2 game source was like that. Beautifully straightforward code.
The example sounds like a quite basic insight into algorithmic complexity or complexity of lookup operation of data structures. A linked list is fine, if you need or want to go through the entries sequentially anyway, but if you need random access, then you probably want something different. I can tell that without ever having looked at something like Quake's console commands implementation. However, it might have been the case, that there were not that many commands anyway, so that the linked list did not noticably slow things down.
> it might have been the case, that there were not that many commands anyway, so that the linked list did not noticably slow things down.
Also, unlike the game code itself which has to finish running its work in time for every frame, it probably doesn’t matter if running a command from the Quake terminal takes a little bit extra time.
Would anyone notice or care about a difference in the amount of time it takes to run the /noclip command for example, in a O(n) vs O(1) lookup of the command in the probably short list of available commands? I don’t think so.
Speaking for myself, if I bring up the terminal in a game like quake to run a command, I’m probably standing stationary somewhere out of danger at the moment. And the amount of time I spend to tab open the terminal and type /noclip would be much greater than the amount that the game then takes to look for that command in its list of commands.
> Also, unlike the game code itself which has to finish running its work in time for every frame, it probably doesn’t matter if running a command from the Quake terminal takes a little bit extra time.
Except we did, because back then, the console command loop was part of the work done every frame - so your lookup still had to fit in the budget, or the player would see frames being skipped. Which, if memory serves me, happened as far as Quake 3.
Here's another important insight about how games were written back then: they were single-threaded. Rightfully or not, the cost of context switching was seen as too big, so everything was run in a single thread - maybe with an event loop (what kids these days call "async") thrown in for convenience, especially around UI. The games that did use threads, would use a small amount of them to offload some work that wasn't strictly frame-bound, or when outside main gameplay (e.g. in menu). I actually can't think of any game from that era, which would run multiple threads during main gameplay.
And sure, you can adapt the console with your linked list lookup to run on the event loop ("async"), so it would e.g. do a fixed number of search steps, then yield, and resume next frame. But the code for that would get much, much more complex than replacing a linked list with an array, even if you then also replaced linear scan with binary search.
So one other thing about games back then: things were much simpler, and skipping frames wasn't that big of a deal-breaker. Multiplayer wasn't so popular, there was nothing you could honestly call physics code - which would explode if you skipped frame without compensating, etc. And players were used to getting anything from 6 to 60 FPS, depending on hardware they owned. These days, a game console blocking main gameplay thread and causing frame skips, would be unthinkable.
Single threaded kind of makes sense for machines with single core CPUs. And multiplayer was usually limited because internet wasn’t that good typically being dialup.
Games required more cutting edge machines (maybe 2 years old) I remember getting a notebook with enough power (66mhz, 4 megs of ram) to place doom. Taking my machine to a friends and playing one on one death match over a serial cable.
But you were not typing a console command each frame didn't you? A spike of 0.X ms when you type a console command and hit enter won't be anything to worry about
The game studio I did did many many things in linked lists or arrays still because literally searching an array is still much much faster than computing out hash algorithm when the total number of entries is less than a thousand and it gives you memory predictability. So generally when you're searching it almost all of it has been loaded into RAM especially if you limit the size of the items in the length list which games almost always do and you list limit the size of the array which games almost always do almost everything in a good game engine is fixed size arrays for repeatable performance. I was surprised by this as well when I moved from doing Ruby and Java apps into AAA game studio but the engineers were kind and explained it to me and showed me the math and I was like yep that is way faster. I also didn't appreciate the things like cash coherence that they highly leveraged to make every frame sing
Intrusive lists are not bad. Building one does not require heap allocation unless the object itself is heap allocated. I can imagine this being case for a list of console commands, just a bunch of static allocated structs in various places tied together via intrusive list. In fact we (abother game company) are also how are doing it today as well
As for the linear search, it is just console commands. User types it and then it makes a search in what, a couple hundred entries at most? Sounds perfectly fine
Does Quake 3 also use a linked list for the console commands? That game even has command completion, whereby pressing tab after typing a couple of characters, the console fills in the command you most likely wanted. The console in Q3A is extremely fast IME.
I wonder how many people still program modern game engines? Sometimes it feels like everybody just take the newest release of the Unreal Engine and drops assets and scripts into it.
Just to be clear, I am not saying that there are no alternative engines, just that these things are so complex that there are very few people, who dare to compete with Unreal.
Most of the old engines have been modernized. IoQuake3 for Open Arena, Doom3, even the Quake 1 src it's not the same as the one ID released. And I am not talking about DarkPlaces, but QuakeSpasm, SDLQuake...
