A Prototype Navigation System

After completion of NMGen coding I started work on a navigation library to use the NMGen meshes. I wanted to explore several areas, including high performance threading and some new computational geometry algorithms. The result is here. It's a basic multi-threaded navigation system written in Java that uses a variation of the simple stupid funnel algorithm for path straightening.

Threading Design

The design includes the rule: Don't trust clients to act in a thread safe manner. This rule precludes the use of callbacks since the navigator can't trust its clients to provide thread-safe functions. Instead, when a client asks for services from the navigator it gets a request object. The request object contains the request's status and, when complete, the final data.

To keep performance up, the design encapsulates inherently non-thread-safe data within wrappers using a dual class design. One class is the "master" aspect. It is thread friendly, meaning that is not thread-safe but can be used in a thread-safe manner, usually without synchronization. The navigator manages the master aspect. The second class is the "client" aspect. The client aspect does not depend on its users to act in a thread-safe manner. It may use synchronization to keep data safe, or it may expose the data in a way that doesn't require synchronization. Clients get references to the client aspect. Both aspects use the exact same data through a outer/inner class design. For example, there is a MasterPath class that is only used by the navigator, and a MasterPath.Path class that is given out to clients. In this case, neither class has any synchronization costs.

I'm generally happy with the multi-threading. It still needs some work, but the navigator meets my goal of supporting 30 clients concurrently.  So I'm leaving it alone for now. In testing I was able to average over 100 path queries per second with an average frame delay of less than 2.

Paths as Corridors

I got the idea for path corridors from Mikko's simple stupid funnel algorithm blog post. Take a detour to look at his visualizations. When the navigator returns a path, the underlying data is an ordered list of navigation cells. The client is getting its own mini-navigation mesh with most of the benefits of the mesh.

I really like this data structure. It makes it a whole lot faster for a client to determine whether it is in a valid location to continue its locomotion. It also allows paths to be quickly repaired if the client strays slightly outside of its corridor. As long as a client's goal remains the same there is rarely a need to completely rebuild the path.

For example, lets say a client has trouble around a doorway and has strayed off the path...

There is no need to perform a full path search to recover. The navigator uses a limited depth Dikstra search, searching from the client's current location to the cells that belong to the path. In this case, it will find a way back to the path within a depth of 1. Another possible repair method is to search for cells directly adjacent to the path corridor. If the client is in any of them, the path can be repaired. This method can be optimized by starting the search at the last known cell location of the client. With the data structure I use for my navigation mesh, this type of fast repair can be performed without needing to make a call to the navigator. It can be added to the on-demand string pulling that I use, effectively widening the path corridor to all adjacent navigation cells with no extra memory cost.

I hope to explore the use of path corridors more. But I'll need a realistic locomotion system first. So that is next.  Though it will be in C++ rather than Java since I need to learn that language.

For anyone wondering when I'll be completing the NMGen documentation, don't worry. I'm going to complete it before I move on to locomotion.

Good hunting and such.