Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

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.

Edit:

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 (lets 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

share|improve this answer
    
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 –  user Feb 23 '11 at 17:38
    
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 –  brainydexter Feb 23 '11 at 17:50
add comment

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.

share|improve this answer
add comment

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

http://www.red3d.com/cwr/steer/

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.

share|improve this answer
1  
+1 for OpenSteer –  David Young Feb 23 '11 at 18:32
    
+1 Steering behaviours FTW –  Ray Dey Feb 23 '11 at 21:04
    
Steering behaviours are perfect for this. –  tenpn Feb 25 '11 at 11:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.