# A star pathfinding and discrete/smooth positions

The A* (A-star) algorithm usually represents a path on a grid.

Once a path has been found, however, the path looks blocky and is not suited if you move your units with floating point datatypes.

Here is an image describing the problem. The whites tiles represent the path found by A*. The black line path is the path I want, the red line path is the one I don't. One solution would be to select a corner when the path turns, and switch/keep side when the path turns the other way. Seems like the most logical and cleanest way to do this.

• The common solution is path-smoothing, but often a better (easier/faster) solution is to use an Any-Angle pathfinding algorithm. See here for more details. – BlueRaja - Danny Pflughoeft Aug 9 '14 at 19:24

## 3 Answers

As other option, you could split the path into straight parts. Then you only need to find the points where your original path leave a path part (no need to compute, just switch by direction of the next part). Only what remains it is connect points of your new smooth path! EDIT: if you insist on the path you drawn, just compare the two extreme possibilities in which way path can leave a straight part (=point at one or the other end of the edge), and choose whatever produces shorter line segment (pythagoras theorem).

As for hero width, if you look closely - where is the path closest to edge? In the connection of last "tile" and the one before. Check path distance to the edge in that point(you will have to do math now, switch wont suffice), if it is less then hero width/2, add new point to the path at hero width/2 distance from edge. Sorry of image inconsistency, already deleted source of original image.

• Very nice. Do you have by any chance a simple way to handle the 'hero' size ? i wonder if considering the corridors have width = width - hero's radius (while keeping same corridor center coordinates) wouldn't do the trick. – GameAlchemist Aug 9 '14 at 19:34
• @GameAlchemist: Yes, that's the usual way to handle it. – Ilmari Karonen Aug 9 '14 at 20:17
• Thx for your update. Since it is corridor width = corridor width - hero width, then on each side you should consider only (hero width / 2 ), or even better consider radius = sqrt ( sq(width/2)+sq(height/2)), in case the hero can freely turn. (in your scheme the corridors are too narrow ) ( Rq : I'm assuming here we consider the center of the hero -the only way to avoid nightmares -) – GameAlchemist Aug 9 '14 at 21:30
• @GameAlchemist good point, it should be width/2. Radius is a bit overkill though (just take higher of the two dimensions). – wondra Aug 9 '14 at 21:33
• In fact, about radius, a precision : if one is using axis-aligned Bounding Box collision tests, then the 'radius' should be max(width/2, height/2). For one using Bounding circle collision tests, the formula is the one above (computed once for each object creation). – GameAlchemist Aug 9 '14 at 21:37

One option for path-smoothing is casting rays from the current position to the farthest visible node and go there. You could either do it in real time or just build a new path from the one you already have, so the navigation algorithm stays the same.

Starting from the current position, cast rays to each node in the path. When there is a node that cannot be reached by the ray, the previous node is the one to take into account. Considering the last node, repeat the process until the final node.

In the end, you'll have a result similar to the image below (green path) depending on the ray's width and extra parameters your game requires. Also, there is this Valve's presentation about the AI used in L4D. It's worth taking a look at it and getting ideas from it.

• your green path seems incorrect... you do cast a ray from the unit position, and not from the tile position right? – jokoon Aug 10 '14 at 9:34
• @jokoon It depends on how you apply it. The first ray is cast from the unit position, then from the farthest visible node unless you apply it when the unit is navigating (but then again, it's shot from the location of the farthest visible node). The path is just an example and, as I said, it will depend on the width of your ray and I just avoided the corners while drawing it. – reefaktor Aug 10 '14 at 11:15

The A* Algorithm works with paths on a graph. The graph does not have to be a grid.

If you look at the paths you want, they go through the corners of the square tiles. Specifically, they go through the corners where three tiles are walkable and one tile is a wall. Instead of giving A* a graph with the tile centers, you can build a graph with only these "exterior" corners, with graph edges from corner to corner (if there's line of sight). You may want to move the corners a few pixels away from the corners to handle the “hero size” problem.

If you build this corner-to-corner graph instead of the grid graph, A* will be even faster than post-processing paths or using an any-angle algorithm (Theta*). However, building the graph takes some time (mostly to process line of sight), so it might not be a great choice if the player can change the map while the game is running.