Advertisement

How to smooth path created using a* patfinding

Started by July 27, 2019 09:17 AM
3 comments, last by ManFromTheMoon 5 years, 4 months ago

I have a 2d tilemap and I used to A* patfinding algorithm to generate a path of nodes from a starting point A to a starting point F, now, on this path I want to move a tank, the problem is that this path is not smooth.

 

This is what I want to achieve: https://ibb.co/gRHS2nk

 

The thing is that I have no idea how to do it...

For a vehicle like a tank, an easier solution might be to have the tank stop at each node and rotate in place before continuing. This would increase the total path traversal time a bit, but would be easy (or easier) to implement and wouldn't require deviating from the path at all.

As for your image, what might be helpful is a similar example, but superimposed on a grid, so we can get a sense of the magnitude of the turning radius with respect to the grid cell size.

In any case, obviously a turn like in your second drawing also introduces the possibility of running into obstacles that the path itself misses. So it may not be as simple as just adding turns to the path - essentially, a path with turns is a 'different path' that itself might not actually be navigable.

Another possible issue is that (possibly at least) a strictly grid-based path could result in 'stair-step-y' paths that a rational agent wouldn't take. Adding turns won't help much with that problem. There are however path smoothing algorithms (e.g. 'string pulling') that can address this issue. That's separate from the turning problem though; even with a smoothed path, you might still want to add smooth turns at the nodes, which again could introduce the possibility of running into things the path itself misses.

Having said all that, again, a drawing with a grid might help so we can see more specifically what you have in mind with respect to the turns.

Advertisement

You can solve that in A* if you can express "smooth" as a path expansion limitation.

A* works by extending path by one position within the limits of your entity that moves.

Normally, the only limits of the entity are not crossing obstacles on the map. If your entity has no limitations in movement (the usual case), you can simplify A* by only looking at the map to extend paths. However, you can add more limitations to the movement of your entity, reducing the number of path extensions that can be made each step, without a problem.

If you define "smooth" as driving at least 3 steps in a single direction, and turning at most 45 degrees after 3 or more steps, you not only need a position of the entity, but also the current direction and how many steps to take before it can turn again. A "position" is thus not just position p, but also direction d (0..7), and number of remaining steps s (3..0) before you can turn again.

A "position" in A* thus becomes a triplet (p, d, s). It becomes possible that several entities in the open or closed list are at the same p, but with different d or s (different directions of movement or different number of remaining steps).
This is the disadvantage of the approach, the number of points in an open or closed list becomes larger (here, theoretically, maximum by a factor 3*7 = 21).

Path expansion in the usual form within A* is a function that takes a position p, and constructs a list successor points. In the above case it takes a triplet (p, d, s) and produces a list new triplets (p', d', s').

In code:


DELTA_XY = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

# Usual expansion, ignoring obstacles on the map.
def expand(pos):
    x, y = pos # 'pos' is a x,y pair
    newposlist = []
    for dx, dy in DELTA_DXY:
        newposlist.append( (x+dx, y+dy) )
    return newposlist

# Limited expansion, ignoring obstacles on the map.
def expand(pos, dir, steps):
    x, y = pos
    if steps > 0: # Can't turn, continue moving in direction 'dir'
        dx, dy = DELTA_XY[dir]
        return [ ((x+dx, y+dy), dir, steps - 1) ]
    else: # Can turn 45 degrees
        newposlist = []
        for dd in [7, 0, 1]:
            newdir = (dir + dd) % 8  # Turn, but limit to 0..7 again
            dx, dy = DELTA_XY[newdir]
            if dd == 0:
                newsteps = 0
            else:
                newsteps = 3
            newposlist.append( ((x+dx, y+dy), newdir, newsteps) )
        return newposlist

 

Thanks guys, but I found my solution, after I generate the nodes ( points ) using the A* pathfinding algorithm, then I go on using the Catmull splines to smooth the path and they are also easier for making an object follow the generated path.

This topic is closed to new replies.

Advertisement