Loftar's thoughts on pathfinding

[loftar]

Since pathfinding comes up every now and then, I guess I'd better write down my current thoughts on the matter.

To begin with, I think that "pathfinding" is a mischaracterization of the problem. The real problem is the stupid clipping on unobvious corners and edges of objects and the total interruption of movement that such clipping entails, so I'll refer to the whole thing as "the clipping problem" rather than as pathfinding. Pathfinding is just one possible solution to the clipping problem, and I'm not convinced that it's the proper one. I think pathfinding is too complex (and arguably unreliable) a phenomenon to incorporate into fundamental movement mechanics. For instance, when you're fleeing from a bear (or a player), you don't want the pathfinding algorithm to cut in and choose an oblique angle away from the bear just because it happens to be the shortest way to get around the wall you simply clicked on the wrong side of. If you doubt this assessment, just consider the countless times you've sworn at RTS games for the stupid decisions of their pathfinding algorithms, and multiply that feeling by the difference in importance between a single Starcraft Marine and your main character.

I'm not entirely sure what a more proper solution to the clipping problem is, but I'm inclined to think that it is rather something akin to what happens in most games, where, if you try to walk into a wall, the wall simply pushes you back out in its normal direction, so that a simple corner doesn't prevent and interrupt movement but rather just slows it down slightly for the fraction of a second that the tangential movement will take to get you around the corner, and where one can also walk at almost full speed in a direction which only minutely crosses into a wall. I'm not sure if there's a common term for the phenomenon, but if there isn't, let's just refer to it as "push-out".

The primary reason I haven't already implemented push-out, then, is because it's not terribly compatible with the internal interfaces I use for object movement. This should of course be addressed, and perhaps I haven't made that enough of a priority (I agree that clipping is an important problem), but for now that's how it is. Perhaps it's not even that difficult once I get cracking on it.

So you might say, then, that even if pathfinding isn't the proper solution, it is at least far better than nothing until I get to implement push-out, but pathfinding movement is incompatible with the current interfaces in exactly the same way as push-out is, so that doesn't really help.

So that's how things currently lie with regards to the clipping problem. Just FYI, I guess.

[shubla]

One solution would be to give little assist to custom client makers (Way to get all hitboxes) and hope that those who know how to make pathfinders make them on their (public) clients so people can choose if they want to use them or wait for your solution.

[Granger]

stuff

Thanks for the update on this, I hope you find a solution quickly because it heavily eats on my will to play - and I fear i'm not alone with this.

[Tamalak]

I feel like the fix for this is to allow us to walk through stuff, like:

