Steve Exploring Stuff: 2010

2010-11-27

A Little Bit of Recast for Unity

It's been a while since my last post.  I've been working on various projects in parallel: dynamic obstacle avoidance, behavior, smart objects; and the first to reach a point worth sharing, navigation mesh generation in Unity.

The new NMGen is a wrapper for Recast with simple API's for use in Unity Pro and .NET applications.  This release only includes the ability to create static triangle meshes. But the foundation is in place to expose Recast's advanced functionality if I ever need it.

The project home includes links to code, documentation, and a Windows-compatible distribution.  The distribution includes a Unity package containing components, prefab's, and custom editors for non-programmers.

There are three main limitations in this release:

Use is not completely free since native plug-ins can only be used with Unity Pro.  I have some idea's on workarounds.  So this may not be a permanent limitation.

Sorry Mac users.  I don't have a way of building and testing for your OS.  So I can't create any distributions for you.

The Unity components can't create navigation meshes from Terrain objects.  This isn't a technical limitation.  I'm just not sure yet how to extract tree mesh information from the objects.  Also, the potential large size of the terrain is problematic.  (Threading in the Unity Editor ==  Potential ickiness.)

Enjoy the new code.  And have a happy <insert your favorite winter holiday here>.

2010-07-13

Port of Navigation System to C#/Unity3D

Over the last month or so I've taken a road trip, gone camping, and had a visit from out-of-town family.  I've also been preparing for my next project: Locomotion.  As I mentioned a couple of posts ago, I want to learn C++.  While I became comfortable reading C++ during the NMGen project, it is now time to do some coding in the language.  This means leaving behind Java and the Java based 3D engine I've been using.  I've settled on the Unity3D engine.  Some of the reasons include:

  • It's vast depth of built-in, very well documented functionality will make it a great, fast 3D prototyping environment.
  • There is nothing in its license that stops me from posting my own code as open source.
  • It has a free version, so others can still experiment with my code at no cost.
  • It has an easy to deploy web player, so I can move past static examples. (As you will see shortly.)
There are some drawbacks:
  • The engine is closed.  No calling into the guts from my own code.  I doubt that is going to be a problem for a long while.
  • In in order to keep things free for other's, I'll have to make sure that all my C++ code can be compiled as a .NET assembly.
I expect that last drawback will be the biggest pain.  But the overall benefits of using Unity3D are likely to outweigh the drawbacks.

Now for the code related stuff.  To get things up and running I've ported my Java navigation system prototype to C# for Unity3D.  The "for Unity3D" part is due to the fact that I switched to using the Unity3D Vector classes.  I'm not sure that is the best decision since it ties the code to the engine.  But it isn't a costly decision.  With only a day or two of work I can easily switch back to my own Vector classes.  

Here is the code, the project home, and, goody, a web demo.  The web demo requires the Unity3D player.

There is also a bug fix for anyone who downloaded the Java version.  If you are still using it, make sure to pull down the update.

Enjoy the new code and keep the puppy out of the cactus patch.  (Silly dog.)

2010-05-28

NMGen Documentation Complete (Plus a Bug Fix)

The NMGen documentation is complete, done, put to rest.  The final three chapters include: Contour Generation, Convex Polygon Generation, and Detail Mesh Generation.  Whew.  I tend to be a stickler for documentation, but creating it makes my head hurt more than the most complex coding task ever does.

If you've downloaded the code before, I recommend getting the most recent version.  It includes a bug fix.  There was a problem during region merging that could result in dropped polygons.

Enjoy the weekend and let the smurfs be.

2010-05-18

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.

2010-03-25

Two New NMGen Chapters

It's been a lot longer than the promised two weeks between updates of the NMGen study documentation.  I don't have a good excuse.  So I won't make something up.  (Read as: I let myself get distracted by other things.)

I've pushed out two new chapters.  One on the the voxelization process and another on region generation.

Enjoy.

2010-02-17

Navigation Mesh Generation

My first project is a study of the navigation mesh generation process used by Recast.  It consists of Java code that takes an arbitrary triangle mesh as input and generates meshes that represent the traversable surface of the source mesh.  Lot's of good computational geometry algorithms!

I'm calling it a study because it is way over-documented.  Overviews with visualizations, full javadoc, and lots of code comments with references.  It's got so much documentation that hackers may get irritated.  But the target audience includes novices.  So hackers, deal with it.  There is plenty of undocumented code in the world made just for you.

It's been a long time since I've used so much math in my work.  And forcing yourself to create documentation is a  great way of burning new things into the brain.  I also learned SketchUp and a new content management system in the process.  So lot's of secondary fun for me.

The project is over on a new domain:  CritterAI.org.  Its a place where I'll be posting AI related code.  The NMGen entry point includes links to source, javadoc, etc.

The overview documentation is still in progress.  I'll provide updates in this blog whenever I post a new "chapter" to the overview.

Enjoy and don't eat the broccoli.

The First Post (Why this Blog)

This is me exploring.

I'm a tech type.  Mostly software programming.  Up to this point all of my development projects fell into two categories:  Owned by employers, and tech demo's rarely worth sharing with others.  I've benefited so much from others sharing their work that I'm changing things up a bit.

Starting with my first project, which will be published shortly, I'm going to be using this blog to share stuff I'm working on.  There will be status updates along with posts on what I discover along the way.  Whenever possible I'll share code under the MIT license to allow others to re-use it freely.

You'll see mistakes and corrections.  That is just part of exploring and learning.  Coming from a tools and automation background, I have a very wide area of interest.  So you'll also see a wide variety of content.

While the content will vary a lot, most will have a common wrapper.  The wrapper domain will be "simulations".   Game-like, but not really.  I'm wrapping everything as a simulation because it will give me a great deal of latitude to re-use and refine code.  Here is an example:

Desire: I want to study computational geometry, C++, and voxel graphics.
Project:  Implement a navigation mesh generator in Java, derived form a C++ code base.

Desire: Continue study of computational geometry.  Add graph theory and associated algorithms.
Project:  Implement pathfinding algorithms in a simulated environment, using the output from the navigation mesh project.

Desire: Continue study of C++ and study Java/C++ adapters.
Project:  Using my knowledge of navigation meshes and pathfinding, implement a Java adapter to the C++ code on which the first project was based.

Desire: Study performance constrained networking and web development.
Project: Implement a server-side virtual environment simulator using the previous projects with the presentation layer in a web browser.

And on and on and on.  Just about any domain I can think of to explore can be done by building on a simulated environment.

At the end of the day, I can only hope that these explorations are useful to others.

Be good and don't eat the broccoli.