3D Navigation Plugin

Development Pipeline & Plugins Plugins
1

Another plugin! After watching Daniel Brewer’s GDC talk on SVO navigation, I thought I’d give it a go…so what we have here is basically a straight UnrealEngine implementation of what is described in this talk :

https://www.gdcvault.com/play/102201…esh-Navigating

Code is here ( Contributions are extremely welcome and will be credited) :

Demo :

Documentation:

Capture.PNG.jpg
Capture.PNG.jpg952×682 61.4 KB

Capture1.jpg
Capture1.jpg967×695 325 KB

4 Likes
2

Hey @mid_gen - I really appreciate you making this plugin free and open source.

Got a few questions -

  1. What algorithm are you using for navigating the Volume? A*, Greedy A*, etc.
  2. What is Async Path finding?
  3. What is the max scene size that this plugin supports? or is there no upper limit?
3
  1. Greedy A* using Manhattan distance heuristic at the moment. I’ll be adding more option as covered in the GDC talk, such as unit cost, face vs. node centers etc.
  2. Async = pathfinding off the game thread, I only implemented the synchronous path so far
  3. No upper limit.
4

Update:

  • Removed custom AI and BT tasks, not necessary as the AI controller takes care of using the appropriate nav data
  • Known issue - the last segment used when following a target actor doesn’t respect any pathfinding…looking into it
5

All I can say is WOW… Very much appreciate the time and effort that went into coding this, let alone the quality and the fact you’re sharing for free…

6

quick question, how does this differ from DoN 3d navigation? is it a different method?

7

As far as I can tell, that plugin is using a uniform voxel system, as opposed to the sparse octree approach I’ve used here. Based on that :

DoN (Voxel) Advantages:

  • Simple data structure
  • Easy to update partial sections of the navmesh
  • Good for small, dynamic levels

SVO Advantages

  • Much more space efficient
  • Vastly improved A* performance across long distances
  • Good for huge, static worlds

Not that you couldn’t mitigate some of the disadvantages of each…but that’s roughly accurate. The DoN approach will die if you want to path across long distances, the A* iterations will kill you.

8

Update:

  • Added the unit cost distance travelled pathfinding option. Available in SVONavigation component.
9

Thanks for the answer, definitely going to give this a go, I’ve been using DoN to control my flying drone ai,and yeah it can get very sluggish on my 7.5kmX 5.5km map

10

Updates

  • Added Estimate Weight settings (greedy A*)
  • Added Node Size Estimator pathfinding optimisation setting
11

I’ve added the plugin to my demo project, and started making some demo levels/AIControllers/BT/BB

12

mid_gen, Thank You a lot for work on this (and CashGen, and plugins). It is really exciting we will have alternative to DoN’s 3D pathfinding. Well, there is also “Mercuna” system, but that is out of reach by price. Btw, if anyone knows some more (free or cheap) less known 3D navigation / AI systems, please maybe post here info. Thank You.

13

I just tried to use this in my game , I dragged the UESVON master folder to my game plugins folder but I’m getting error that the binary’s are missing.
What Am I doing WORNG pls

14

You’ll need to build the project with visual studio. Right click on your UPROJECT file, ‘Generate Visual Studio Files’, then launch the .SLN, and build.

Work on plugins is pretty much at a standstill during this summer heat as my study is just too hot to work in in the evenings. I did manage to clear up the various issues/PRs I had on github yesterday morning before work though!

15

sorry but Im kinda lost. Whats SLN and uprojectfile.
I don’t have Visual studio installed, I’m not a programmer ,I’m using BP’s
Is there a complied version?

Edit: oh you mean the project launcher file. got it! but still unsure about SLN

16

Hello! If UE4 project has C++ parts (that might be also plugin as here), it needs to be compiled. You should install Visual Studio (i use 2015, Community Edition, I guess that it was called). You will need it sooner or later, and - you need it now :slight_smile: Now, important: i am also not a programmer, and I jumped into UE4 because it has visual Blueprints. I am bad at math, programming, I don’t have that kind of brain. But - believe me, VS is not that scary :)) You just need: common sense, logic, web searching, dedication. :slight_smile: Not necessarily in that order.
So, basic steps here will be: right click on project file, and “generate VS files”. It will make SLN file. That will open in Visual Studio, when you have it in system. Then - “build solution”, pray. :slight_smile: If it gives error(s) - use those common sense and search ingredients I mentioned :slight_smile:

17

Thanks for the breakdown Thunder_Owl :slight_smile:

I will install this Visual Studio Community 2017
Free, fully-featured IDE for students, open-source and individual developers. I noticed there is some support option for unity but nothing for UE4 on the setup , is there anything else I should consider doing for UE4 integration

18

Yep, that’s it. Check ‘Options for a new Visual Studio Installation’ in this document :

19

I have no Idea what Im doing in vs & Just keep getting
the following modules are missing
UE4EDITOR-UESVON.dll
UE4EDITOR-UESVONEditor.dll

and it wont compile.

am i supposed to create a plugins folder and drop the whole file contents to that or just to the root of the game project folder.

20

ProjectFolder - Plugins - usvon
that would be where to place.
AlphaWolf, for “practice” you can start with running current CashGen-Demo from Github (link was on previous page, I think). I downloaded and compiled today - all was without hickups, and it contains working “uesvon” with demo map. I will tell here steps I do, downloading, copying, compiling.
Go here: GitHub - midgen/CashDemo: Demo project for CashGen, UnrealFastNoise, GOAPer and “download ZIP”.
Now, interesting part: in that same opened page, browse into “plugins” folder.
After that, browse into each plugin sub-folder, and there download ZIP with that particular plugin that will open as page.
Downloaded files will look a bit like in screenshot I attach here.
Unzip CashDemo project. There are plugins folders already, but empty. Fill them with appropriate unzips of plugins you just got.
Simply try to run CashDemo project after that. If all good, it will compile stuff for some time, and run as normal project (go open some demo map, cashgen or uesvon).
Good luck… :slight_smile: