PathFinding Content Pack

#21 Wesley, my intention was precisely to encourage you guys, not the opposite!

That little gem can use some work, specially on the "by hand" mode you were thinking/developing on top of the mesh generator, and thats not to mention some of the points you listed initially.

And of course, as you well say, integrating it with Torque and its editors could be the new fundamental stone.

#22 @Novack Hehe I think intimdated were my initial thoughts and rightly so by the way. That gem seems pretty far along the curve from what i was thinking i could possibly do and i guess for a brief while i was wondering if their was anything left for me to do. However i read a little the thread and rembered what i was planning to do and i am willing to bet this thing is a really ugly beast underneath that pretty exterior with half a dozen things that will need fixed or changed before it is even halfway cooperative with torque.

Even with open source their ain't no such thing as a free lunch after all.

As to earlier about teaming up almost pulled that off with Andy until we realized we were working in Different engines TGE and TGEA respectivly. That kinda confused which platform i should really be targeting here. I still hope to work with Andy acctually regardless.

#23 I had a look through that code before and it's a fantastic source for auto-generating a mesh for a level much better than the approach we've taken as we've started the same way as some of the other pathfinding resources here (Immersive AI & Dan Kellers), except we've then taken it a step further and optimisized things by removing unneccesary nodes, merging them together where possible, etc. Would talk more about this but I don't want to steal Dan's thunder as he's doing a fantastic job on it and hopefully he'll share some pics/vids soon.

Unfortunately the recast auto-gen uses convex polygons and our design was to stick with triangles as the maths is a lot simpler and we figured what you may gain with a smaller mesh you'd lose by heavier maths - plus we read that the Ghost Recon games and Fallout 3 all use tri's so figured it should be good enough - still once we've finished our working solution I'll take a look if we can use the first couple of stages to build the sections and drop that into our solution (hopefully).

@Wesley - Since we spoke we now have 3 of us teamed up to work on this and about 80% of the way through development now of features for the first version. Although we've some design changes to be made as things aren't quite working how we'd hoped.

I'm sorry but not sure how we could team up at this stage of development, with delays of late with personal lives we really want to focus on finishing what we have now rather than trying to merge solutions (hence deciding not to look at the Recast source) and start discussing design features again. Perhaps once we're done with this version/iteration that would be a good time to discuss if there's enough commonality in design, thoughts and features to think about combining efforts.

Don't give up on your version of things, these libraries rarely solve much of the overall solution and getting them to work with Torque is no small feat in itself so there's still a massive benefit from the work you were planning.

#24 Would absolutely love to see a pack like this. A long time ago there was talk of a AIPack, with tools, nice screenshots, etc. But its been years and I think it died out. A well done nagivation/AI pack with solid documentation, good tools, easy to use, can easily be extended for things like formations (group pathfinding, etc) would be worth a decent amount. I would certainly try it out and buy it if its well done.

I wish you guys luck and hopw you do finish it.

#25 @Andy yeah i was kinda feeling like we were going in very different directions with what we are trying to do and since you already have a team togheter and so far along i think it would be hard for me to even catch up on what your doing much less contribute much.

So for the time being i am putting all my efforts into recast. I am not gonna argue what the best mesh representation is since that has become somthing somewhat subjective and dependant on what exactly your doing. I feel the meshes generated by recast are more than sufficient. I just am not confident enough in my own abilities to even think of trying to improve on a mesh generation package made by a guy who worked on crysis that is just kinda out of my league. Plus Recast seems to be getting a good number of updates so the possibility of being able to always use the latest version is a real plus.
That said I do not think adapting it for torque will be an unsurmountable task. I am thinking it will be a good learning experience for me. I am really doing all this for the sake of learning this stuff more than the actual hopes of making any money here. I already have a fairly good idea of how recast imports and exports it's data. The trick for me now is to figure out how to get the needed raw geometry data from torque somthing i have no idea how to do just yet. Fortunatly i at least have some places to look.

I am going through this older resource. Have a glance at it you never know.
http://www.garagegames.com/community/resources/view/8531
Regardless what may be thought of his implementation he had to access raw geometry at some point to do auto generation.
EDIT: (I tried the link to the code for that resource to see if thier was a new version and noticed the link is no longer working. Fortunatly i grabbed it a long time ago and still have the original zip file on my system so if you need a copy just let me know. ;) )

