Less aggressive path smoothing

[EskelCz]

I'm trying to implement free mouse movement on top of grid based terrain, with A* search. Everything is working fine, except the smoothenPath method is smoothing a little too much (most of the times just one tile beyond corners) and not allowing for collision-free passing.

I don't understand the algorithm yet but it seems like a fairly generous 'line of sight' approach which passes even if just a part of the tile is visible. This results in the moving agent slightly cutting through obstacles. Simply it doesn't account for any size of the agent itself.

Is there any simple fix to this problem? (on the side of the algorithm if possible)
Great library by the way, thank you very much.

[EskelCz]

To clarify, the problem is not removing too many intermediate points, but frequently leaving the ones behind the turn/obstacle, not in middle of it. Unfortunately it doesn't seem consistent, sometimes it does pick the right one.

Below are two pictures of the problem. Green fields are walkable, red are unwalkable (walls). Small blue dots are A* path, large dots are the smoothed result. Red dot marks destination.

[imor]

I am aware of this problem with smoothenPath but unfortunately haven't been able to find time to think about how to fix this. If you (or anyone else) are able to come up with a solution, please do not hesitate to open a pull request.

[myc0210]

@EskelCz if you take a look at source

if (!grid.isWalkableAt(testCoord[0], testCoord[1])) {
                blocked = true;
                break;
            }

this test whether next valid path point is walkable.From your example you can see that the case when your character walks cross obstacle is a special case which it exactly fall into a edge point of the path grid when doing isWalkableAt test. Then i think you may look at isWalkableAt to see how to fix it or walk around it.

[myc0210]

@EskelCz Sorry. I seems mislead you. Actually the problem is the algorithm inside interpolate function. the nodes it generate for the line test. Your path for example is now [[0,0],[0,-1],[0,-2],[1,-3]] then the algorithm will keep find the possible longest nodes which now is [1,-3]. then go by interpolate function the line nodes it generated are [0,0],[0,-1],[1,-2],[1,-3] that all are walkable... Then your problem appears because from [0,-1] to [1,-2] characters will cross that obstacle field which is [1,-1]. Now my suggestion is that you can substitute the interpolate function based on the Bresenham's algorithm to the other complex one or customized one to suit your case. http://playtechs.blogspot.sg/2007/03/raytracing-on-grid.html take a look at this!. using this ray tracing algorithm to verify the nodes. In your case if there are any nodes belong to obstacle in the ray tracing function between two test point ex: [0,0],[1-3], then we decide not to take this node into account for path smoothing.

[EskelCz]

@myc0210 The algorithm you link to is actually exactly the same as the 'Interpolate' function you mentioned. (I've implemented it only to find out it's the same thing)

Also I've found a nice article explaining the difference between bresenham and raycasting. http://www.saltgames.com/2014/line-of-sight/
I'll look into the raycasting method. Unfortunately I'm not a programmer and I get easily intimidated by any kind of math / complex algorithms. :(

[myc0210]

@EskelCz the difference is that bresenham is try to implement a efficient way to find nodes to represent lines but may skip some based on his algorithm because the x and y value are integer. but the raycasting line is to include all the nodes the line passes. because bresenham is try to find a simple easy way to handle intepration between two point so it does a trick and introduces a acceptable error into his implementation.

[myc0210]

@EskelCz if you see from https://github.com/libgdx/gdx-ai/wiki/Path-Smoothing the optimal smoothing path actually is what you encounter now. It also crosses the obstacle when the character has body size.