Loftar's thoughts on pathfinding

[MagicManICT]

In the world of 3D design, you have a few options for bounding boxes, but the come down to two efffective choices*: rectangles (not sure what a 3D right-angled quadrilateral is called... cubics?) and spheres and variations of them (ovaloids, etc.) Circles and spheres are actually the simplest bounding object since all you need is a point and distance, and you only have to make a single calculation to determine if they will intersect. It's been a while and I forget off the top of my head the algorithm you need to walk through to determine if two rectangular objects intersect.

I'm not saying the engine should be converted to use circular bounding boxes, as some of the same issues occur when objects are near each other (such as an object moving at an angle into two circles can still get stuck between two bounding boxes with no slide left or right possible), but if the circles are more or less linear, there are no sharp corners sticking out for the mobile object to collide into and not slide around.

*other choices are combinations of the two, mostly rounded objects of some manner as long as they are easier to define and calculate than a polygon mesh. I'll also note that 2D engines are basically the same in design, just simpler math. Even if the world is effectively two dimensional, the same core concepts apply.

[Karede]

Push out is probably better than my position on pathfinding complaints which is sux2suck

[romovs]

... The real problem is the stupid clipping on unobvious corners and edges of objects and the total interruption of movement that such clipping entails...

How's object collision implemented currently btw?

Bounding boxes appear to have bottom and right side shorter (or just displaced) by one unit at 0 degrees.
So it leads to very strange behaviour when you can walk by an object from one side but cannot from the opposite.


What's up with that

[Granger]

Bump.

[apoc254]

This is seriously over thought. Just give use pathfinding that will only calculate for short obstacle distances. Let it figure out how to get around a tree, but not something as wide as a timber house. That way its up to the user to choose a direction and we are not stuck on every single tree.

Don't go through every item and redefine all the hit boxes as circles or spheres(time suck).

[APXEOLOG]

Make the character's hitbox a circle instead of square. This should solve a lot of angle-based problems.

[Granger]

Make the character's hitbox a circle instead of square.

Are there already any circle hitboxes? If not then the logic in the intersection check might get more expensive...

[lachlaan]

What would circle hitboxes do? It'd make some stuff more bearable, but it would instead still cause the same issues once you do clip something. The solution is something i think loftar suggested in the original post. Too lazy to read it but ideally your character would slow down when bumping, be displaced a bit then continue on its path. That way derpy navigation still gets penalized for combat situations, and combined with your suggestion, might make the walking game playable. But hitboxes alone can't do much without redefining how they interact.

[Ysh]

What would circle hitboxes do? It'd make some stuff more bearable, but it would instead still cause the same issues once you do clip something. The solution is something i think loftar suggested in the original post. Too lazy to read it but ideally your character would slow down when bumping, be displaced a bit then continue on its path. That way derpy navigation still gets penalized for combat situations, and combined with your suggestion, might make the walking game playable. But hitboxes alone can't do much without redefining how they interact.

Right now the player box is a square. Say this square is 10 unit for all side. If I go straight with perfection, I can squeeze in a hole 10 unit wide. If I am at any angle at all, I cannot fit because the distance of box corner to corner is longer than his side. If this is instead a circle, rotation is not mattering.

Assuming adding a circle hitbox is easy, it can be a useful temporary fix. But I do not think it can substitute for a proper solution.

[shadyg0d]

Forgive me if somebody already suggested this or if this is somehow retarded:

Maybe it could walk parallel to the the edge it encounters for up to a set distance(such as one tile). If the obstacle is cleared within the set distance it would continue on the path. If not it would simply stop (to prevent path-finding around massive objects). It could use either the direction that immediately brings it closer to the destination, or calculate which direction clears the obstacle faster. This could be triggered the moment you are blocked by something rather than trying to "predict" the path. It would simply change the direction the character is facing and walk alongside the obstacle. I think this is a better solution than "pushing" because pushing would either require a decently-distanced push, or multiple pushes. It could avoid multiple obstacles in one path, as long as it moves toward the destination between every obstruction. Or let's say you encounter a corner(rather than an edge), it changes direction by 90 degrees for 1 tile, then attempts to move towards the destination again. If successful it would either have fully cleared the object already, or gotten blocked this time by the edge of the object, in which case it would walk parallel to since it successfully moved in the direction of the path for that minuscule distance. If multiple objects are placed in such a way that causes infinite walking in an undesirable diagonal direction, a limit or radius could be placed on the x-distance it is allowed to traverse away from the original path.