Working group: navigation

#1 My two cents, I believe you should definitely have automatic path finding. I know it's off topic but it should also be planned in parallel to some sort of AI Behavior editor. That way everything would be build to support each other.

#2 By automatic, do you mean replanning when the navmesh changes, or planning when the path is first created? The former I removed because the API was messy, and we should decide on a standard as a community. The latter I removed because it made the NavPath API unclear - it seems better to have an explicit call to plan() so you know for sure when the path will be available.

Initially, I'd like to make this stuff as little-dependent on the editor as possible. For example, now that navmeshes can be built tile-by-tile in the background, I'd like to have the navmesh automatically rebuild itself whenever you unselect it in the editor. So if you select it, change its position, scale it a bit, the unselect it, it will update automatically. I also want to make it such that adding or dragging shapes in the editor triggers an update for the tiles that are affected.

This means the workflow becomes very simple, and the navmesh keeps itself up-to-date automatically. Of course, if we wanted to add features like jump links and area painting, we'd have to look into a dedicated nav editor like Walkabout's, and that'd definitely benefit from being developed alongside an AI editor.

The problem is, every game's AI will be so unique that coming up with a generic editor sounds very complex - or, like we could develop an editor that is so generic it's pretty much useless. The same goes for navigation, unfortunately, but I think pathfinding is similar enough among a lot of game types that we should be able to make better progress.

EDIT: personally, I'm kind of waiting to see what happens to Jeff Raab's behavior/component system. I think that will cause a lot of change in T3D's editors if it becomes widely adopted, and I think it should be part of any AI system that is stock in T3D.

#3 I need more time to play with recast, but i want to contribute to Torque AI/Navigation stuff.

Thx for all your work.

#4 Awesome. Are you interested in any parts in particular?

#5 @Daniel,
Yes I was talking about automatic replanning when the navmesh changes. Honestly you are more of a expert in the area than I am, so I think you would have a better more thought out plan for how things should work. I totally agree that it should be done with or in parallel to Jeff's behavior system. The behavior system should be basic. Maybe something like having the ability to create a new datablock for the AI. Set up things like predefined visual states, Simple actions, High-level actions like fighting enemy with different types of weapon (melee or distant), chase/flee enemy, patrol territory, wandering around. A sensor system allows AI entity to emulate eyesight and hearing in the virtual environment.
These are things MOST if not all games would use, so it's not gerne specific. That way the Navigation part would take care of the pathfinding. Actually guidebot's system would be a good place to look at for a NavMesh and AI behavior editor.
This is a related topic but should things like dynamic cover points be handled?

#6 Heh, fair enough - I guess once the basic pull-request is submitted I'll start to work on some additional features like that, propose them, and see what people think. Basically, in the original resource (and still a bit in Walkabout, unfortunately) the navmesh event API was very unclear and a bit ad-hoc: I just added in whatever events I needed to make stuff work, without any forethought.

I guess important events to consider are:

• A single tile has been rebuilt (this event might be fired during gameplay)
• The entire navmesh has been rebuilt (avoids having a spam of individual rebuild messages; will probably only happen when the editor is running)

...which is surprisingly few. Not sure why I wrote that as a bulleted list :P. At the moment, there's also a load event which isn't used as far as I recall. Walkabout stuffs a ton of information into the tile update event (such as progress percentage) which might benefit from being separate events.

Disclaimer: if any owners of Walkabout are worried about me being so blase disclosing information about its insides, and porting features to MIT3D: don't panic. I'm treating the two projects as very separate beasts. Walkabout is all about the editor, advanced features like coverpoint generation, and total integration (for example, AIPlayer::setPathDestination). This MIT port is about solid basics, providing a platform for other people to work on, and modifying the rest of T3D as little as possible. Improvements will be ported in both directions, but I'll rarely be grabbing code wholesale out of Walkabout for MIT3D. (Exceptions include support code like the debug drawer, recastPolyList, etc.)

Kory: that makes sense. I guess a good first port of call would be to ensure we have a complete list of desired basic functionality in pathfinding. For example, following a path defined by waypoints in the level.

I also think a lot of this functionality should be implemented in scripts - for example, path following - but I'd like to wait and see what Mike's modular templates look like first. When they happen, we should focus on creating a pathfinding script module that adds common features like that.

Also, while we're here, we should probably ensure we fix all the bugs that need to be fixed from the RR. Off the top of my head:

• Long paths fail, as pointed out by Steve.
• Terrain is only half built, though this may not be anything to do with the recast code (but we should still try to fix it, if the issue is present with the new meshloader code)

Dynamic cover points as in moving ones, or ones that react to changes in the navmesh i.e. destructible cover? Actually they'd both be pretty cool, though the latter would be more common. This shouldn't be too difficult to do at a basic level - when a tile rebuild event happens, search for all the cover points inside the tile and re-evaluate whether they should remain, or be downgraded to a different stance or whatever else needs to happen.

If someone coomes up with an automatic coverpoint generation solution, then you could simply remove all the cover points in the tile and regenerate them.

