Topic: Path-finding

Hi,

I found an interesting open-source library on google-code : http://code.google.com/p/recastnavigation/
and I would like to implement it by default, it can create automatic navigation mesh and then find optimal path for IA.

Will it interest you to have this feature ?

Re: Path-finding

That sounds wonderful, but in the interest of your engine design, I suggest inserting into plugin system. I love that engine is light as it can be. Maybe you feeel a pathfinding system would be light 'enough' to warrant direct inclusion, but where do you draw the line ? wink

I vote for plugin system; give some incentive to work on that wink

cheers
gm



anael wrote:

Hi,

I found an interesting open-source library on google-code : http://code.google.com/p/recastnavigation/
and I would like to implement it by default, it can create automatic navigation mesh and then find optimal path for IA.

Will it interest you to have this feature ?

Re: Path-finding

The lib looks quite light, but it could be a plugin yes, I don't think it requires any additional tool in the editor. But it might also be a "standard" feature, I'm not sure yet.

The plugin system can already improve the script functions list, the only small problem is to find a way to access loaded plugins functionalities from another plugin in c++, for that I need to add a transparent system to access remote plugin functions (like actually done in lua). I still don't have a pretty way to do it.

Re: Path-finding

We have used Recast at work. It's pretty good. If anyone wants a list the pros and cons of Recast just give a shout.

I definitely think that this should be a candidate for the plugin system. As gamemaker stated, having Maratis as small and compact as possible is a very nice thing. Not all games need pathfinding at all, having this integrated (even if it's quite light) is a significant amount of extra bulk to the engine. Of course, this isn't my decision to make, but I thought I'd throw out my opinion smile

As for accessing plugins from C++. I was looking at that the other day actually tongue I think the main issue is that there is not a base class for a plugin implementation. I can write up a quick patch (on top of my previous patch) if you want, and you can take a look at what I was thinking.

Disclaimer: I don't claim that this is going to necessarily be a "pretty" way, however, I feel that it's at least a simple and clean way.

Re: Path-finding

Yes, it is also a good test for the plugin system.

For the plugins access, there is some ways like function pointer or virtual class,
the challenge is for a clear way to do it, specially for passing arguments.

For example, a path-find plugin would need to share a function to get a path from a start point and a end point,
like "bool findPath(MVector3 start, MVector3 end, vector<MVector3> * path)"

How to have this clear and simple ?

function pointer dictionary ?
using a standard call like "bool func(...)" could be used like :

bool (*findPath)(...) = dictionary->getFunction("findPath");
if(findPath)
    findPath(start, end, &path);

or a virtual class ?

Re: Path-finding

Personally, the way I would do this is to have a virtual class, call it MPluginImplementation for the sake of explaining here. Then you can have subclasses like MRecastPluginImplementation which, in StartPlugin, get initialised and added into the plugin system.

Obviously, if you're going to be calling C(++) functions from other code, you'll be linking to the headers of the plugin library anyway, so you can add a wrapper macro into it. This is entirely pseudocode and not even compiled, let alone tested, but something like:

#define MPLUGIN_IMPLEMENTATION_DECLARE(name) \
name* MGet##name() { return (name*)MPlugin::staticGetPluginImplementation(#name); } \
bool M##name##Exists() { return MGet##name() != 0; }

Then you can do things like

if(MRecastExists())
    MGetRecast()->findPath(start, end, &path);

Of course, you would have to add some mapping of names to MPluginImplementation classes, I suggested just having them static within MPlugin, but they can really be kept anywhere.

It really depends, I know a lot of code designers don't like the whole "everything is an object" thing and shoehorning things into OO design when they don't need to be, but I think when it comes to plugins, it's quite nice to have one central plugin object that you can interface with. It also makes any mapping much simpler because you only have to do one lookup for all functions, rather than one lookup per function.

Re: Path-finding

But it means you have to distribute the header of the plugin with the binary, how do the compiler know "findPath" otherwise ?

Re: Path-finding

Yes, but I think that's quite normal for a plugin system. I think in general each plugin would only need one interface header. I think it's possibly a little more friendly to do it that way, as it forms a first stage in documenting the functionality of the plugin. I'm not sure there's a nicer way to do this unfortunately

Re: Path-finding

There is also dlsym and GetProcAddress, it doesn't need the header and can be simplified by a macro.

But I was not thinking of the possibility of distributing the header, why not, with this we don't need to do anything as the header can contain functions or class like the user wants, there is just the risk to use the header when the plugin is not loaded.

Re: Path-finding

Hmmm, I would say that would cause more problems.

You could potentially get half of the functions implemented and acting as expected, but then the plugin could change it's API and act differently, or some functions might not even link at all. I think, whatever the solution ends up being, adding a plugin version number and allowing version checking from game code.

As I said, I think that distributing one header file is actually quite nice because it gives a beginning to documenting the API of the plugin, plus you can include it into the game project and IDEs like Visual Studio will pick it up and use it for compile time checking, as well as code completion.

Re: Path-finding

The safer is the dictionary, but it's a bit limited.
Distributing one header will be faster and good for code completion, with a method to check if the plugin is loaded it should be safe enough. Thanks for the idea smile