Dr. Kevin Hamlen Sets Spaceflight Simulation Game World Record
Computer science professor Dr. Kevin Hamlen was searching for the fastest route to a human colony 22,000 light years away in the game Elite Dangerous when the challenge started to look similar to a theory he teaches his students.
Hamlen, who was playing with his 6-year-old son, Will, would need to take risky shortcuts by scooping fuel from neutron stars to make long “hyperspace jumps” to beat the world record for reaching the farthest human colony (named Colonia) from Earth.
But which stars? And in what order? Traversing the galaxy without these dangerous maneuvers could take weeks, but using them without a careful plan could leave him stranded in deep space with little hope of rescue.
“I realized that the problem of finding the fastest way to get from Earth to Colonia is actually a famous graph theory problem we teach in computer science,” said Hamlen, Eugene McDermott Professor of computer science in the Erik Jonsson School of Engineering and Computer Science. He said solving the problem involves analyzing a directed graph — often drawn as circles connected by arrows — to identify a least-cost path.
“I thought it would be fun to see how well I could do using science to solve it,” Hamlen said. “I downloaded star map data and wrote some computer code to search for optimal flight paths, and then flew the route it discovered, with Will at my side calling out course corrections.”
The large dataset, with more than 1.3 million known neutron stars, required some coding finesse to analyze without large computers, Hamlen said.
“I used a number of algorithmic and programming tricks, such as pairwise heap data structures, a metric space transform, memory-mapped files for buffering data at high speed, and vector arithmetic operations available in modern Intel processors,” Hamlen said. “In all, it took me about four hours to write the code. After I was done, I could compute optimal routes between arbitrary stars in about one minute per 20,000 light years on my desktop PC.”
Using an A* (pronounced A-star) algorithm, Hamlen and Will reached their destination in 1 hour, 38 minutes and 11 seconds, beating the previous record by more than 12 minutes.
The online publication Sagittarius Eye chronicled Hamlen’s, aka Commander Falken’s, victory. (Online, the team is known as “Steve Falken,” named after the fictional computer scientist in the movie “War Games.”)
You can watch him stomp the world record here.
UPDATE
Dr. Hamlen has already beaten his own world record in Elite Dangerous. The professor said he used additional computer science theories he teaches students to broaden the space of possibilities that his algorithm could consider.
Hamlen was able to cut his flight time to 1 hour and 29 minutes (from his record-setting time of 1 hour, 38 minutes and 11 seconds).
“This weekend I refined my approach to beat the record by an even greater margin,” Hamlen said. “It’s probably the best I can get it.”
Source | UT Dallas Magazine | Kim Horner
ABOUT THE UT DALLAS COMPUTER SCIENCE DEPARTMENT
The UT Dallas Computer Science program is one of the largest Computer Science departments in the United States with over 3,315 bachelors-degree students, more than 1,110 master’s students, 165 Ph.D. students, 52 tenure-track faculty members, and 44 full-time senior lecturers, as of Fall 2019. With The University of Texas at Dallas’ unique history of starting as a graduate institution first, the CS Department is built on a legacy of valuing innovative research and providing advanced training for software engineers and computer scientists.