Progress on A* Navmesh and multiple agents surrounding player WIP

Author

Message

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 22nd Jun 2019 04:05

Link

I guess I have come a long way from the beginning, but I have been working on this for about a month, now. I am getting really frustrated, so I came here to see if anyone has some suggestions to perfect this. Plus, its always nice to vent and get your thoughts out.

It was really bad at the beginning. My paths were taking from 10seconds to about 20MS being the fastest. Trial and error got me down to about .5MS-2MS.

I use a Navmesh based A* pathfinding. To make the Navmesh I use Blender's Navmesh function - quite handy. I do not use a heap, I use AGK's sorting. My testing showed it was faster than using a heap. I tried out a navmesh with less nodes, and for some reason I got slightly worse performance not just in terms of the pathfinding, but also my agents would not surround my player as well. Its possible my algorithm was including too many neighbors, thus slowing it down. Testing and adding neighbors is a huge bottleneck for A*, if you are unfamiliar.

Currently, to surround the player I have 8 nodes that surround the player that can be occupied, once an agent chooses that node the node is no longer available(or if the node is inside a wall). The agents move to those nodes. I currently have a bug that doesn't make the agents land perfectly on those nodes. I have been unable to track down the errant code/algorithm.

As far as trying to make the agents avoid each other:
I want to preface this by saying this might need more trial and error on my part:

I have tried Raycasting - it usually misses any obstacles. I wanted my agents to "bounce" off each other if they got too close. Sadly, the raycast is very unreliable. It probably needs further refining(ie testing each individual object). I currently send out 5 rays. Straight, MidRight,Right,MidLeft,Left. It still failed to detect an obstacle 99% of the time. I am sure I am doing something wrong, I just haven't figured it out. I got it to work perfectly using it on the player to avoid obstacles.

SphereCast provides too random of a point to use.

I have tried ObjectSphereSlide - this has potential but the agent is likely to get stuck on the obstacle. It would be really nice for the developers to show this in use. I don't know how to use this properly.

Note: The player does not avoid obstacles, because I wanted to test the agents ability to find the player.

Back to top

Profile PM

blink0k

Moderator

11

Years of Service

User Offline

Joined: 22nd Feb 2013

Location: the land of oz

Posted: 22nd Jun 2019 04:39

Link

Sounds like heaps of work.
It says the video is unavailable

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 22nd Jun 2019 16:05

Link

Quote: " My paths were taking from 10seconds to about 20MS being the fastest. Trial and error got me down to about .5MS-2MS."

How large were the maps?

The video doesn't work

Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Back to top

Profile PM Email Website

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 22nd Jun 2019 17:47

Link

Uh, weird. It was set to private. Not sure how I managed that...

The map is a 100X100. The small white blocks are the nodes.

Back to top

Profile PM

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 22nd Jun 2019 19:15

Link

I tweaked a few things, and they are doing better at staying separate. A few problem areas that I need to work on. The agents seem to find new positions when they don't really need to. Like if my character moves a smidgen they are trying to find a new path instead of just backing up. I still haven't solved what I will do if the character is in a corner and only has one slot available. Currently, the agents won't move. I need to make them move to the character and wait for a spot to open up. I'm not sure how to do that without a bunch of extra work. Open to ideas

I got the ray-casting to work much better. Not real sure what I changed, tbh. I think my length might have been too short.

Back to top

Profile PM

chafari

Valued Member

18

Years of Service

User Offline

Joined: 2nd May 2006

Location: Canary Islands

Posted: 22nd Jun 2019 22:59

Link

Great work Golelorn ! I like it !

I'm not a grumpy grandpa

Back to top

Profile PM Email

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 23rd Jun 2019 03:12 Edited at: 23rd Jun 2019 03:19

Link

Thanks, bud. A lot more work to do, though. There is so little information out there for A*, navmesh and AI path-finding. Crazy, since this something that was solved over 25 years ago. I remember playing Might and Magic VI in 1998, and the mobs did it a lot better than my current way of doing it. Although, if I recall correctly, they did stand on top of each other. But Age of Empires just a few years later had it perfected.

I remember playing EQ in 2001, and while the path-finding could go wonky it was pretty damn impressive. It got better with the expansions. I don't expect to create any cutting edge tech, but damn surely I can meet the standards from 15 years ago.

Back to top

Profile PM

PSY

Developer

8

Years of Service

User Offline

Joined: 3rd Jul 2016

Location: Laniakea Supercluster

Posted: 24th Jun 2019 19:39

Link

Quote: "I remember playing EQ in 2001"

Man, I played that game for 3 years in a row.
Waiting for Pantheon: Rise of the Fallen. It's being developed by the original guys from EQ

PSY LABS Games
Coders don't die, they just gosub without return

Back to top

Profile PM Website

Rick Nasher

7

Years of Service

User Offline

Joined: 25th Jul 2017

Location: Amsterdam

Posted: 24th Jun 2019 22:53

Link

Looking good!

Back to top

Profile PM Email Website

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 4th Jul 2019 00:25

Link

Here is my current progress. I still haven't been able to keep the agents off each other during the pathing. I have tried multiple strategies.

I currently have the player surround by 48 nodes. 8 are designated to be Next to Player. If one is open, the agent will move there. If its not open the move to the next closest slot, and wait.
The slots are closed if another agent is in it, the is no LOS for the player, or there is an obstacle in the way. I have the code to correct the pathing through the edge of the walls. Hopefully, I can just plug it in and it works.

I also plan to add code that if the agent is not exactly on its node it will slowly back up to its node. This should prevent the agents from touching whilst close to the player.

My plan to force the agents to avoid each other is to switch from the Navmesh to the grid surrounding the player. Every other method I have tried works sometimes, but always has a catastrophic failure.

Thoughts? Anyone want to share their hidden secrets?

Back to top

Profile PM

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 6th Jul 2019 18:14 Edited at: 6th Jul 2019 18:18

Link

I have the agents avoiding each other fairly well. There are a few problem spots. I think if I could space out the agents a little better they wouldn't run into each other so much. Or create more nodes near the player to use a guide.

I have yet to test adding a gridbase around the player, but I think that will by this week's project. I am still not able to get this right. I also will be trying to add a centripedal catmull rom spline to the path, if I have to go that route(will of course have to figure out how that works exactly). It doesn't work well with the Navmesh because there are so few points. But a gridbased A* will need it for realistic movement.

Back to top

Profile PM

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 8th Jul 2019 20:20

Link

So, I decided to try going back to a grid based A*. I was finding it too tricky to keep the mobs off each other, and most of the time it just looked unnatural. I kept running into problems that started making the code look absolutely nuts. I read somewhere if your code starts getting messy you're going about it the wrong way. So, for now, I think I am shelving the Navmesh idea until I understand more about steering mobs. There aren't enough nodes to keep the mobs separated.

Instead of covering the entire map, I have the grid follow the character I don't really need it to cover the entire map, and that is just extra nodes to slow down the process. If the mobs step outside the grid, my plan is just to have them go back to their starting position.

I've tried a few "tricks" to get rid of turns some of them were too costly. One I think works well is searching neighbors -2to2 instead of -1to1 loop. This does add some processing time, but the paths are much straighter.
I also add a cost if the new direction turns from the old direction.To keep the mobs off each other I add cost to the node they are traveling to, and then reset the node once they are out. I am not sure how well that works. It might be bugged. ¯\_(ツ)_/¯

My rotation to face the character is a bit off, I will have to debug it at some point. I am going to try and find ways to get it faster, so I can add more algorithms to make the path smoother.

Back to top

Profile PM

Golelorn

8

Years of Service

User Offline

Joined: 20th Nov 2016

Location:

Posted: 13th Jul 2019 05:12 Edited at: 13th Jul 2019 05:31

Link

New videos. One is my basic. They other is I am trying to get a bit more advanced, and make the units try to switch locations. I don't quite have it down! Funny to witness.

I am disappointed that it took me this long to get the basic working. In the end it was very easy to make the agents avoid each other.

I have a few bugs. One is it can get caught on walls and go the wrong way, and then its just starts to jitter moving back and forth. I plan to add a timer on a per node basis. For example, if the agent has been trying to get to the current node for x amount of time it will find a new path.
The other is trying to swap locations surrounding the player so another agent can move in. Its really ugly. I will have to think about how to accomplish this. But I think this needs to happen. Just figuring out a good way to have the agents communicate is not clear to me, atm.

My goal is to minimize the use of a grid based A*. It very costly, and on top of that it needs even more computing power to make the path look natural.

Basic: