I would like to write a "game", where you can place an obstacle (red), and then the black dot tries to avoid it, and get to the green target.
I'm using a very easy way to avoid it, if the black dot is close to the red, it changes its direction, and moves for a while, then it moves forward to the green point.
"Unrealistic" path

How could I create a "smooth" path for the computer controlled "player"?
Edit: Not the smoothness is the main point, but to avoid the red blocking "wall" and not to crash into it and then avoid it.

How could I implement some path finding algorithm if I just have basically 3 points?
(And what would it make the things much more complicated, if you could place multiple obstacles?)
Smooth path


3 Answers 3


A very common and general approach is to divide your world space into grids and use algorithms like A*.

This link helped me get started with understanding and implementing the A* algorithm.

A simpler thought that comes to my mind is once you have the world into grid-cells. Always, have the black dot follow Manhattan distance to the green dot. Then, you can assign weights to each cell. Obstacles can have a high weight on the grid-cell and free-to-move can have (let's say) 0 weight. As you move along the Manhattan distance, for each move, check to see if the weight of the next cell is not higher than the weight of the current cell. If it is higher, check the adjacent cell's weight and then move on.

Hope this helps

  • \$\begingroup\$ This A* algorithm article seems to be what I was looking for, but unfortunately what I still don't know is how to divide my "world" into grids :S \$\endgroup\$
    – user
    Commented Feb 23, 2011 at 17:38
  • \$\begingroup\$ It really depends. Thought: divide your world into a grid of 32 x 32 which would then represent positions in a 2D array. For example, in your case: red dot is at 120, 120 pixels (or 120/32 x 120/32 : 3.75 x 3.75) 3.75 x 3.75 represents a position on your world-grid (or 2D array). Since arrays are indexed by integers, you only want integer part of it. Thus, the red dot would be at 3 x 3. Hope this helps \$\endgroup\$ Commented Feb 23, 2011 at 17:50

Steering behaviors are designed for pretty much this exact problem set.


Basically you would combine the obstacle avoidance behavior with probably the seek or pursue behavior. That page has a bunch of java animations of the different behaviors and what they do. There are several open source implementations of steering behaviors. Here's one.

  • \$\begingroup\$ Steering behaviours are perfect for this. \$\endgroup\$
    – tenpn
    Commented Feb 25, 2011 at 11:38

An easy thing to try is to have an invisible dot that goes ahead of the black dot and executes the path in your first image. The black dot then follows the invisible dot at a small distance behind.
I've seen this work with good results but of course might not suite your needs.


You must log in to answer this question.

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