A Possible OpenSim Pathfinding Implementation

Navigation Mesh

A navigation mesh displayed in an unmodified viewer

OpenSimulator has a good track-record when it comes to actualizing new features. It had support for custom meshes almost immediately, and there was rapid progress on the materials system. Things like support for multiple attachments per attachment point took a little longer, but OpenSim eventually adopted it. One of the larger features we haven’t yet seen an implementation for yet is pathfinding.

Dahlia Trimble, a member of OpenSim’s core developer group, has been quietly working on a pathfinding implementation. While much of its essential functionality is complete, it is not yet ready to be included with OpenSim, and may not be for quite some time due to some rather unfortunate issues with platforms other than Windows. When reading this blog post, it’s also a good idea to keep in mind that I have not personally had the opportunity to make use of this pathfinding implementation. I only know a few things about it based on what I’ve seen and read about it, and from a few rather brief responses from the module’s author.

So what is pathfinding, exactly?

If you’ve ever played a video game of almost any sort that has computer controlled characters or ships walking or moving around, you’ve seen pathfinding in action. The game (or other application) needs to be able to move these characters around in a way that makes sense. It needs to know where a character can travel and where it cannot. It needs to be able to navigate around obstacles, up stairs, or through tunnels.

In order to accomplish this, an application needs to know certain things about the environment it displays. There are a number of methods to provide a program with the necessary data to move characters or similar entities around in a convincing manner. The very simplest is a predetermined list of coordinates within the world for characters to follow. This method works fine for an environment there is very static and predictable, and is computationally easy, but is not at all suitable for virtual worlds hosted by something like OpenSim, where the world can and often does change rapidly.

Instead, one needs a method of determining where a character can and cannot go by allowing the application to inspect the environment, calculate valid coordinates, and dynamically generate a path to travel. It is necessary, when designing the environment, to designate what volumes constitute an obstacle, and then allow the application to intelligently assess coordinates that comprise a path to follow.

It is actually quite possible to script your own pathfinding solution with LSL. But this approach can run into issues and barriers. Pathfinding is a computationally intense process. The larger the space it has to deal with, and the finer the coordinate resolution, the more expensive it becomes. LSL is a pretty blunt tool when it comes to computationally intense tasks, and it is difficult to optimize. The LSL pathfinding example linked to here also only works in two dimensions. Once you add a third, up and down dimension, it becomes an even more complex problem to solve. What’s more, it requires a lot of manual labor to define what areas are safe to use as valid coordinates, and that labor must be repeated if the environment changes in a significant way.

So, it’s a lot easier to allow the simulator to determine paths for our characters to traverse. It always knows all about the objects that make up our worlds, and thanks to pathfinding features in the viewer, it can know which volumes of space are suitable for paths. All we have to do is ask the simulator to “bake” or create something called a navigation mesh, or navmesh. Once that navmesh has been created, the simulator can use it as a guide to calculate a list of coordinates that can be used to guide an autonomous entity around the scene.

OpenSim’s pathfinding sneak-peek

[vimeo 51836266]

For well over a year, Dahlia has been working on a pathfinding implementation for OpenSim. I’ve mostly caught glimpses of her work here and there, and she’s made it clear that she does not feel that it is ready for a release of any sort. Here’s what I know about it so far.

It works! Mostly. The essentials are all there. It’s able to look all the objects in a scene over, create a navmesh, and then from that deliver a list of vectors via an LSL function named pfGetPath.

What it doesn’t yet have are the other LSL pathfinding functions that provide support for things like evasion, patrolling, pursuing, etc. These are things which could be re-implemented by scripters in LSL, so aren’t a big blocker. They’d just be nice to have, and there’s nothing stopping an interested developer from adding these LSL functions.

So what’s the hold-up?

Sadly, there’s a major problem when using the Mono runtime on platforms like Linux or Mac OSX. As mentioned previously, the navmesh calculation is a pretty large task to tackle; it consumes a fair amount of CPU and memory. And memory is the issue here, as for some reason Mono is refusing to release that memory once it is done with it. This is probably a bug in Mono, and will hopefully be addressed at some point. But until it is, and until most OpenSim operators are using a fixed version of Mono, it won’t be practical to include it with OpenSimulator.

Another minor issue is that while the viewer can have support for being able to see the navigation mesh in-world, it is my understanding that that functionality relies on a proprietary Havok library. Viewers which support connecting to multiple grids are not allowed to include this library. This isn’t a showstopper; pathfinding will still work. But scripters and creators will not be able to visualize the navmesh in their viewers, and instead will have to imagine it in their heads. There is also the possibility that some intrepid viewer developer will tackle the problem and come up with an open-source alternative that allows for navmesh visualization. This has been done before with the HACD library for meshes.

So while Dahlia’s pathfinding work is very exciting, it is also very experimental and uncertain right now. I do find it comforting to know that it is possible to have a pathfinding implementation for Opensim, though, even if we may have to wait quite a while for it.


One thought on “A Possible OpenSim Pathfinding Implementation

  1. Pingback: New Second Life article - Second Life's Strange Second Life - Page 7 - SLUniverse Forums

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s