I have been playing Counter-Strike: Source off and on since its release in late 2004. Gameplay largely consists of playing the same short scenarios over and over against different opponents. Over the course of hundreds of hours of gameplay, everything from tiny obstructions in the game levels to the feel of the recoil of each weapon is inevitably memorized and incorporated into players’ muscle memory. Players continually search out better tactics, tune their game client configurations, and generally try to develop a better feel for the Source engine.
I say all of that in the hope that with the above introduction, the next sentence won’t seem overly bizarre: I’ve been wondering for years about the most efficient way to climb a ladder.
Typically to climb a ladder in a first-person shooter, the player (1) walks forward into the ladder while looking up. But what happens if you (2) back into the ladder while looking down? What happens if you (3) strafe sideways into a ladder while facing off to the side? What happens if you (4) face 45 degrees to the right of the ladder and then walk diagonally forward and left? In the case of the Source engine, 2 produces the same upward movement as 1, 3 produces no movement, and - I found - 4 produces up to 142% of the upward movement of 1 and 2 depending on where you’re looking vertically.
To get exact times for each possibility, I created this test map (screenshot) with the Source SDK. The idea was to climb the ladders with each technique, record the climbs, and examine the video to get the exact time for each climb.
Unfortunately, the second variable in play - the vertical angle that the player is facing when they climb the ladder- has a huge influence on the speed of the climb. What I really want is to rank the times using the optimal vertical angle for each technique. It would be extremely difficult to determine the optimal angle and control it experimentally, so I cheated!
Because of the game’s physics model, if the player gets up to speed and reaches the top of the ladder, then he or she will sail upward a short distance past the top before falling back down. By trial and error, I determined that it’s impossible to clear more than 53 units using techniques 1 and 2, and it’s imposible to clear more than 105 units using technique 4. Those maximum distances can only be cleared at very close to top speed. So I jump around trying to find the optimal vertical angle which will clear the first height at the bottom of the track. Then I let go of the mouse and record a climb the rest of the way up at top speed!
Here are some recordings of the forward and diagonal methods. It takes about a minute to find the exact angle where it works, but I cut that part out.
The final results: technique 1 and its variant 2 climb at about 281 ups (units per second), and technique 3 and its variants climb at about 399 ups. That’s 42% faster!math 24 May 2012
The Fibonacci sequence is:
Each term is the sum of the previous two terms in the sequence. Terms in the Fibonacci sequence are pretty easy to spot. An interesting property of this sequence is that it works as a mnemonic for converting miles to kilometers. For example, 21 is followed by 34 in the Fibonacci sequence, and 21 miles is about 34 kilometers. Likewise, 34 is followed by 55 in the Fibonacci sequence, and 34 miles is about 55 kilometers.
Why does this work? The short answer is that the Fibonacci numbers grow with , and is approximately the conversion constant from miles to kilometers. More exactly,
The value of is about 1.62, and 1 mile is about 1.61 kilometers. So successive terms in the Fibonacci sequence are approximately converting miles to kilometers! And, of course, to convert in the other direction you simply look at predecessive terms.
A couple of techniques are useful for when the number you want to convert isn’t exactly a Fibonacci number. If you want to convert 17 miles to kilometers, you could look at the conversions for Fibonacci numbers 13 and 21 and try to interpolate the answer. However, since 34 is a Fibonacci number you can get a much better answer by converting 34 miles to 55 kilometers and dividing by 2.
You could also change the initial conditions of the recurrence. A Fibonacci sequence with general starting conditions is called a Lucas sequence. Because when solving a linear homogeneous recurrence relation the starting conditions don’t affect the relation’s characteristic equation, a Lucas sequence also grows with , and the mnemonic applies. So you have more data points to work with if you also memorize, for example, the sequence:
For more mathematical coincidences, see the Wikipedia article.puzzle 03 February 2012
GitHub provides a great service called GitHub pages, which allows you to host static web sites from GitHub servers by simply pushing a repository containing the content. GitHub founder Tom Preston-Werner wrote a fantastic blog platform called Jekyll to fit this hosting model. Blog authors can write their posts in Markdown and Jekyll will render the posts to HTML and generate an entire site structure of static pages suitable for hosting with GitHub Pages. It makes sense as an architecture- if not for user comments there would be no reason at all for having a whole scripting lanugage and database engine behind an otherwise static blog. Of course you’ve probably guessed that this post is published through that system. The complete source code and some comments about setting up your own blog are available here.
Besides playing with GitHub, I’ve also been working on my reading list over the break. Other than fiction, I’ve been reading through some textbooks which I have been fortunate enough to recieve for free thanks to financial aid. One of these books is Introduction to Algorithms (in my classes we used Manber and Kleinberg & Tardos instead), which I have discovered has some excellent exercises- perfect little puzzlers for a blog format! Today’s puzzle is based on exercise 9.3-9 in the 3rd edition.
A number of well pumps have been built in arbitrary positions throughout a region. An east-west pipeline is to be built through the area. Connections will run north-south from each pump to the nearest point on the main pipeline. Your task is to decide where to place the pipeline so that the total length of connections that need to be laid is minimized. An example region map is below; click the image to expand it.
The example above is, in fact, a solution- you cannot find a better place to put the east-west pipeline. So how do you find an optimal position in general, given the coordinates of each pump?
You might be tempted to suggest that the pipeline be placed along the mean y-coordinate of all of the pump stations. It seems to be clear that the pipeline should be laid roughly through the center of the constellation of pumps, since we’re trying to minimize the distance to each pump. This geometrical intuition turns out to be wrong in rather the same way that our as-the-crow-flies pathfinding intuition is wrong in cities- the unusual way of accounting for distance foils the obvious solution. I hope that examining an example of using the mean will convince you that the mean doesn’t work; click the image to expand it.
The correct answer is to use the median of the y-coordinates. The easiest way to see why this works is by considering the case where there are an odd number of pumps, for example 5. The median, then, is the latitude line through the third pump sorted by y-coordinate. Say we move the pipeline from the median to just one meter north of the median. Then the lengths of two vertical connectors (to pumps 4 and 5) will decrease by one meter, and the lengths of three vertical connectors (to pumps 1, 2, and 3) will increase by one meter. In sum, the total length of pipe will increase. The same thing will happen if you move the pipeline just one meter south.
If we have an even number of pumps, say 6, the solution is that the pipeline can go anywhere vertically between pumps 3 and 4. It should be clear that you can move the pipeline up and down within that range without changing the overall total length, because three vertical connectors increase and three decrease in lockstep. It’s only when you move outside of that range that an asymmetry appears.