x

Search in
Sort by:

Question Status:

Search help

  • Simple searches use one or more words. Separate the words with spaces (cat dog) to search cat,dog or both. Separate the words with plus signs (cat +dog) to search for items that may contain cat but must contain dog.
  • You can further refine your search on the search results page, where you can search by keywords, author, topic. These can be combined with each other. Examples
    • cat dog --matches anything with cat,dog or both
    • cat +dog --searches for cat +dog where dog is a mandatory term
    • cat -dog -- searches for cat excluding any result containing dog
    • [cats] —will restrict your search to results with topic named "cats"
    • [cats] [dogs] —will restrict your search to results with both topics, "cats", and "dogs"

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

Product Version: Not Selected
Tags:
more ▼

asked Dec 22 '14 at 04:51 PM in C++ Programming

avatar image

ethanmac
8 2 5 6

avatar image RoboticHuman Jan 20 '15 at 03:16 PM

I Have the same problem here :D 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?

avatar image ethanmac Jan 20 '15 at 09:05 PM

Hi RoboticHuman(cool name btw :) )..if you figure out will you let me know.Il let you know if I make any progress on this also

(comments are locked)
10|2000 characters needed characters left

3 answers: sort voted first

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

more ▼

answered Dec 22 '14 at 06:46 PM

avatar image

MieszkoZ STAFF
7.2k 223 56 407

avatar image ethanmac Dec 22 '14 at 07:09 PM

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

avatar image MieszkoZ STAFF Dec 22 '14 at 11:12 PM

No worries :) 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 :D

avatar image ethanmac Dec 22 '14 at 11:13 PM

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

avatar image ethanmac Dec 22 '14 at 11:20 PM

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.

avatar image ethanmac Dec 23 '14 at 11:34 AM

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.

avatar image MieszkoZ STAFF Dec 25 '14 at 05:32 PM

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*.

avatar image ethanmac Dec 28 '14 at 09:56 AM

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

avatar image MieszkoZ STAFF Dec 28 '14 at 10:09 PM

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.

avatar image ethanmac Dec 29 '14 at 05:59 PM

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?

avatar image MieszkoZ STAFF Dec 29 '14 at 09:28 PM

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.

avatar image ethanmac Dec 29 '14 at 09:34 PM

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

My apologies for all the questions

avatar image MieszkoZ STAFF Dec 29 '14 at 09:37 PM

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.

avatar image ethanmac Dec 29 '14 at 09:45 PM

cool :D .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

avatar image ethanmac Jan 19 '15 at 12:34 PM

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

avatar image MieszkoZ STAFF Jan 19 '15 at 12:44 PM

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

avatar image ethanmac Jan 19 '15 at 01:13 PM

thank you :)

avatar image ethanmac Jan 20 '15 at 03:04 PM

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?

avatar image MieszkoZ STAFF Jan 20 '15 at 04:01 PM

Yes, the actual pathfinding is being done in navmesh code (boils down to calling ARecastNavMesh::FindPath). I suggested overriding UNavigationComponent::FindPathToActor and the other function so that you can put your whole pathfinding there. The proper, long-term, blessed solution would be to derive from ARecastNavMesh and implement your own pathfinding there. I'd wait for 4.7 before doing that though since there were some changes that will make your life easier if you wanted to follow that route. If you do let me know if you do.

avatar image ethanmac Jan 20 '15 at 08:51 PM

Il try to keep doing it in 4.6 until 4.7 is released.If I havent gotten anywhere I will then try the ARecastNavMesh.

If I override the functions specified in 4.6 can I still leverage the API to obtain the information necessary to run the algorithm?Is there any guides or further documentation on this subject.It is all very abstract to me and harder to see where it all links together. I have been looking at the source for around a week now and I'm no closer to figuring out how to go about implementing my own, even though your help has been really good.

I do apologize for all the questions this developing in C++ for Unreal is still very new too me :(

avatar image RoboticHuman Jan 21 '15 at 12:34 PM

I think what ethanmac is trying to obtain is the graph of nodes created by Recast's navmesh, so that he can run his A* on. Is this even the case with Recast? does it produce a graph of nodes or does it work directly on the polygons? If there is a function in UE that retrieves such a graph it would be great, but if you really want to get down to the very bottom, then DetourNavMeshQuery.cpp has the implementation of A* as far as i can see (the findPath function). Please correct me if i'm doing it the wrong way MieszkoZ cause i believe i really am going the wrong way since this is too deep down in core code. Thank you for your perseverance btw :D

avatar image ethanmac Jan 21 '15 at 12:40 PM

yes thats soort of what im looking for.I can then run D * lite on that which shouldnt be too difficult

avatar image MieszkoZ STAFF Jan 21 '15 at 01:11 PM

Recast does have a kind of graph-like representation under the hood, but it's not really exposed to UE4 users. You can however obtain it with a bit of effort and dtNavMeshQuery::findPath is indeed a good place to learn how it could be done.

avatar image ethanmac Jan 21 '15 at 01:22 PM

Would this be more difficult then the approaches suggested earlier?If I couldnt figure those out I think this could be beyond me at this point in time.I cant seem to wrap my head around how to encompass all of this together.If A uses the RecastNavMesh then it should be possible for D light ?Is this an advanced topic though?

avatar image MieszkoZ STAFF Jan 21 '15 at 01:35 PM

Hard to say. It depends on your C++ expertise and how deep you're willing to go. But if you want to reuse whatever recast generated then you'll need to get familiar with the way it stores the graph anyway. Unless you're willing to setup custom navigation data, but it doesn't sound like you do.

The bottom line is now you need to give those ideas a try and see which works best for you.

avatar image ethanmac Jan 21 '15 at 01:49 PM

I would be willing to do anything. Its just I dont know how to go about it. To build my own custom nav Id need certain info for the engine I think?

I completed a module in C++ last semester. So Im not an beginner but not an expert by any means.

THanks again for your help

(comments are locked)
10|2000 characters needed characters left

hey guys thought Id give an update.I may have bitten off more then I can chew in this case because I still do not have the faintest idea of how to do an implementation in UE4 .Perhaps I would need to gain more experience with UE4 before attempting this. It wouldn't be possible to mimic such behavior in Blueprint?

Thanks for your help Mieszkoz my apologies that I was unable to take your advice and implement it

more ▼

answered Feb 05 '15 at 04:03 PM

avatar image

ethanmac
8 2 5 6

(comments are locked)
10|2000 characters needed characters left

Hi ethanmac, are you still having the problem?

The way I see it, the important points that the Unreal's navigation provides for your example are:

  • implementation of pathfinding algorithm

  • moving along the path found by the algorithm

You can either:

  1. Use them (described in the documentation)

  2. Implement your own pathfinding deep in the engine and use the provided path following (described by MieszkoZ)

  3. Implement your own pathfinding, and according to your requirements you may not need the Unreal navigation at all. But in that case you have to implement the movement yourself.

So in 3 a simple approach is to:

  • create the pathfinding D*, A* in any way suitable but with clear interface, e.g. that accepts as parameter an FVector (destination) and gives a result, for example a TArray of FVector through which the character will pass in a tile based world.

  • given that your characters are not driven directly by user input, you'll probably have an AIController. Call either of your pathfinding algorithms in your AIController in your overriden version of MoveToLocation(FVector location).

  • use the path found before in a new custom UCharacterMovementComponent, which in the method PerformMovement(float DeltaTime) can implement the actual movement of a character.

In this way the desired pathfinding behavior is regulated by your AIController, while the character movement by the UCharacterMovementComponent. So to provide distinct movement characteristics between the predator and the evader you only have to implement their UCharacterMovementComponents accordingly. This worked fine for me, if it helps I can give you more information.

more ▼

answered Jul 23 '15 at 10:33 PM

avatar image

ntk4
1 2

(comments are locked)
10|2000 characters needed characters left
Your answer
toggle preview:

Up to 5 attachments (including images) can be used with a maximum of 5.2 MB each and 5.2 MB total.

Follow this question

Once you sign in you will be able to subscribe for any updates here

Answers to this question