Matthew Beckler's Home Page

Home :: General :: Software :: Hardware :: Microcontrollers :: Artsy Things


Solution to XKCD Velociraptors Problem #2

Original Comic:

XKCD Webcomic - Substitute

Introduction: After introducing my housemates to the wonderful webcomic XKCD, we discovered a quite interesting puzzle in the comic titled "Substitute." I have reproduced it on the right side of this page.

Problem one is fairly simple, and has already been solved on the XKCD forums. From a quick browsing of the XKCD forums, there's been some half-hearted discussion, but no analytic or numeric solution so far. My housemates and I decided to take on problem number two.

Solution Method: We created a numeric simulation of this situation in Java. We choose Java because it's easy to work with, and we were all pretty experienced with it. All our source code has been released under the GPL, so feel free to modify and redistribute our code.

Assumptions: We had to make some assumptions about the problem, and we also consulted with Mr. Munroe (The creator of XKCD) for further clarifications.

More Solution Information: Since the only characteristic of a human's behavior is the angle at which he runs, and the only measure of success is survival time, we have a relatively simple task, to maximize survival time by changing the angle. Since evolutionary algorithms are fun, and amusingly appropriate to this problem, we created a method for a human to 'reproduce' by undergoing mitosis, and introducing mutation to the run angle at this time.

Mutation Details: We initially start the simulation with 8 runners, facing E, NE, N, NW, W, SW, S, SE. We then take these eight 'parents', and mutate them 10 times, to produce 80 new runners. These 80 are the first generation. They are placed into the simulation, individually, and run until they get eaten. When all 80 have been evaluated, we take the 8 runners that survived the longest, mutate 10 children off each of those, which produces the 80 runners of the next generation. We keep track of the best time and best runner for each generation, and when we have gone 15 generations with no improvement, we end the trials.

Visualization of Results: Getting a single number out of a simulation isn't very believable, so we started dumping run data into a comma split file (CSV), for later analysis. We wrote a visualization application that could read those output CSV files, and provide graphical feedback. Here are two screen-shots, one standard, and one with 'trails', which show where each object came from. These images are from the same simulation run, and from the same point in time, at 2.08 seconds.

Visualization Without Trails Visualization With Trails

Video Results: If pretty pictures weren't enough, I (automatically) prepared a screen-shot from each of the 309 steps of this simulation run, and created a video of both with and without trails. Click on the screen-shot to see the associated video. Hopefully the videos work for your computer. The were created with mencoder from a series of PNG images. I think I created an mpeg4 video, so please let me know if the video doesn't work for you. Really, the videos aren't important, just kind of amusing.

Polar Plot of Survival Times

Results: As someone noted in the forums, there are actually two 'solutions', symmetric about the vertical axis. In our simulation, we found angles of 0.5694 and 2.5724 radians, or 32°37'27" and 147°23'15" gave the same results, a survival time of approximately 3.1 seconds. In other words, the solutions were (Pi/2)±1.0015 radians, or 90°±57.3877°. It's interesting to notice how the runner's angle seems to be closer to the injured raptor, until the very end, when the quicker raptor catches up, and they eat the human at the same time. Also interesting, is that the injured raptor's velocity limitation doesn't become a factor until approximately 2.5 seconds into the simulation, when all raptors have accelerated up to 10 m/s. After 2.5 seconds, the injured raptor is limited to 10 m/s. At the end of the simulation, the healthy raptors are only going about 12.3 m/s, less than half of their maximum velocity.

Source Code Download We have packaged our source code (5 Jana source files) into a tar.gz file, as well as a .zip file. You can download it below:
Velociraptors.tar.gz
Velociraptors.zip

Comments? This project was created by Matthew Beckler, Grant Miller, and John Saxton during their undergraduate years at the University of Minnesota. We would enjoy hearing comments on our work, so if you have any questions, concerns, or suggestions, you can email Matthew

Related Work:


Homepage Made with Vim! Validate HTML Email Me! Made with Inkscape! Validate CSS

Copyright © 2014, Matthew L. Beckler, CC BY-SA 3.0
Last modified: 2009-12-16 01:39:31 PM (EST)