Babbage Builds a Path: Linden Inventor Releases Open Source Pathfinding Code

In his recent travels, Babbage Linden got word of a plan by veteran Resident Eggy Lippman to create a Tower Defense game in Second Life.  This struck Babbage as a great idea (and, I should add, me fricking too), but even top Lindens thought the Linden Script Language was not ideal for handling pathfinding, the deceptively complex game developer challenge of programming an AI to move from point A to point B in a relatively efficient manner.  It's one of the reasons the Lindens have been trying to migrate SL scripting to Mono.  CTO Cory Linden "has talked about the need for AI and pathfinding being reasons for integrating Mono in Second Life," Babbage tells me, "so I started working on it thinking that it would be a good demo for Mono." 

During the process of building one, however, he realized it could be developed in LSL after all.  The result is what you see in this video: pathfinding in SL that's robust enough to coordinate the movement of numerous AIs, even speedily re-routing them in opposite directions, when Babbage rezzes up impromptu obstacles in their way.

Babbage's code is GPL-licensed and available to all.  Hopefully, he says, it "will be used to provide the basis for lots of new games in Second Life."  (Just picture the green balls in the video as Creeps from DTD.)  But how's it work?

"It's potential field-based pathfinding done entirely in LSL in Second Life," Babbage explains, downshifting into full geek patois: "A pathfinding script stores the distance from each point to the exit as two hex digits in a string. Agents query the pathfinding script to ask which square to move to next. When squares are clicked on, they tell the pathfinding script that they've become an obstacle. The pathfinding script then sets the distance from the obstacle to FF and then updates the squares around it which may have been using the square as an exit. If any of these squares are updated, the update region expands and more squares are updated. In this version the updates occur synchronously, so if adding an obstacle results in a lot of updates, the pathfinder becomes unresponsive to queries. The new version only updates a few squares at a time, so continues to be responsive at the cost of sometimes using out of date information to respond."

Get Babbage's pathfinding code here at this SLURL link, at Babbage's home in Ambleside.

Comments

[Rodion Resistance]

Hopefully this technique won't be used to create more efficient um, "flying appendages" bent on following you around wherever you go--I shudder at their efficiency if they ever get this code wired into them.

[Gwyneth Llewelyn]

LOL! I can't believe that you've covered this, Hammie :)

Babbage and Eggy spent a whole day discussing this (last week iRL), and I was moderately curious about what they were talking about. Then Eggy gave me the hint about the version of DTD that you've covered on GigaOm... and I got immediately addicted (now if I only knew how to score more than 2000 points...). A few days later, Babbage also previewed to us his version, and our surprise was that it worked so well, even on plain old LSL :)

I'm really intrigued of what might come next. Doing towers with special effects, hitting the creeps with physical bullets and particle explosions, is pretty easy to do — the hard part was the pathfinding done by Babbage! — but I can imagine that this game could be "secondlifed" in pretty interesting ways, namely, as contests among several players, getting your score paid in L$, whatever. Will this be the Tringo killer application? It's easy enough to be fast to learn, fun enough to be very addictive, and complex to master to ensure returning users. So — why not? LSL just has to become faster, but I'm hoping to hear the official announcement on that in a few weeks...

[Babbage Linden]

I'd really like to see a tower defense game that took advantage of Second Life by being multiplayer and incorporating physics. A team of avatars place defences that catapult creeps through the air, back towards the start, in to each other, and in to the path of lasers, pull them along with tractor beams, push them down pits, up ramps and on to conveyors. Tower defense meets Robo Rally, Dungeon Keeper, Mouse Trap and the Wacky Races.

[postmodern]

While moving the Linden Scripting Language to Mono would definitely be an improvement, I just can't stand Mono. Maybe something less C-like, perhaps Ruby once Rubinius becomes stable.

[Nexii Malthus]

I just found this news post. I am myself working on a real time strategy game, it works nicely, and I do agree Mono would be extremely useful for pathfinding. I am already incorporating trajectory algorithmns for accurate ballistics in my tanks and working on bezier curves (got confused at B-Splines and NURBS) flight paths for my airplanes.

I would like to contact you Babbage, I am very enthusiastic about creating proper games for Second Life and would like to discuss about game development with LSL. Unfortunately, I reside on the Teen Grid, and as a quick search for your profile in SL tells me, you have not been background checked.

Could someone please put up the LSL script? I would be very grateful, I am unable to get it.

@postmodern; Mono will be just the backend for LSL. The way we script won't change. It is just that LSL will be compiled more efficiently.

[Babbage Linden]

The code is now in the Second Life wiki here:

https://wiki.secondlife.com/wiki/Pathfinder