Hey guys having a little bit of trouble figuring out how to refine an astar path.
I’m using a built-in astar algorithm which is working perfectly for obstacle avoiding and finding a path from start to finish. What I need to do though is check where my path has changed direction as I want a different ‘cost’ for these movements.
I’m having a little trouble trying to figure out how to do it myself as I’m fairly new at working with pathfiding. What I want to achieve is something like B as opposed to C since I’m working of a visible grid.
Well, Astar works on a graph basis. So any path it calculates is based on some predefined graph. This graph can be, as in your case, a grid. So the algorithm is only allowed to move on that grid. So only on connections between two nodes on that grid. Astar always picks the shortest path on that grid. In your case path A and path B are exactly the same length. So there’s no reason why B should be better than A.
You could include a penalty for changing direction. I did something like that in my turtle Astar pathfinding routine for computercraf (minecraft mod). Since the rotation into a new direction takes time i wanted to minimize the rotations if possible. So the “cost” of a node would depend on the angle between the direction you entered the current node and the direction to the next node. You could also try to priorize diagonal moves by giving horizontal / vertical moves a small penalty.
Be careful when choosing a penalty. Too large values can lead to unoptimal path results or to a longer runtime as more nodes has to be checked.
All this can only bring you from A to B but never to C. C is something that can’t be determined by the pure graph data as it would require connections between nodes on the grid which are far apart.
So in the end you might have to rely on some manual raycasting / capsulecasting to check if the way is clear. To refine your path you can simply iterate your path points with two index pointers. I1 would start at “0” and I2 at “2”. Then you do the following:
check if there is a clear sight between point I1 and I2
If it is increase I2 and repeat step (1.) until there isn’t a clear path or you reached the last point on the path
Now we either are done (we reached the end) or I2 can’t be reached from I1. So We simply decrement I2 one time so we’re back to a valid path. Now we remove all nodes between I1 and I2 so we get a straight line between I1 and I2.
Now we increment I1 one time so it now points to the old I2 node which is now the next one. You set I2 to be I1 + 2 and continue at step (1.) until you reach the end.
Note: Your path should be stored in a List so you can easily remove points.