ALso on the to-do list should be properly multi-threading the build process, rather than just spreading it out over multiple ticks.

Recast resource, because I keep needing to find it and Google isn't helping.

#7

Quote:ALso on the to-do list should be properly multi-threading the build process,

And the rest of the engine... lol

#8 Yeah, that was the challenge when I did it originally in the recast resource... I could multithread the navmesh build but nothing else was threadsafe, so if I wanted to, for example, access the bins to parse collision geometry... well, here be dragons.

Having learned a little more about concurrency since then and having implemented a tiled navmesh the process should be much easier. Now the main thread can parse collision geometry one tile at a time, and add those tiles to a dirty pool. The entire recast process can be performed in a separate thread for each tile (or even among a group of threads that all grab tiles from the pool), and then the data is dumped back into the navmesh in the main thread.

The idea is to do only Recast stuff in the separate thread, sidestepping all Torque's non-multithreadedness.

#9 Daniel's Recast based pull requests have been merged into the Development branch.

To enable the "navigation" module as a selectable module in the Project Manager we'll need to modify the modules list in projects.xml to add a new entry:

<module name="navigation">Recast Navigation</module>

Once that is done Recast will show up in the list of module choices. Otherwise you'll need to manually add a line to buildFiles/config/project.conf for each project you want to use Recast with:

includeModule( 'navigation' );

#10 @dB,
Is there a way to pause the AI updates on individual AI? I have a concept where I possess different AIs in game. I want to be able to have the AI pause when I take over an AI and resume when I leave the AI. I also want to train the AI while I am in possession of the AI and perhaps allow limited AI action. I know this is kind of application specific though.

#11 Presently using a raw object-to-target distance comparision + script-based comparator callback (several, actually) for comparing weighted distances between multiple targets. If it isn't too heavy weight, might be a good idea to have something similar based on projected navpaths to shore up the one to many end of things.

#12 Mike: so awesome to hear that :D. I've pull-requested the projects.xml change.

Demo: not sure what AI updates you're referring to. As in have them stop pathfinding? Just call .stop().

Azaezel: as in finding the shortest path distance to an object? You can do that with navigation by accessing NavPath's .length property for each path to your multiple destinations. But yeah, I've always wanted to add some sort of automatic way to do this.

#13 @dB,
I was hoping it was that simple. I am just not very familiar how the system works to begin with. I thought there was more to it.

#14 Daniel,

Bout freakin time (just kidding)! Grats on working it out. By the way.... Been adding recast to every build I have been making (it is MANY). This path finding solution (if you know how to use it) is AMAZING.

Just cuz not many people say it, and you deserve some recognition. Good work and thanks for your time, I know your time is precious (skilled programmer that you are, not gonna comment on that except for all the 'contact' stuff you have been getting) and honestly, having your skill level and professionalism involved in the MIT project is awesome! Guys like you and Mike and Dave and the new Committee guys will only make T3D a better engine.

Ron

#15 @Ron,
I second your comments about the dB.

#16 Aw shucks guys :).

Demo: I think I understand what you're talking about now. It's honestly totally beyond the scope of navigation - currently T3D has no such thing as an 'AI update'. Pathfinding with this resource is done completely independently of the AIPlayer class, and the found path is followed by a character using the standard Torque AIPlayer scripts (or something similar). If you want your character to stop moving, call .stop() and delete the NavPath they were following. To resume, just find another path to the original destination and start following it.

This is all part of higher-level logic than my pull request provides.

#17 @Daniel: Sorry to butt in here ... tried to mail you but I had some issues. Is Walkabout compatible with Torque 3D MIT? I am a license holder of Walkabout. :)

Thanks

Edit: @Azaezel: Yeah ... I maybe should have read the documentation better ... my bad. :)

"Should work out-of-the-box with Torque 3D MIT 3.0." -- *slaps self*

#18 @Quinton: It is. Just got a fix for compatibility with the latest, in fact.

http://www.garagegames.com/community/forums/viewthread/132276

@Daniel: Ahh. Dunno how I overlooked that one. Thanks. Will see how that goes when we're talking upwards of 50-100 potential targets.

#19 For the record, questions about Walkabout should go to the dedicated thread in the addons forum. I'll probably mention Walkabout all the time in this thread because the work is related, but I'd like to keep a clear separation between MIT stuff and Walkabout. As much as is feasible.

Azaezel, yeah, 50-100 pathfinds in a single tick will push it... go for it though! I'd love to see a good and proper stress test of the system. Unfortunately, if it turns out to be infeasible, there's really not a lot to be done. We could reinstate sliced pathfinding, but that comes with its own issues like needing to write asynchronous code, which souynds like a pain in TS.

#20 @dB,
I was thinking there was some kind of AI think hook. I am sorry for the silly questions as I have not looked at the resource.

If you want examples of how to control an asynchronous thread using TS check out my Audio RTT resource. It does this and I believe is a good example of how to control threads processes from script.