A* algorithm visualizer written in pygame.

Graphical A* simulation.

Last week we mentioned the change to make biters not collide with each other,
but that wasn’t the only biter-related update we released this past
week. Somewhat coincidentally, this week’s updates have included something I’d
been working on for a few weeks before – an upgrade to the enemy pathfinding
system.

Pathfinding

When a unit wants to go somewhere, it first needs to figure out how to get
there. That could be as simple as going straight to its goal, but there can be
obstacles – such as cliffs, trees, spawners, player entities – in the way. To
do that, it will tell the pathfinder its current position and the goal
position, and the pathfinder will – possibly after many ticks – reply with a
path, which is simply a series of...

This book presents a unified treatment of many different kinds of planning algorithms. The subject lies at the crossroads between robotics, control theory, artificial intelligence, algorithms, and computer graphics. The particular subjects covered include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning.

The tangent bug algorithm is actually the imroved version of Bug1 and Bug2 algorithms. Unlike these methods, tangent bug algorithm depends on the existence of a range sensor that is mounted on the point robot in the map. By only investigating the output ot this range sensor, and including the knowledge of the robot's current pose and goal's pose, the robot plans actions to reach to the goal.

This web page consists of information about the tangent bug algorithm and its implementation.

18/April/2007

In this report we discuss our implementation of a local path planning algorithm based on virtual potential field described in [1]. The algorithm uses virtual forces to avoid being trapped in a local minimum. Simulation and experiments are performed, and compared to the results presented in the paper. They show good performance and ability to avoid the local minimum problem in most of the cases.