Announcement

Collapse
No announcement yet.

DoN's 3D-Pathfinding / Flying-AI system (with full source!)

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • replied
    really nice project! probably I will not use it, but seems to be good as a learning resource, because I'm planning to convert my wip custom pathfinder to a plugin in future...

    Leave a comment:


  • replied
    Sadly I'm not an expert either. But I'll really need this plugin for a future project.

    Leave a comment:


  • replied
    Originally posted by MatzeOGH View Post
    Stupid question but isn't an octree a better data structure for holding the voxels then arrays?
    I'm using a graph-like data structure that maintains node->neighbor relationships in a cache. I only use the 3d-array for lookup via index to quickly alter data. Octree support needs to be investigated.

    BTW I'm no expert yet! Feel free to let me know if you see something amiss. I tend to build my systems by continuous experimentation and patient prodding rather than by broad theoritical know-how. I hope to learn more and pick up new concepts as I gain more experience with game dev.
    Last edited by VSZ; 04-27-2017, 01:28 PM.

    Leave a comment:


  • replied
    Stupid question but isn't an octree a better data structure for holding the voxels then arrays?

    Leave a comment:


  • replied
    [MENTION=193494]aloneball[/MENTION] - Thank you

    I want to thank everyone for your continuous stream of encouragement, I didn't manage to reply to all but I deeply appreciate every single message from everyone!

    Originally posted by MatzeOGH View Post
    I think it would be helpful to look at the build in navigation system. Is it possible to optimize away all the empty voxels and rebuild them if you need them? I know it is a huge undertaking but making this plugin behave more like the build in navigation system would be so awesome.
    Re: optimizing unusued voxels, I've tried two approaches:

    1) A TSet driven "fully-lazy-loaded" system that would only create voxels "on-demand". The performance was awful! Apparently hash operations for looking up a unique voxel with an identifier(x, y, z) was just too slow. Granted, my hash function was probably suspect; I might revisit this some day.

    2) TArray with "reallocation-aware" usage: For best performance, voxel TArrays are only allocated once (BeginPlay) and references/pointers to individual elements are used by the various caches. This is how the system works presently.

    Now, to allow for "infinite worlds" where only those voxels we truly need are maintained the first step I took was to eliminate all dependencies on references/pointers in the code as these would be invalidated each time the TArray gets realloacted. So when I substituted all references with a tiny struct to hold a voxel's unique identifiers (x, y, z) and tested it, performance dropped significantly. The plan was shelved right there and I didn't even dare to try expanding the TArray on demand to see what the performance was like; I suspect it would have been even slower.

    One idea brewing in me now is a "nominal world" that gradually expands each tick as the game goes on, eventually maturing to "full world size". Won't work for all games (especially if players/AI can teleport rapidly) but it's something. I don't think serializing voxels to disk will help load times though. AFAIK rehydrating from disk into struct objects is slower than just creating them from scratch on BeginPlay.

    N.B. Collision checks are never performed on BeginPlay anyway, they're always lazy-loaded. If you turn debug voxels on with bAutoInitializeVolumes to false, the whole world will be full of green voxels until you actually start running navigation queries! Voxel collision for static meshes could be useful to cook, but this is not the real bottleneck for load times right now - the mere act of constructing millions of empty voxels whether loaded from disk or from code, is the thing determining load times now.
    Last edited by VSZ; 03-08-2016, 05:33 AM. Reason: for clarity

    Leave a comment:


  • replied
    Amazing addition to the community. Thanks for sharing!

    Leave a comment:


  • replied
    I think it would be helpful to look at the build in navigation system. Is it possible to optimize away all the empty voxels and rebuild them if you need them?
    I know it is a huge undertaking but making this plugin behave more like the build in navigation system would be so awesome.

    Leave a comment:


  • replied
    Originally posted by VictorBurgos View Post
    I've been cheating with "flying AI" with waypoints. This is obviously way superior
    Heh Waypoints are way easier to work with though! With a full-blown system users need to be prepared for bugs that are hard-to-reproduce, frustrating technical hitches, etc which, depending on the needs of a project may or may not be worth it. I've learnt the hard way that when a project onboards a fancy new piece of tech, it also acquires the technical debt arising out of it. Simple systems can be less prone to error and I think that allows developers to focus on actually making their game instead of fighting with tools that they might not even need for their project!


    Originally posted by MatzeOGH View Post
    Are the data structures generated on begin play or is there a way of building them in editor like the build in nav-mesh?
    Hey, this is a really important point you've brought up, thanks for that. Let me quickly explain the current status:

    --

    Loading time impact for large maps:

    The "voxel world" is currently built on BeginPlay so large maps with high voxel density (small voxels) will increase your loading times accordingly.

    For example, a world 500m x 500m x 100m with a voxel size of 100cm will cost you approximately 2.37 seconds of loading time (tested on my i7) and generate 25 million voxels in the process.

    This was tested with Visual Studio running in Development Editor though, Debug Editor mode is much slower IIRC. Packaged games on the other hand should be slightly faster.

    --

    I've tried cooking these into the map with mixed results:

    For my old "Adaptive Space Filling Volume" prototype (see "Legacy" sub-folder in source) I was using box component uobjects that were getting saved straight into the umap. This provide instant load time for the players (which is great!) but significantly increased the umap size (by hundreds of megabytes) and slowed down the Editor.

    For the voxel based solution I haven't been able to save it into the umap at all. I get a crash from ArchiveUObject.h in the line FMemory::Memcpy(&ObjectData[Offset],Data,Num);. If I turn the UPROPERTY flags off (just to test load times, obviously the data won't get copied) then the load times are actually slower than the amount of time it takes to just generate the structures each time on Begin Play!

    For maps at km x km x km scale I honestly don't know what the load times would look like lol

    I don't know if there is a way of properly cooking the voxel USTRUCTs into the map (and thus fully eliminate load times for users).

    For now the load times are somewhat reasonable for my game so I'm kinda happy to just let it slide!

    Leave a comment:


  • replied
    This is awesome! thanks

    Leave a comment:


  • replied
    thanks

    Leave a comment:


  • replied
    Are the data structures generated on begin play or is there a way of building them in editor like the build in nav-mesh?

    Leave a comment:


  • replied
    This is jaw-dropping. It's humbling just how much effort people put into sharing and helping the Unreal community.

    Leave a comment:


  • replied
    Well this looks awesome thanks for this!

    Leave a comment:


  • replied
    Freaking amazeballs. Good job. I've been cheating with "flying AI" with waypoints. This is obviously way superior

    Leave a comment:


  • replied
    Originally posted by MatzeOGH View Post
    This is awesome. Thanks

    Any reason why it is a developer uplugin? Aren't plug-ins that are flagged "developer" excluded from shipping builds?
    Ah... so that's the reason my packaged builds weren't working unless I added DonAINavigation to the PublicDependencyModuleNames.AddRange(....) list? (I forgot to mention that in the original post, thanks for reminding me)

    I'm setting it to "Runtime" now and re-testing...

    UPDATE: It worked! Thank you MatzeOGH for the tip, packaged builds work perfectly now and Blueprint-only projects don't need to meddle with Add code" and Build.cs anymore either!

    I've uploaded a new version of the plugin with this fix. The sample project still has the wrong uplugin but because it's nearly 2 GB I'm going to leave it alone for now

    --

    BTW thanks everyone for the kind words!
    Last edited by VSZ; 03-04-2016, 04:08 PM.

    Leave a comment:

Working...
X