PathFinding Content Pack

#1 I think there would definitely be a market for this were it well organized and documented. One of the problems that people have with creating AI is that they don't know how to do it (and often do not want to know; they just want it to work). But there is definitely a market for it.

#2 There is a rather large market for anything AI related.

#3 well that is good to hear. I am certainly planning to make it as easy to use as possible. When it comes to Ai no two games are gonna be quite alike and have differing requirements. So i think keeping it as well documented as possible is a absolute minimum and I hate running across incomplete documentation myself nothing can get in the way of using a piece of code faster than having to stop what your doing and having to figure out how the thing works before you can move on.

My NavGrid implementation i have already displayed thier is pretty close to just click and drop as it is I have automated everything i could think of so far simply because i was intending to use the thing myself and i did not want to have to bother with it.

So far i am planning on doing the following:
* separate nevmesh implementations for RTS Square type grid
* influence mapping and terrain analysis for RTS
* Navmesh implementation for RTS and RPG's ect..
* Possibly direct compatibility with the RTS pack )though i think i would have to get in touch with the people who did that before i can really add that)
* support for non standard sized moving objects and turning radius's For Navmesh
* support for dynamic objects such as doors barrels dropped on the path ect.. For Navmesh

What i think i will avoid doing:
* Making it a full 3D pathfinding system. 2 dimensions is complicated enough. (the navmesh does allow you to run path over and under bridges just fine basicly anything walkable on the ground will be easily doable)

Got a bit on my plate thier but i think thier is room for other things. What would you like to see feature wise in this kinda content pack.

#4 Definitely a market for it. Pathfinding performance is also key. And as you mentioned dynamic pathfinding is definitely a plus.

#5 @Wesley - Definately a market for this kind of thing, I've just started work on a navMesh implementation for our game with a very similar premise.

I have thousands of Nodes autogenerating across the terrain already, I'm then intending to use a triangulariztion algorithm to build basic polys before using something like Hertel-Mehlhorn to build a good set of convex Polys.

Interiors are my stumbling block at the moment - which I may try a floodfill algorithm to gen nodes, get the structure/poly list from the scenegraph or simply go with manual placement (which might just be easier and simpler all round).

It'd be great to be able to team up on something like this or share thoughts as most of the NavMesh documentation out there is all theoretical stuff, Phil Carlisle mentioned one of his game dev students is also working on a navMesh implementation that is supposed to be open Sourced when complete.

#6 your right you would think thier would be some realtivly clear cut answers by now of what would be the best way to structure the grid.

I can appreciate the benfits of litteraly having a grid that the user could just press a button wait a bit and have thier grid fully setup for them.

However i am doing a manualy placed navmesh because it is simplier and less error prone overall(hopefully) and generally i think you lose little bit of flexibility with auto generated meshes since it is harder to let the navmesh define corners for you, for larger moving objects or with differing turn radius's.

I certainly would not mind working with you on this kinda project two heads are better than one after all.

#7 Yeah I'm not sure how well the auto-generation will work but if I get it working for terrain only it'll be a time saver overall especially on large maps - no matter how good it is though it'll never beat manually placed ones so I'll need to add a way to modify/influence the created grid.

Guess my thoughts are if it's even 50% useable that's still half the job saved more than that and it's a real bonus - although there's also a big chance I'll fall flat on my face and go 100% manual anyway.

Drop me an email to redrolo (at) hotmail (dot) com and we can have a chat about we can collaborate on things or I'm on the forums here most days.

#8 This is an interesting idea. If you combie both approches, you could make a really complicated grid in moments, expecially if the nodes in the auto generated grid were movable (for those oops moments) and still have the ability to add manual nodes to areas the auto missed.

I'll be watching this one.

#9 > I'll be watching this one.

me three.

#10 me four

#11 I would be interested in a product like this as well. Let me know when you are ready/plan on sell/licensing it.

#12 Hey,

I know this is a very beginner question, but what exactly is PathFinding?

#13 It's how your AI characters move around in the game world... Say for example you need to get from A to B well pathfinding would work out how to get there.

#14 Keep us updated, I'll be waiting for release.

I'd tell you what else I wanted in the setup but I have not looked into this area much and from the screenshot it looks easy enough to implement mission-by-mission.

Also try and stay within the TGE1.5.2 setup as well.

#15 yep another one watching this ;)

#16 We've started working on a system albeit a little later than planned due to some alpha bugs that needed to be fixed first, we're taking a slightly different approach than this to Wesley and have the workings of useable navmesh editor already.

I'm hoping to have some information to share on the pathfinding side of things in the next couple of weeks including some early screenshots of how it might work.

#17 I am sorry i have not given this much attention lately. Acctually got myself bogged down on several seemingly simple things. Always the simple stuff that seems to get you in the end sigh....

I wanted to create a search table for the grid. So that you could check and see if any given point resides in a polygon (as well as which one) or not. The obvious uses such as having a starting point for pathfinding or use for quick querries via script made it seem like an obvious next step. The problem may have been my approach but i decided to try and break the game world up into regions and hash to those then once we know the general square region the point resides in and all polygons in that region we could alot more easily figure out if we are in one of the polygons or not.

Well to make a long story short i once again realized my annoying lack of 3d math up to this point and got fed up enough to go out and do somthing about it. The college i am going too does not have any classes directly related to 3d math sadly so i went and got myself a good and easily understandable book and have been working through that lately. So i am afraid not much has advanced on my approach other than i am to the point i have decided i need to rethink my approach a bit because i think that will save me alot of hardship down the road.

Other than that what i am really worried about is just do not quite know where the market is at the moment. We have TGE TGEA and torque 3d coming out. Since i only know the in's and out's of TGE at the moment I feel pretty restricted. I am hopeing that porting code up from TGE to TGEA and then to Torque 3D will not be that complicated.

@Andy Rollins I beileve is working in TGEA I am hopeing to hear back from you again sometime.

in a nut shell i am back to working on this.

#18 Hey Wesley, we're in much the same situation as yourself haven't really touched our pathfinding much over the last couple of months, a busy period for me and Dan's been moving house.

Moved on a fair bit from the last blog I posted here but was hoping to have been finished by now.

I've got TGEA and Torque3D so can say that porting to either platform isn't that hard from TGE - not for pathfinding stuff, the hardest part would be getting the rendering working the rest would probably run pretty much straight as is.

#19 Hey guys, you should check this, could be useful.

Andy, the video looked realy promising, as well as the Wesley planned features. Nothing serious yet about team up?

#20 Oh my, I think i have been put out of a job by that. It says it is even open source.

Simply put, getting a proper navigation mesh togheter is acctually the lion share of the work. The acctual A* algorithm is remarkably easy and simple once you have the mesh. Of course i am not including any thoughts for optimizations to the algorithm and of course i might be over reacting since i am just going off my first impression of what i have read about it in those posts. Things always sound better and easier to use in the text describing what it is supposed to do than reality will mercifully allow. I think if nothing else it would be interesting to dig through and see what they did as well as try and get it working for torque.