Implementing pathfinding algorithms in an AI agent?

Hi

Im completely new to UE4 and in my infinite wisdom i decided to do my FYP project on D* real time pathfinding.Im just wondering where would this be implemented.Ive looked over the documentation and video tutorials a bit but I cant find exactly where it would fit in.Can anyone point me in the right direction?

Thanks

It depends on what level of access to recast navmesh or other bits of navigation system you need.

The best way would be to create your own ANavigationData-derived class (or ARecastNavMesh if you want to reuse recast generated navmesh), implement pathfinding function and assign it to ANavigationData.FindPathImplementation (see how ARecastNavMesh does that). To have your custom navigation uses instead of RecastNavMesh add following to your DefaultEngine.ini file:

[/Script/Engine.NavigationSystem]
RequiredNavigationDataClassNames=/Script/YoutProjectName.YourNavigationClass

Alternatively implement your own AIController and override RequestPathAndMove (provided you’re using UE4’s master branch, this has been refactored recently). This function calls navigation system to find a path, you can make your own calls there.

Let me know if you have any more questions.

Cheers,

–mieszko

the situation I wish to implement is to have a predator using a form of d*(d* lite) pursue an evader who uses A* to navigate the environment…Sorry if I don’t pick your tips up right away i’m new to programming in Unreal.

sorry forgot to mention I wish to try and do it in C++.Or a combination of C++ and blueprint if its more suitable.

Thanks

im completely lost on this so any help would be much appreciated

i had 4.4 version of the source on my laptop. …will i have to download and set up all the source code again as I did for the previous version of the engine?

RequestPathAndMove would then call D* if im correct?

Thanks for all your help on this.

No worries :slight_smile: I’m going to assume you’re working on UE4 github master branch, or at least the promoted branch.

If you want to support both pursuer and the evader on a single, recast-generated navmesh, then you need to implement a special AIController-derived class for your pursuer, and hijack (override) RequestPathAndMove function to run your D* instead of the generic recast A*.

Let me know if you need more guides :smiley:

ok i think I am on the master branch now…Would A* for the evade require the same override?Is there any place in particular with tutorials on this or is it just the documentation?

Happy Holidays.

Your implementation of RequestPathAndMove would call your D* implementation, yes. Regarding A* it’s already implemented and can be used via default AI API. Unless you want to have your own A* implementation - if so use the same route as for D*.

Will this work on the latest release 4.6.1?Thats what I have installed on my machine…Thanks a milion for your help

Unfortunately this has been refactored after 4.6.1 shipping. You’ll need to wait for 4.7 or use UE4’s github master branch.

So does that mean I cant implement D * on the 4.6.1 release?
I need to do this for a project so I need to know asap if its possible. the master branch wouldn’t install and setup correctly on my computer

If I downloaded the source from Unreal git hub last week would the master be included. In my unreal launcher I only have 4.6.1?

ok thank you…do you know which functions i would have to override in 4.6

My apologies for all the questions

cool :smiley: .I think i may stick with 4.6.1 because I need a stable release to work on for the next three months for my fyp.I will take a look at UNavigationComponent .THanks a million :).Il let you know how it goes

You can implement D* in 4.6 in a similar fashion to what I described, but you’ll need to override different functions.

Regarding getting sources from the github repo, provided you got promoted or master branch you’ll be fine.

Come to think of it it might be actually pretty easy before the RequestPathAndMove as well. I don’t remember the specific functions, but look at the way UNavigationComponent is used and at its API. UNavigationComponent has been removed as part of a larger refactor, but it was responsible for triggering pathfinding for it’s AI-owner. You should be able to implement a custom navigation component and put D* implementation there. Just bear in mind that UNavigationComponent goes away in 4.7.

Hi thought id give an update.Ive been looking at the API for a few days and I cant seem to find where exactly in UNavigationComponent that the default behaviour is implemented

Overriding UNavigationComponent::FindPathToActor or UNavigationComponent::FindPathToLocation should be what you’re after.

thank you :slight_smile:

ive been looking over these functions extensively but I just cant seem to find where the A * code is implemented.They seem to call a query class that returns the path am I correct?But when I follow its path I cant seem to find A *…would that implementation be in one of the navmesh classes?

I Have the same problem here :smiley: I’ve been searching for the A* implementation for days now!(wonder how you guys at Epic find your way through all this lol) The thing is i want to see how you guys handled the information flow in your algorithm and i mean by that where you get your graph data from and all this so that i can start putting things together. I’m quite lost as ethanmac obviously. It would be great if you can help us out MieszkoZ. Is the A* impelmentation available from Epic’s side or is it something done internally in Recast and that’s why i can’t really find it?