10
\$\begingroup\$

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.

here is the picture

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – BlueRaja - Danny Pflughoeft
    Commented Aug 9, 2014 at 19:24

3 Answers 3

Reset to default
4
\$\begingroup\$

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!

enter image description here

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.

enter image description here

Sorry of image inconsistency, already deleted source of original image.

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – GameAlchemist
    Commented Aug 9, 2014 at 19:34
  • \$\begingroup\$ @GameAlchemist: Yes, that's the usual way to handle it. \$\endgroup\$
    – Ilmari Karonen
    Commented Aug 9, 2014 at 20:17
  • \$\begingroup\$ 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 -) \$\endgroup\$
    – GameAlchemist
    Commented Aug 9, 2014 at 21:30
  • \$\begingroup\$ @GameAlchemist good point, it should be width/2. Radius is a bit overkill though (just take higher of the two dimensions). \$\endgroup\$
    – wondra
    Commented Aug 9, 2014 at 21:33
  • \$\begingroup\$ 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). \$\endgroup\$
    – GameAlchemist
    Commented Aug 9, 2014 at 21:37
4
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
2
  • \$\begingroup\$ your green path seems incorrect... you do cast a ray from the unit position, and not from the tile position right? \$\endgroup\$
    – jokoon
    Commented Aug 10, 2014 at 9:34
  • \$\begingroup\$ @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. \$\endgroup\$
    – jorge_codes
    Commented Aug 10, 2014 at 11:15
2
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .