Better Quake strafe-jumping with genetic algorithms
Вставка
- Опубліковано 10 чер 2024
- In this video I write a bot to speed-run Quake's 100m level by reverse engineering a human's run and improving it using genetic algorithms.
00:00 Introduction
01:00 Demo files
03:20 Physics state updates
05:28 Input recovery theory
06:58 Genetic algorithms
08:57 Recovered human WR inputs
09:51 Optimizing a bot
10:45 Results
12:14 Future direction - Ігри
As noted in the video, the 9.688 s demo I refer to as the world record actually got beaten a few days before I finished this video. It was too late to go back and re-do everything so I left it as-is. A couple of other notes and caveats for Quake experts:
- I didn't mention cl_sidespeed / cl_forwardspeed for brevity / clarity reasons, however I actually recovered these values (or rather their ratio) from the demo too by including it as an optimization parameter. Similarly, I added it as a parameter for my strafebot optimization. The demo value is cl_sidespeed 1400, and the bot selected value is cl_sidespeed 1515 (both assuming a cl_forwardspeed of 800). If I fix cl_sidespeed to 1400 my bot gets 9.580s, about 0.04 seconds slower than it does with 1515, but still about 0.1 seconds faster than the old human WR.
- I'm not sure if the 3-turn method is already known. I'd love to hear from any top speedrunners if they've tried this already, and what they found.
By the looks of file types that quake use and other small details, cs 1.6 runs on same code. Cs 1.6 had bhopping and long jumping, long jumping is similar but it takes sometimes seven strafes to jump, only difference that i see between cs and quake is that in cs once you start bhopping you let go of w key and just use a and d keys alongside mouse inputs
@@kamolzaaliite 'runs on same code' is still too big of an assumption to make. Valve might definitely have altered certain physics constants which in turn could make strafes per hop more viable for humans compared to quake
Not a speedrunner, but in DM, i sometimes use 3 turn instead of my usual 1 turn.
Did you try 4 turns? How many turns are possible if you don't try to play like a human at all and where does it stop giving advantage?
im sure the speedrunning community would like it if you could use this data to write a demo player movement verification tool, to help weed out the cheaters
I'm sure skynet wants IFF technology
and DON'T think we don't know how to weeeeed 'em out!
Of course the community can weed out cheaters, but automated tooling to reduce the burden on mods is always appreciated 😄
@@hoo2042 i think bro was makin a reference to the spongebob movie or im just dumb asl
These videos deserve a significantly larger audience. The work you've put into them shines through.
I wouldn't bat an eye if this video had 7 million views instead of 7,000. This stuff matches the production quality of 3Blue1Brown. Absolutely fantastic. Keep up the good work.
Kind words but this was recorded with the same microphone he used when Quake was released.
You should also see HL/CS jumpers as their techniques are more complex - they turn multiple times
CS jumping is so ugly compared to the Quake games.
Floored, FLOORED that you one-upped your previous work. Loved the wiggle worm and fascinated by the part about reversing a quantize operation. SO cool!
I don't know anything about computer science or algorithms or anything...but I did play Quake 3 a lot when I was younger. Your videos have been a great source of education and entertainment. I hope to see more videos in the future. Going to enjoy this one now
I understand that these videos must take a long time to make but just gonna say that I think that if the uploads were more regular your channel would explode for sure, you've got the quality of production nailed completely.
I love your videos always so interesting
This is amazing, and the presentation is outstanding. Well done!
I don't play speed jump activities but I do enjoy watching them in not too lengthy batches every now and then :). I used to play quake 3 in 1999 and 2000
Fascinating. I'm not into competitive play, and I wasn't aware of strafe jumping. But I was aware of airborne turn velocity, and I always do 'wiggle jumps' when attempting to cross large gaps.
Such a good quality breakdown of your process and paired with great video editing. Keep up the great work!
Very enjoyable video, as always. I would be surprised if people didn't try fitting in more strafes per jump to get a better trajectory, but the difficulty increase is massive. Just fitting in 2 strafes with proper power bunny hop technique took dozens of hours for me and my best time is still far from the record (9.98).
I was so hoping that you would release videos. Also this one is one of the best videos I've seen in a long time on the internet.
Quake, Code and examples. I really hope to see more content from you.
Doesn't have to be Quake tho. But the stuff with how demos work, and how to work with them is really really awesome!
You make me wanna code again hahaha
Engineering at it's finest!!
Adding more strafes has long been known as a way to gain more air speed, it's just the risk of messing up the extra strafes is commonly accepted to be not worth the speed. There's actually an entire long-jump community in CSGO dedicated to seeing how much speed one can gain during a jump with successful strafes, measured by how large of a gap you can cross in one jump. The reason being, this skill actually has practical use on some maps
Amazing channel. Am looking forward to binging your videos this weekend.
Fantastic visualizations and impressive results :) I love all your videos
I'd love to see in-eyes view of the 3-turn method
absolutely incredible video. I'm jealous of your analysis skills. Like seriously fucking blowing my mind. This is the sort of stuff I wish I could do at my computer.
Loving your videos man
Great video, thanks for doing this. I would be interested in seeing the complete code.
Wow! Very fascinating!
Would be interesting to see what happens when you go to 4 or more turns per jump. Wouldn't that using the same argument as going from 2 to 3 also improve time? You probably hit another barrier at some point, but when does that happen? Would probably be even harder for a human to execute too.
I did actually try this --- you get into diminishing returns quickly (maybe 0.01s saved, but for a big increase in difficulty)
I think that's why tool assisted Quake speedruns jitter left/right all the time: performing many many turns per jump is technically speaking the most optimal strategy lmao
@@MattsRamblings Oh that answers my question. Very cool programming here. I didn't realize this was 2 years old when I saw it. Amazing content, beautiful animations, loved seeing the 3 turner pull ahead.
i love your videos, please upload more
Loved it, thanks.
Amazing work! Damn, I need to get back to CPMA.
This is fascinating....You should make a 3 minute version of this called "REVEALED! Who is faster: Quake Guy or Wild Cheetah?" and do a scale experiment of the 2 running in split screen...that's the viral video to pull in the audience, then add this video to the outro card, description etc.. so people get the quality behind the quantity, so to speak. You can do follow-ups like Quake Guy vs Doom Guy, Quake Guy vs a Chocobo, Quake Guy vs Corono Virus etc....(this is all tongue-in-cheek ofc)
absolute gem, shame this didn't take off.
Great stuff, I've wanted to see someone do something like this for at least 10 years :) e2m1 might be a good first non-trivial one to try?
You're a genius.
cool video. you're right that adding another directional change per jump increases speed, 2 strafes per jump is most common across flat terrain because more strafes in a given jump means more opportunities to have slightly less-than-perfect inputs which cost speed, increase total travel distance or both. autostrafe TAS tools/cheats simply change direction every server tick. ps i'm not a speedrunner so idk if they might have a different reason, just a casual bhop player
You should use the number of strafes as a parameter so that your genetic algorithm has the potential to optimize its airpath and gain
nice videos
stop blasting dubplates
Good. You've entertained me. Now make a video covering Slash's physics in Quake Champions :D
This is so cool, amazing work. Are you planning to open source the code?
Is Carmack actually god though ? like.. he came here to make this game to show us that we're playing a game just like it
Quantum phenomena are just data availability, why compute for noone etc..
Fucking legend keep it up :)
Great vid but I really wish you had shown the 3-turn from first person view
How does the three turn strafe jump look from the players viewpoint?
Nice
Is there a possibility of miniscule frame time variations tampering with the results? I know from experience that forcing higher frame rates significantly impacts the player's speed. Do WR entries always use fixed time steps?
Good question. The Quake speedrunning rules stipulate that cl_maxfps is between 10 and 72, which is enforced server side. This allows some scope for speedrun tricks, and in fact, the most recent WR (9.633s) uses a trick where they set cl_maxfps to 10 right before touching the level exit trigger. There's normally a 100ms delay between hitting the trigger and the intermission being triggered (which is what counts as the finish time), however, as I understand it, limiting the framerate in this way means the delay is completed within the same frame, and so you can save around 0.1 seconds with this trick. Comparing the two demos shortly before the finish shows that in fact the current WR is slightly behind the old WR at the point of crossing the line.
2021: it's time to improve on quake 1 speedrunning
If you want a better explanation on the strafejump speed acceleration techniques, I recommend watching half life speed runs with the scripts they use to gain maximum speed.
Do you have any videos of your/a 'humanized' bot completing a Defrag map? I've seen a non-humanized one during a Defrag tournament, but I have wanted to see one performing something that could potentially be done by a human (not cyborg.)
Unless I have the biggest human brain, a 3-turn puts more moving parts on top of Power Bunnyhopping. I'm not saying it's impossible, for me I'm just getting started with Power Bunnyhopping. A 2-turn is already proven to have a lot of moving parts, but that may be the fact that I've burdened myself by learning the standard Bunnyhop with QuakeWorld Physics first. QuakeWorld Physics completely throws the forward key out the window when you land on the ground and makes movement as effective as your framerate is. I've had 8 seconds in 100m with QW-Physics, so, this might mean we've got a ways to go in Vanilla (maybe anyways).
Instead of genetic algorithms for reversing the inputs, how about a breadth first tree search starting from the first frame? I'm not familiar with the technical details, but I imagine after a few hundred frames all the previous inputs up to a certain point (or at least the high precision coordinates if they are truly ambiguous) would get "locked in". This would also solve the problem of monsters, switches etc. when applying the technique to more complex demos.
I'm probably misunderstanding you, but isn't the problem that with a breadth first search you have an exponential explosion of permutations it has to try out to determine the next optimal input? If you just limit it to determine a very limited number of input like 100 then you risk it getting stuck in local optima, so on a path that only seems ideal because it isn't able to do long-term strategies, no? I guess most Quake levels are linear enough for BFS to work.
@@sanderbos4243 We're talking here about the process of reconstructing the input key presses from the recorded position data. All positions are only dependant on previous key presses so if you can reconstruct the earlier ones first it makes it a lot easier.
While it's true that BFS will expand exponentially, because of the sequential nature of the input sequence I believe you will be able to aggressively prune the tree very quickly, as the earlier inputs get "locked in".
@@jamesflames6987 Gotcha, I somehow didn't see the "for reversing the inputs" in your original comment's first sentence. Very good idea!
Hope the algorythm picks this one up
ugh i'm too impatient to listen to the technicalness''''''... hahaha i remember learning bhop when it was brand new to cstrike... i'd be in the opponent's spawn before they were done buying weapons. i wish i had demos in order to share the sheer, ecstatic joy of the experience ♥
how do you make these videos :O
Is the client's camera roll value ever not 0 in quake?
why is quake 3 strafing so much diff than this?
I'm sorry but what does quantizing mean
isnt quake 1 10fps in netcode and demos by default??
10 fps was an animation framerate in q1, before people was able to modify source code and increase it using interpolation. 72 or 77 server frames per second are a standart now. Mvd demos contained 19 fps somehow...
if you could do something like that for my 100m world record in quake3 (map name is un-dead!021), that would be great.
Disappointing that it took youtube two years to show this to me
ezPotat
its 4 27 am for me and my last 2 woke braincells try to process what is going on. but you are insane.
this is some harry potter shit
read a new book. ANY other book. just something else. for the love of god
Nobody! I said, NOBODY will ever tell me that Python is slow...
this is the peek of nerd stuff
Watching an AI figure out what people figured out in the 90's is pretty hilarious.
I'm sorry but Genetic algorithm is absolute garbage. Not sure why you would choose it over a variety of alternatives.
Cuz it works and it worked here?
Your mouth sounds are unbearable.
I don't know how the movement works in this game, but in Valve games the velocity is constant when in the air. This makes me think that it could be possible to get a faster time by just letting go of the controls, and just travel straight forwards once you've reached a high enough velocity where it would otherwise be hard to gain any more speed. Could be worth trying :)
Yeah, there has to be a point where you're going fast enough, and you're close enough to the end, that the extra distance gained by travelling in a straight line outweighs the speed gained from curving. I'll add it to my list of things to try out, thanks!
Velocity is not constant in the air for valve games
@@Anon.G Perhaps not all Valve games, but at least Counter-Strike and Half-Life.
With sv_cheats set to 1, you can write cl_showpos 1. This brings up some information about position and velocity. You can see that the velocity stays constant if you're in the air while not pressing anything. This is also what makes b-hopping possible because the constant velocity is transferred into the next jump if you jump quick enough after landing.
@@ifroad33 showpos used to not need cheats for cs, and won't need cheats for half life games. Also you've changed one massive point, you said not pressing anything. Your velocity absolutely is not constant if you are air strafing. And that is not what makes b hopping possible
@@Anon.G I don't know if you got understood what I meant by my comment. I was talking about a strategy of reaching the finish line quicker by letting go of the controls somewhere close to the end, because then you could travel in a more direct line while maintaining constant speed. My explanation might have been terrible lol, but I think MattsRamblings understood what I meant in his response. Sorry if I was not clear enough in my explanation.