Matthew Beckler's Home Page

Home :: Blog :: General :: Software :: Hardware :: Microcontrollers :: Artsy

---

Solution to XKCD Velociraptors Problem #2

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.

• The human will run radially outward in a straight line. This will allow us to characterize a run path with just the angle of the run.
• The velociraptors need to be very close (10 cm) to your position to eat you. The eating distance really only slightly affects the survival time
• The human has infinite acceleration to 6 m/s. This really would only effect the time slightly. The shape of the solution would not change significantly.
• The velociraptors can turn any angle at any velocity. This has a large effect on the solution, and was only implemented after consulting with the author, who said, "I actually remember seeing some research saying that Utahraptor may have sacrificed some speed in favor of quick turning ability, so there's some justification for that one. So I would say you let them turn as fast as they want, but they always run toward your current position (in reality, raptors are far more cunning than this)." We have placed the acceleration limit on the straight-line acceleration, but allowed the raptors to always turn towards the target, regardless of velocity.

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.

 

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.

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:

• Joe Frambach created a totally awesome poster on this problem for a Scientific Computation course at the University of Pittsburgh. Check it out!
  
  
• H. Chen used Mathematica's numeric differential solver to find a more accurate solution.

---

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