Jump to content

Fixing Path Finding


tdphys

Recommended Posts

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 by tdphys
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 by Sensuki
  • Like 1
Link to comment
Share on other sites

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 by tdphys
Link to comment
Share on other sites

 

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.

Azarhal, Chanter and Keeper of Truth of the Obsidian Order of Eternity.


Link to comment
Share on other sites

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.

 

 

 

ayBqKKj.jpg

 

 

 

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

 

 

 

4CbI6He.jpg

 

 

 

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

 

Link to comment
Share on other sites

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.

  • Like 1
Link to comment
Share on other sites

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 by Sensuki
Link to comment
Share on other sites

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.

  • Like 1
Link to comment
Share on other sites

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. 

"The essence of balance is detachment. To embrace a cause, to grow fond or spiteful, is to lose one's balance, after which, no action can be trusted. Our burden is not for the dependent of spirit."

Link to comment
Share on other sites

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. 

"The essence of balance is detachment. To embrace a cause, to grow fond or spiteful, is to lose one's balance, after which, no action can be trusted. Our burden is not for the dependent of spirit."

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

×
×
  • Create New...