Fixing Path Finding

[tdphys]

So I'm not a backer,  expecting to Pre-Order and hoping to contribute to the *Profit* argument for POE

 

However,  I'd like to contribute and given that we now have 6 ish months,  I wonder if anybody could fill me in on what's wrong with 

pathfinding.    Does anybody know what algorithms/data structures OE is using,  and maybe we could set up some mock tests/frameworks and do some crowd source research on how to help fix it.   Does Unity come with its own pathfinding libraries?

 

 

 

Edit:

 

I guess this is what they're using, and why Sensuki keeps referring to Nav-meshes

     

 http://unity3d.com/unity/quality/ai

 

So what's the problem with the unity based finding in the beta's?  Is it a quick fix or something more substantial.  

 

Okay...  I assume it's A*  path finding using nav-meshes as detailed here.

 

http://unitygems.com/astar-1-journeys-start-single-step/

   

Edited October 3, 2014 by tdphys

[Matt516]

That's a good question. I see 3 possibilities:

 

1) The baked-in pathfinding is not very good.

2) Obs isn't using the baked-in pathfinding toolboxes correctly.

3) Some other AI stuff of modifications they've made to the pathfinding in an attempt to improve it have borked it up temporarily.

 

Personally, my money's on 3. Unfortunately, I don't know how much we can do to help them fix it if that's the case - other than continuing to provide feedback and details about when it messes up. Most of the issues I've seen deal with multiple actors moving at once and getting tangled up - which is orders of magnitude more difficult to get right than simple static pathfinding.

[Sensuki]

Another thing that *really* doesn't help is a combination of enemy creatures on the whole being larger than the IE games, area size in general being smaller and using larger creatures in areas with limited navmesh space (such as the spider groups in the Ogre Cave entrance and inside the cave).

 

Actors also don't seem to be making regular checks for 'shortest path' pathfinding checks, they seem to make a single check until a condition is met that interrupts it, which is why we are seeing ring-around-the-rosy instead of an actor changing their path to their target when there is a new 'shortest path'.

Edited October 3, 2014 by Sensuki

[Seari]

I hope they tone down creature size, those giant wolves look esp. silly.

[Sensuki]

If you want to take a look at the pathfinding source code tdphys I can tell you how to do it

[tdphys]

I'd love to see the code, but first steps I think would be to get a mock up in unity running with some toy nav meshes and pathfinding AI, then maybe we could see if we could match (ahehmm... maybe exactly)  the POE implementation.   I'm going to see If I can get Unity Editor running in wine on linux or in a VM.   Can somebody verify for me that POE is using Unity 4?  This will probably take a weekish , but hey,  we've got months now    Maybe some of you unity gurus can put a test case together.

 

Even if we don't help fix things, maybe we can inform the devs a little bit more, and perhaps learn something in the process.  I'm more interested in the pathfinding algorithms themselves, but I don't think some Unity chops wouldn't be a bad thing to acquire.

Edited October 3, 2014 by tdphys

[morhilane]

 

Actors also don't seem to be making regular checks for 'shortest path' pathfinding checks, they seem to make a single check until a condition is met that interrupts it, which is why we are seeing ring-around-the-rosy instead of an actor changing their path to their target when there is a new 'shortest path'.

 

They don't do "shortest path" algorithm, they do a "clockwise" check. I'm calling it clockwise because that's what it end up looking like in the game. seems like the scanning algo just keep the first "fit" and not the best one.

[Lephys]

It does appear to give the characters approximately the wisdom of a clock. 8P

[Hiro Protagonist II]

Another thing that *really* doesn't help is a combination of enemy creatures on the whole being larger than the IE games, area size in general being smaller and using larger creatures in areas with limited navmesh space (such as the spider groups in the Ogre Cave entrance and inside the cave).

 

Actors also don't seem to be making regular checks for 'shortest path' pathfinding checks, they seem to make a single check until a condition is met that interrupts it, which is why we are seeing ring-around-the-rosy instead of an actor changing their path to their target when there is a new 'shortest path'.

 

 

I've also noticed something in the town or any areas populated with a lot of people. Sometimes one of your characters might get stuck running into people.

 

For instance, I went to medreth and noticed I was missing my Priest. I clicked on the map and my priest was near the inn.

 

 

 

 

 

 

Then I went to the inn to see what was wrong and saw this.

 

 

 

 

 

 

Seems the pathfinding couldn't figure out how to get around them.

[morhilane]

Hiro that happens to me all the time. Sometimes it's even stuck on a single person (mostly at the Inn).

[Matt516]

Like I said - I don't think it's a navmesh issue. Static pathfinding with objects that don't move is quite easy, computationally speaking. It's characters, both moving and not, that seem to be mucking up the works.

[Sensuki]

Yeah it's not the navmesh. There are navmesh issues where certain bits of areas don't have pathable terrain where they should and there's a black hole at the Drake Egg where all of your characters can get stuck in the same spot.

 

[Hiro Protagonist II]

The path finding is worse in this update than the previous versions. I wonder what they did to make it worse. And I didn't know about the black hole with the Dragon's Egg. In the IE games, the characters seemed to pass through or pushed your other characters out of the way. They should do the same here. It feels very turn based where your characters have to go around each other.

[Sensuki]

They don't have a collision system I don't think, which is really really really strange. Units *cannot* overlap one another in the Infinity Engine games.

 

Same with the 3D models and clipping into each other.

Edited October 4, 2014 by Sensuki

[Hiro Protagonist II]

I'm wondering if the way they've done it with your characters not being able to push other characters out of the way is due to the combat. When you're in combat, a rogue can't push a fighter out of the way to get where they want, a mage running past your priest can't push the priest out of the way and this carries through to non-combat. Your characters have to 'ring around a rosey' with each other before they get to their places. Maybe it could be changed when you're out of combat, your characters can push others out of the way.

[Captain Shrek]

They don't have a collision system I don't think, 

 

 

This is really bad. But with combat map so larger than the char size does it matter? Positioning need not be that accurate in such a game. 

[Sensuki]

Bloody oath it matters and yes it does.

[Captain Shrek]

Maybe. What I gleaned from the videos you made is that as long as some general positioning rules are followed, the actual tactical stuff is immaterial: tanks in front, DPS/Healer in the back or if the DPS is melee then flanking.

 

Also, I would suspect that having no collision based model would actually SIMPLIFY pathing. It would be unrealistic, yes, but trying to fix that now does not really seem like a serious issue. 

[Caladian]

The way it appears to me is that at first, each model makes a path and only changes it if it collides with something, instead of trying to always optimize the route.  The big issue is this though, chars getting stuck.  To me, it appears to be happening because the computations for the path generation are thinking certain holes between 2 other things is larger than it really is, or the collision isn't registering as it should so that it would make a new route.

 

If they are using a collision to trigger new pathing... boo.  It should be checked several times and based on collisions.  If there is an issue with the calculating, it can be solved by making the calculations as if the model is actually larger than it is.

[archangel979]

They should ask InXile for help, WL2 does not have pathfinding issues outside combat.

[Hiro Protagonist II]

Out of combat, I've noticed the characters in your party will push other party members or NPCs out of the way in WL2. Much like it did in the IE games.

Edited October 8, 2014 by Hiro Protagonist II