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.
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?)
Answer
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
No comments:
Post a Comment