-toads
-bushes (maybe slow the player to crawl speed when he's in a bush)
-logs/stumps

[Kaios]

I feel like the fix for this is to allow us to walk through stuff, like:

-toads
-bushes (maybe slow the player to crawl speed when he's in a bush)
-logs/stumps

might be an option, I remember one of them (possibly jorb) mentioning that maybe animals should jump over cliffs when chasing and I got the impression this was something that is feasible. I imagine a similar mechanic could be done for hearthlings and logs, stumps, other short objects as a hop or step over animation, sped up in comparison to cliff climbing also.

Then they can get to implementing "tripping" injuries

[ArvinJA]

"tripping" injuries

Should also be able to incur those from the magic mushrooms jorb was talking about in his stream

[warrri]

Since pathfinding comes up every now and then, I guess I'd better write down my current thoughts on the matter.

To begin with, I think that "pathfinding" is a mischaracterization of the problem. The real problem is the stupid clipping on unobvious corners and edges of objects and the total interruption of movement that such clipping entails, so I'll refer to the whole thing as "the clipping problem" rather than as pathfinding. Pathfinding is just one possible solution to the clipping problem, and I'm not convinced that it's the proper one. I think pathfinding is too complex (and arguably unreliable) a phenomenon to incorporate into fundamental movement mechanics. For instance, when you're fleeing from a bear (or a player), you don't want the pathfinding algorithm to cut in and choose on oblique angle away from the bear just because it happens to be the shortest way to get around the wall you simply clicked on the wrong side of. If you doubt this assessment, just consider the countless times you've sworn at RTS games for the stupid decisions of their pathfinding algorithms, and multiply that feeling by the difference in importance between a single Starcraft Marine and your main character.

I'm not entirely sure what a more proper solution to the clipping problem is, but I'm inclined to think that it is rather something akin to what happens in most games, where, if you try to walk into a wall, the wall simply pushes you back out in its normal direction, so that a simple corner doesn't prevent and interrupt movement but rather just slows it down slightly for the fraction of a second that the tangential movement will take to get you around the corner, and where one can also walk at almost full speed in a direction which only minutely crosses into a wall. I'm not sure if there's a common term for the phenomenon, but if there isn't, let's just refer to it as "push-out".

The primary reason I haven't already implemented push-out, then, is because it's not terribly compatible with the internal interfaces I use for object movement. This should of course be addressed, and perhaps I haven't made that enough of a priority (I agree that clipping is an important problem), but for now that's how it is. Perhaps it's not even that difficult once I get cracking on it.

So you might say, then, that even if pathfinding isn't the proper solution, it is at least far better than nothing until I get to implement push-out, but pathfinding movement is incompatible with the current interfaces in exactly the same way as push-out is, so that doesn't really help.

So that's how things currently lie with regards to the clipping problem. Just FYI, I guess.

What about the simple stuff. I posted the gif in the other thread. It's not really pathfinding but it works when you plant trellis crops.

The character doesnt try to move directly to the trellis, it moves in front of it. Just take that and copy that for other objects. I realize that it might have some implications for existing objects that are lined up where it would be impossible to reach them like these drying racks but it's a ncessary evil i'd like to accept. The layout on those drying racks breaks the immersion anyway because i cant figure out how my character can squeeze through that and put hides on that

Also, as others have posted, at least reduce the strain on us and make bushes, chicken, toads, rats pathable.

[ArvinJA]

Anyway, a first step, that is very compatible with how objects work right now, would be to provide good neg layers, like in legacy, where the coords for the bounding boxes were encoded into the neg layer of the res files and properly decoded by the client. Right now, client-makers are forced to do tests themselves (APX, hitbox testing), make up bounding boxes that are good enough (romovs, hide trees option), or figure out from the model (k-t). All of those methods are much worse than having the bounding boxes decoded properly by the client.

[Sever]

I seem to remember complaining to a friend about stopping dead when running into something. Wished you would just keep going along the obstacle. I forgot about it, but you hit the nail on the head. That's the problem.

Regarding "push-out", you have the corners of the hitbox, so you calculate the vector of the side of the object you collided with and use that in place of your old velocity. There is some way to maintain the same general direction with some simple math I would need to figure out on paper. The problem will be that corners along that vector still stop you and aren't so easy to calculate around. I have no idea if you can find a "next" object along a path, but if you can, it should be straightforward, possibly a little complex or too glitchy, though this could all be too heavy on the CPU for all I know. Then there's knowing when to stop... good luck with that.

Also, I am 100% talking out my ass because I only see the math, not the practical application of pathing.

[MagicManICT]

There is some way to maintain the same general direction with some simple math I would need to figure out on paper.

It's actually all pretty well all figured out. There's quite a few 3D programming books with the calculations, though you do need to have a grasp of the math to be able to program it without significant bugs. Otherwise, you pretty much described the algorithms used to move two potentially intersecting objects if one is trying to "push through" the other.

I've always seen it called "sliding" the objects, but language varies in different regions.

The big problem with the current design, I think, and the way people cram stuff together off-grid is that with any sliding algorithm, you end up potentially still stuck in a corner with no way to get around it. In a typical WASD movement game, the person can usually just sidestep left or right to get off the concave corner (convex corners/curves won't, or shouldn't, ever be an issue). In point-and-click (Haven), there does need to be some smart way for the user to get out of that sort of corner without moving the mouse back behind or to the appropriate side of the avatar model for a quick side step. On the other hand, if it's at a wall or cliff where the corner is more than an integral or two (say half a tile or more), yes, they should have to manually move out of the corner.

3D engine design is a complex beast. It's why we've come down to about 4 major engines (Unreal, Source, CryTek, Unity, maybe missing one or two) and a half dozen or so minor ones.

edit: apologies for bad terminology in a few spots. It's been too many years since I've really studied geometry, and my mind was drawing blanks on proper terms.