PyPlayGround

Movement Control

Battles

Other

Pathfinding

Pathfinding is the task of finding the best (usually shortest) path between two points. This is hardly a trivial task, as between those two points may lie many obstacles. The two points are usually described as origin and destination to describe the expected direction of movement, but these roles may be disregarded by the pathfinder.

Pathfinding algorithms are usually designed to run over a grid of squares, with each square being either passable or not. Some algorithms also allow to specify how hard it is to pass a certain square. A longer path may be taken if it is much easier to pass.
PyPlayground, on the other hand, runs its algorithms in a theoretically infinitely-precise space. While an algorithm may choose to arbitrarily partition space into a grid, it is not necessary.

Good pages about pathfinding:

Amit's Thoughts on Path-Finding and A-Star - This is one of the oldest pages about pathfinding (although it has changed over time)
Game AI Resources: Pathfinding - A good collection of links
Smart Moves: Intelligent Pathfinding [www.gamasutra.com] (requires free registration) - Great overview. Check out the excellent demo!!

Pathfinders implemented for PyPlayground

Thanks to of the clean design of PyPlayground, code from implementations can easily be extracted into other projects.

Grid Pathfinders

"Smooth" Pathfinders

Gravity Pathfinder

Grid Pathfinders

Simple Pathfinder

Simple Pathfinder truely is simple. It's simple and dumb, and I placed it here mainly as an easy sample to get you familiar with the framework.

The concept is obvious - move towards the target as long as there is no obstacle. If there is one - tough.

Here is the implementation:


class SimplePathfinder(Player):
    def step(self, pg_state):
        robot = self.get_robot()
        x,y = robot.get_pos()
        dst = robot.get_task()

        diff_x = sgn( dst[0] - x )    # sgn(x) -> 0 if x==0 else 1 if x>0 else -1
        diff_y = sgn( dst[1] - y )

        robot.move(x+diff_x, y+diff_y)

Quite simple.
A quick explanation about PyPlayground's design: Each algorithm is a class inheriting from Player. It may implement init and step. init is called when the round starts, and step is then called for every new step (think of it as turns). Here we only needed step. To each step, the current state is provided. The state lets you know where are the obstacles, where are the other players and etc.

A quick explanation about the implementation: First we set things up, then we measure the direction we should move in (sgn is the same as normalizing in 1-D), and then we just move in that direction. We don't test for obstacles because if we hit one, we lose anyway: PyPlayground takes care of disqualifying bad players by itself.

Simple Pathfinder gets lucky. Visualization by PyPlayground

Wall-Tracer

Wall-Tracer is fairly simple as well: It approaches the target directly, and if it encounters an obstacle on the way, it traces around it until it is free again to move directly at the target. Repeat.

The implemenation is a bit odd, so I will explain it. First we define a direction to move in, just like in the simple pathfinder. If we can move in that direction, then hooray. If not, we will try to rotate the direction of movement by 45 degrees and try again. We repeat this process 8 times (until we exhaust all possible directions). This creates the effect of having your robot (your avatar) trace around the obstacles. It does so impressively well, and the only problem is getting stuck in a loop of tracing the same wall all over again. In order to avoid getting stuck in such loops, I also added a record of nodes that's been visited, and made sure never to step on the same node twice. This may cause other bugs, but they are more rare and fixing them would clutter the implmentation (but feel free to try it yourself).

The actual implementation is very elegant, and I'm quite proud of it:


class WallTracerPathfinder(Player):
    def init(self):
        self.visited = set()
    def is_visited(self, x,y):
        return (x,y) in self.visited
    def visit(self, x,y):
        self.visited.add((x,y))

    def rotate_direction(self, dir):
        """Rotates direction clock-wise by 45 degrees."""
        # Directions are numbered as:
        #  7 0 1
        #  6   2
        #  5 4 3
        dirs = [ (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1, 0), (-1,1) ]
        return dirs[ (dirs.index(dir)+1) % len(dirs) ]

    def step(self, pg_state):
        robot = self.get_robot()
        x,y = robot.get_pos()
        dst = robot.get_task()

        diff_x = sgn( dst[0] - x )    # sgn(x) -> 0 if x==0 else 1 if x>0 else -1
        diff_y = sgn( dst[1] - y )

        # Try out all directions, starting with the correct one.
        for i in range(8):
            new_x, new_y = x+diff_x, y+diff_y
            if not self.is_visited(new_x, new_y) \
               and pg_state.map.is_passable(new_x, new_y):
                robot.move(new_x, new_y)
                self.visit(new_x, new_y)
                return
            diff_x, diff_y = self.rotate_direction((diff_x, diff_y))

        raise actor.Surrender()

