Implementing pathfinding algorithms in an AI agent?

Development Programming & Scripting
21

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.

22

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 :frowning:

23

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

24

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

25

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 :smiley:

26

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.

27

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?

28

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

29

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.

30

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

31

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.