Once i hunt that down i am considering wheter or not to export the raw geometry snapshot as a .obj since the recast demo that comes with the package loads it's meshes from that format already. Plus having an actual file in a well known format for debugging will make my life alot easier.

I can't help but wonder if that is kinda cheating a little bit. Though while it is probably not the absolute most ideal and professional approach, i am figuring it is probably the easiest way in the long run to just make it work.

I will worry about everything else once i actually get recast working with torque.

#26 @Wesley - No arguements here on what the best mesh representation is either, in fact I'd say there isn't one they all have strengths and weaknesses that seem to level things out overall.

Recast looks like a great solution, wish it'd been advertisted when we started as I'm sure we'd have used it as the basis especially since the auto-generation that Dan's created works from the level geometry.

In terms of the resource you posted, I don't think from looking at it that it does use the level geometry at all? It says to manually place nodes around the map. Did you post the right link?

In terms of getting access to the raw geometry though I don't mind sharing how we've done it if it's going to help you get started with using recast, anything you can learn or gain from it can only help the community here :)

Can't wait to see what recast can do.

#27 Hmm i think your probably right about that resource. It really was somthing i had downloaded a long time ago forgot about and noticed again while i was searching through the forums. I had not gotten around to implementing the thing yet. It pretty much is just an implementation of the A* algorithm for torque. I thought it did some auto generation because i read about the precomputation it does but i suppose that is what happens to the mind at 3 a.m

Any information on how to get at the raw geometry would be quite helpful.

#28 Well after alot of hunting and searching i finally figured out how to get at the raw geometry of torque. Then get it exported into the .obj file type.






This is the test map i was using earlier loaded into the recast demo.






I am using the bounds of the missionArea to define the area to export but i have it setup that you can define your own regions.
I think I still have a few things to take care of before i can call it 100% perfect though. Right now it is exporting the terrain underneath water blocks as well. Which unless you want to enable swimming is a bit of a problem. At the moment though that seems more like a finishing touch.






Now that i have all the information about how torque exports it's geometry and am 100% sure it is exporting and displaying correctly. It should not be much trouble to then directly feed the geometry into Recast. I am considering whether i want to store the navigation mesh in the internal data structures supplied by recast or whether to export it back to torque.

Either way i think i will want the ability to export and import the generated navigation mesh as a .obj file. This would provide a way to store the mesh so we do not have to regenerate it each time at load. (seems like a 10 minute process even with small mission area given the default settings for the demo) Unless you guys know of a better file type the .obj seems good enough to allow for easy editing in just about any modeling program. While it would not be quite as neat as being able to edit the mesh from the built in editor combined with the ability to export the geometry the navmesh is built on we could have some of the rudimental functionality i was proposing with my original navmesh concept without much extra effort.






I actually already have recast compiling just fine within the torque engine as part of the project. Although nothing is calling or using anything from recast ATM. So far i have only had to play with the file structure to get it to compile. I am unsure if i should go through recast and try to get it to use the Torque data types or leave it as is to let the user simply use whatever platformed version is current.

Then thier is the matter of detour though it seems limited to mostly point A to point B stuff it still may be a pretty good spring board to move forward from. Plus then i would probably only have to worry about higher level stuff

Looking back on this thread. I am wondering if it is becoming more appropriate to just start a blog or plan on a navigation pack. I probably shoulda used smaller RES on the pics too i think it makes it harder to read. Hehe i was not even paying attention and accidently cropped them on one side but anyway the basic ideas are thier it takes roughly 10 minutes to generate a reasonable sized mesh so it does not feel like it is worth it to capture better pictures.

#29 Very interesting work Wesley!

I still dont get it completely on the export/import scenario you are designing, Im more prone to like in-engine solutions for this kind of "situations", but you got me very interested in your work, to say the least.

Im curious about this:

Quote:seems like a 10 minute process even with small mission area given the default settings for the demo

This is weird, the stock recast scenarios seemed more complex than your demo mission, and yet the mesh generation takes no time... Although Im guided just by some rough shots that may not do justice to your mission, is still too much difference. How much time it takes for you with the stock models?

#30 @Novack yeah the test area i was using is alot bigger than the test maps provided. The biggest one is like 5.1k verts 10.1k tris the map i used was 39.5k verts 71.3k tris. A large section of the terrain block really uses alot of verts and tris in it. I think the default settings are probably more optimized to run for complex maps so may take alot longer on a large uncomplicated maps.

I understand what you mean by prefering in house solutions as thier is less to worry about compatibility. That is also why i think the .obj type is perfect for this sort of thing. It is a very simple text format it took me under 5 minutes to learn everything i needed to use it for my purposes. Heck i only needed to use the vertex and face tag. If you were really hardcore it would not be hard to hand edit it.

#31

well there we have it a navigation mesh i generated in torque then exported as a .obj file. I just loaded it in recast because it was the most convient way to view it. Also because milkshape refuses to load my .obj files i probably am missing the end file charecter. Should not be too much of a fix to get that working.

This really took alot longer than i really hoped It took about a day to write my own load module strip out all the rendering code from recast and do a test build. Real life concerns and two annoying bugs kept plaguing me. I should have rembered from my previous experienes exporting a .obj to recast that i needed to invert the order of the vertices for the faces and a more embarrassingly stupid bug i would rather not even mention. Simply put i feel like such an idiot. Trying to fix these two simple bugs i dug into recasts innards way more than i ever hoped i would have too. Also getting this to work i realized it will be no where near as plug and play as i had hoped with getting new versions of recast. I had to comment out large sections of rendering code add includes in places convert alot of those calls to rclog to Con::printf or Con::errorf For the most part though I guess I can easily write a guide to importing the latest version of recast since the basic inner workings remains the same.

My code and interface are pretty rough right now and will need some cleaning up. Also realized that unfortunatly the .obj type will not be able to store the mesh data and retrieve it easily. the reason is that Recast stores it's mesh data along with connectivity between the polys that is somthing that is not represented by just a .obj file. So i will have to figure out how to generate this connectivity information myself if i ever want the .obj files to editable by any graphics tool out thier. This also means that .obj files will not be useful for storing the navmesh for loading into torque because it would then have that extra overhead at load of having to generate the connectivity every time a new map loads.

So i am thinking of just making my own file type based on the .obj file type probably call it .nav that stores the connectivity data then include commands to export and import .obj files for use as a navigation mesh.

beyond all this i guess my next step would be to make the navigation mesh render-able in the torque editor and to see if i can get the detour side of things now working. Should be fun.

#32 @Wesley - I'm a little confused at the approach you're taking, we've implemented Recast straight into Torque without having to change anything in their code, there's a video on my lastest blog.

You appear to be trying to integrate the Demo application (in the Recastdemo folder) with Torque, why take that approach rather than just including the source from the Recast Folder which has none of the rendering stuff or demo app details in.

That way you can just drop in a new version of Recast changes without altering anything in Recast.

#33 @Andy My changes were mostly cosmetic but i have to wonder how you managed to get away without changing any of the code in recast and not using anything from the demo file. did you just create your own Builders and meshloader code? For the meshloader i just created a child class TorqueMeshLoader so i could just simply use the parents addvertex and addTriangle without having to change anything thier. The builders though were pretty full of rendering code i decided it would be best just to comment it all out rather than risk any conflicts within the engine even if nothing was calling it.

If you did create your own builders keep in mind i noticed that later versions of recast add more options and values such as a detail mesh that require a few changes to the builders. How do you plan to retain combatibility for future versions that might change these routines? Or if users have older versions of recast that lacks the newer options.

I had to put includes from the torque engine in with recast.h to avoide memory management errors within the engine whenever somthing got deleted. I did not really quite understand the errors i was getting but the includes fixed the problem.

realisticly i think i might have to hang up the hat here. Thier is just no way i can possibly compete with you guys. I only really went through the trouble to getting recast to work in torque because you said you were going to stick with your own navmesh generator. So i saw an opportunity to do somthing useful. Seeing as you have it fully setup with all the bells and whistles all ready thier really is no point to my work and it was just a big waste of time and effort.

#34 Yeah we hadn't planned on recast being a feature at all as I'd posted above I was sure that recast only generated meshes with convex polys and not triangles but one of the AI guys on another forum corrected me and pointed out that it has a parameter to specify the max number of verts for each poly.

We found it dropped straight into the work we'd been doing already and was a great fit with that stuff, really happened by chance than anything planned and it did a much better job than the auto-gen work we had been doing - although I'm still considering using some of our optimatization and 3-2 poly merging on top of it.

The builders at the moment are a combination of our own code and pieces from the demo - seeing as we'll release the updates we can control the versions of Recast that it's compatible with.

Don't hang up the hat, always worth completing projects that you've started and no doubt you'll come up with some great features that we won't even dream of adding. It's really a pity we're using different engines otherwise the simplest solution would be to team up on things