Hopefully this code is self-explanatory.
Note that actor is a module which has to be imported.

Wall-Tracer demonstrates remarkable pathfinding skills. Visualization by PyPlayground

Wall-Tracer finds his way out of a sticky situation, by remembering where he visited.

A* (A-Star)

A* (pronounced: A-Star) is the most popular pathfinding algorithm to-date. Providing a good balance between accuracy (finding the best path) and speed, A* is applicable (and applied) in almost any pathfinding field, be it games, robotics, routing, etc.

For more reading about A*, check out:

A* Pathfinding for Beginners - An excellent tutorial, with simple explanations and graphical demonstrations.
Also check-out the links at the top of the page.

I implemented everything from scratch, trying to use meaningful names (unlike those horribly vague f,g,h symbols) and keeping a logical structure (somewhat influenced by AIMA's excellent implementation, which is more elegant but much less readable than mine, IMHO :-)

Since the entire code is too large to fit in here, the implementation of A* itself can be found here.
I will include here only the Player class that uses it, and therefor a quick explanation is in order:
The AStar class constructor accepts node_map, starting_node and target_node. node_map must be an object that implements a certain interface (a collection of methods), and these are the methods that you will see appended to the Player class.

One last note about the implementation - unlike popular implementations who solve A* in a while-loop, mine is solved by repeated steps. This approach allows for better embedding in code (as a callback, in state-machines, etc.), as most applications wouldn't like to freeze while A* calculates. However, this can be done by simple refactorings in most cases.

And here is the code:


from astar import AStar

class AStarPathfinder(Player):
    def init(self):
        robot = self.get_robot()

        # Create an AStar instance. We will function as the node-map.
        self.node_map = {}
        self.astar = AStar( self, robot.get_pos(), robot.get_task() )

        self.map = None # Will be set on step
        self.path = None    # Will be set once the path is found

    def step(self, pg_state):
        robot = self.get_robot()

        if self.path is None: # A* still not finished
            self.map = pg_state.map # Update for node-map methods
            res = self.astar.step()
            if res is not None:
                self.path = res # Path found. Next step start moving
        elif len(self.path):  # A* found the path. Now let's move
            # A-Star returns the path reversed, so we pop from the end
            self.get_robot().move(*self.path.pop())


    # Implementing node-map
    def neighbors(self, node):
        "Returns all valid (passable) nodes neighboring (adjacent to) given node"
        dirs = [ (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1, 0), (-1,1) ]
        for x,y in dirs:
            new_x, new_y = node[0]+x,node[1]+y
            if self.map.is_passable(new_x, new_y):
                yield new_x, new_y

    def set_node(self, node, parent, cost):
        "Update node data"
        self.node_map[node] = parent, cost
        # This will make the GUI show which nodes we've been checking out
        self.get_robot().mark(shapes.Rect(node, (node[0]+1, node[1]+1) ))

    def movement_cost(self, from_node, to_node):
        """Returns the cost of moving from node A to node B
           (1 for straight, 1.4 for diagonal)
        """
        assert self.map.is_passable(*from_node) and self.map.is_passable(*to_node)
        x = abs(from_node[0]-to_node[0])
        y = abs(from_node[1]-to_node[1])
        return (None, 1, 1.4)[x+y]


    def get_priority(self, node):
        "Return priority for node ( g(n) + h(n) )"
        return self.arrival_cost(node) + self.cost_to_target(node)

    def arrival_cost(self, node):
        "The cost it took to reach node for starting point ( g(n) )"
        try:
            return self.node_map[node][1]
        except KeyError:
            return AStar.INFINITE_COST

    def parent(self, node):
        "Return the last set (also best one found) parent to node"
        return self.node_map[node][0]

    def cost_to_target(self, node):
        """Returns an estimated (heuristic) cost to
           reach target from node ( h(n) = (dx**2 + dy**2)**0.5 )
        """
        target = self.get_robot().get_task()
        diff_x,diff_y = target[0]-node[0], target[1]-node[1]
        return math.sqrt(diff_x*diff_x + diff_y*diff_y)

(astar.py can be found here)

A* easily finds the best path. Visualization by PyPlayground

This A* is too well-balanced for a game. Let's try to tweak it

Here we gave more weight to g(n), and A* behaved too much like a Breadth-First Search

Here we gave most weight (90%) to h(n), and it found a path very quickly, but it obviously isn't the best one.

Nothing like a healthily-balanced A*.

Smooth Pathfinders

Gravity Pathfinder

Admittedly, Gravity Pathfinder is not really a pathfinder. It is a naive implementation of movement control, being run in the hope that a correct path will result. Surprisingly, most situations I've tested lead to a correct path, although not the shortest. It has many shortcomings, and is wrong many times. However, its simplicity is beautiful (imho).

Gravity Pathfinder works by a simple concept - the "finder" is attracted towards its target, and is rejected away from its obstacles.

Visualisation by PyPlayground (and a little paintbrush editing :-) :

Green point is the destination
Yellow arrows demonstrate rejection from nearby obstacles
Green arrow demonstrates attraction to destination
Blue line is the path taken so far
Notice how the path curves around the right obstacle. This is the rejection at work.
The balance between rejection and attraction is not very clear, and is best found by trying different values. At this point, PyPlayground comes to high use, as you just change a parameter and run your finder again to watch how it affects its behaviour.

The current formula I use, which seems to produce the best results is:
rejection = (a/b)(b-x)
Where:

a = max rejection -- This will be the rejection at zero distance
b = (max range of effect) ** GRAPH_TILT -- Rejection will be 0 if distance is exactly at max range
x = (distance from closest point in circle) ** GRAPH_TILT -- This is actually distance from center minus the radius

Current values I use are:

max rejection = 100.0
GRAPH_TILT = 0.1

Current implementation of Gravity Pathfinder (using PyPlayground) is:




class GravityPathfinder(Player):
    MAX_REJECTION = 100.0
    GRAPH_TILT = 0.1
    TARGET_ATTRACTION_MULTIPLIER = 10.0

    def init(self):
        self.map = self.get_map()
        self.dst = tuple(self.get_task())

    def step(self):
        # Rejection is a/b(b-x), where:
        # a = max rejection
        # b = (max range of effect)**GRAPH_TILT
        # x = (distance from closest point in circle)**GRAPH_TILT
        self.clear_marks()

        pos = self.get_pos()

        attraction=Vector(*self.dst)-Vector(*pos)
        attraction.normalize()
        attraction.mul(self.TARGET_ATTRACTION_MULTIPLIER)

        rejections = []
        for obj in self.map.objects:
            ox,oy,r = obj.bounding_circle()

            max_dist = r*2
            dist = distance(pos, (ox,oy)) - r
            if dist < 0:    # Usually this isn't allowed
                obj_rejection_strength = self.MAX_REJECTION
            elif dist > max_dist:
                continue
            else:
                a = self.MAX_REJECTION
                b = max_dist ** self.GRAPH_TILT
                x = dist ** self.GRAPH_TILT

                obj_rejection_strength = (a*(b-x))/b

            self.mark(shapes.Line(pos, (ox,oy)))

            obj_rejection = Vector(pos[0]-ox, pos[1]-oy)
            obj_rejection.normalize()
            obj_rejection.mul(obj_rejection_strength)

            rejections.append(obj_rejection)

        if rejections:
            rejection = (sum(rejections, Vector(0,0))) / len(rejections)
        else:
            rejection = Vector(0,0)

        movement = attraction + rejection

        movement.normalize()
        movement *= 0.99999999  # This is hack which will be fixed soon

        self.move(*(movement+pos))

Gravity Pathfinder at work. Visualization by PyPlayground

Another nice job done by gravity.

Yet another nice job done by gravity.

Yet yet another nice job done by gravity.

Back to index