Moving Object along Path ?
Author
Hi guys,
I'm working in 2D and have been messing around with some paths, they are basically some points that I interpolate between to make the path.
So, to find out where to go I take my X value and interpolate to get the Y value, all I have to do is keep track of the X points I'm between (because the path could loop around.)
First of all, is that the right way to do it ?
And secondly, how do I actually move my object along the path ? I was thinking of applying a 'steering force' toward the closest point on the path instead of just pointing the velocity that way. Does that sound right ?
If I knew what needed to be done I could probably do it but I'm kinda lost.
Thanks,
Cyrus
As for whether you track X and interpolate Y...that's not wrong; however, it also probably is not the best way. What I'd suggest is tracking a parameter, t, and interpolate both X and Y. The parameter t corresponds to a position along the curve. In this way, you can create path curves that can loop, have reversal and crossover points, etc. Much more flexible than you case.
I would suggest that you do a forum search for "Bezier curve" and "path". That should turn up some useful past discussions. In my opinion, Bezier curves are the most intuitive way to begin to understand parametric curves. The idea is that you will generate a series of 2D points, same as you do now. Then, you'll use those points as the control points in a Bezier curve. Then, you can have your object follow the Bezier curve by just varying the parameter, t, from 0 to 1. A value of 0 gives the point at one end of the curve and a value of 1 gives the point at the other end. Any value between 0 and 1 interpolates the interior of the curve.
(There is an article on Bezier curves and surfaces here at gamedev.net, but I don't feel its the right introduction for your purpose.)
The following link looks like it may be useful:
Bezier Curves
You'll need more if you want more than 4 points, though.
I would suggest that you do a forum search for "Bezier curve" and "path". That should turn up some useful past discussions. In my opinion, Bezier curves are the most intuitive way to begin to understand parametric curves. The idea is that you will generate a series of 2D points, same as you do now. Then, you'll use those points as the control points in a Bezier curve. Then, you can have your object follow the Bezier curve by just varying the parameter, t, from 0 to 1. A value of 0 gives the point at one end of the curve and a value of 1 gives the point at the other end. Any value between 0 and 1 interpolates the interior of the curve.
(There is an article on Bezier curves and surfaces here at gamedev.net, but I don't feel its the right introduction for your purpose.)
The following link looks like it may be useful:
Bezier Curves
You'll need more if you want more than 4 points, though.
As for having an object follow the path...are you trying to do physics to have the object stay approximately on the path? Or do you just want the object to be exactly *on* the path? If you want the object to exactly follow the path, don't both with force. Just find the path point and set the object's location to be that point. Now, you will want to deal with velocity. And that's a bit tricky since the parameter, t, that I mentioned in my prior email, is nonlinear. If you just change t with constant steps the object will appear to speed up and slow down depending on the curvature. You will need to consider an arc-length parameterization. You can read up on that at the following URL:
Moving At Constant Speed (parameterization by arc length)
Moving At Constant Speed (parameterization by arc length)
the advantage of using boids and steering behaviours is that it can work with collision avoidance and collision detection (that's when the avoidance failed and you did collided).
Being steered on a path like a train on rail, you can't realy do that, at least not as flexible, and it can turn into a headache (you'll need to introduce logic, so some objects will stop while other cross the path, and then objects can get stuck, waiting indifinitely, ect..).
the path, because it is a spline, can also clip other objects, like a wall or a corner, and then your object will go through stuff. With boids, it's just a matter of implementing a steering force to steer away from nearby walls.
so it depends, if you are confident the collision stuff is not a problem, splines are fine.
Being steered on a path like a train on rail, you can't realy do that, at least not as flexible, and it can turn into a headache (you'll need to introduce logic, so some objects will stop while other cross the path, and then objects can get stuck, waiting indifinitely, ect..).
the path, because it is a spline, can also clip other objects, like a wall or a corner, and then your object will go through stuff. With boids, it's just a matter of implementing a steering force to steer away from nearby walls.
so it depends, if you are confident the collision stuff is not a problem, splines are fine.
I'm looking at the same design problem as the OP but in a 2D platform style game. So I'd like to add my own problem to his thread...
Since my game engine is based on your (Oliii's) Rigid Bodies physics demo I already have collision detection and response in place.
I was thinking of having paths for enemies to follow. They would walk along platforms, jump gaps and run up slopes according to an AI script of some sort. The enemies are represented as rigid bodies, resting on the surface. I can detect if a body is resting. My idea is to move the enemy rigid bodies with a horizontal force pointing toward the next waypoint on their path. Gravity should keep the enemy moving along the platform. Along the way there could be obstacles since it's a dynamic game environment. So the path may be blocked and the AI should decide some other action.
This idea requires that I can detect when a waypoint has been reached, and it would be fine if the algorithm was tolerant to changes in the environment and impassable slopes etc. However I don't imagine that I will be implementing actual pathfinding. I can settle for enemies that are bound to a limited area.
What do you think, would it work???
Since my game engine is based on your (Oliii's) Rigid Bodies physics demo I already have collision detection and response in place.
I was thinking of having paths for enemies to follow. They would walk along platforms, jump gaps and run up slopes according to an AI script of some sort. The enemies are represented as rigid bodies, resting on the surface. I can detect if a body is resting. My idea is to move the enemy rigid bodies with a horizontal force pointing toward the next waypoint on their path. Gravity should keep the enemy moving along the platform. Along the way there could be obstacles since it's a dynamic game environment. So the path may be blocked and the AI should decide some other action.
This idea requires that I can detect when a waypoint has been reached, and it would be fine if the algorithm was tolerant to changes in the environment and impassable slopes etc. However I don't imagine that I will be implementing actual pathfinding. I can settle for enemies that are bound to a limited area.
What do you think, would it work???
That would work.
Since it's a 2D platformer, you can pre-build a map for navigation pretty easily. If you split the map into cells roughly the size of a single tile, then you can pre-proces the map, and generate special waypoints at cells, telling the A.I. the options it has when on that cell (like it's a cover point from the left direction, to progrees to the right, you need to jump, the path is completely block to the right, it's a vantage point from where you can snipe an area, it's a up-hill slope, it's a ladder, it's a grapple anchor point ...anything really). That stuff is used to create some flexible A.I. controlled enemies, and it can get hairy and pretty messed up (see Killzone for example). For a 2D platformer, It would be like a Soldat type of game, or a 2D Unreal Trounament.
for a simple platformer, I'd cut it short. Do you need rigid body dynamics? Do you need advanced physics and collisions? If not, and the dude just follows a pre-determined path stubbornly, you don't need to use rigid body dynamics, so you might as well put him on a path. It all depends from the scope of the game, what features you need, how you want the enemy to react (Mario versus a 2D Quake3).
Since it's a 2D platformer, you can pre-build a map for navigation pretty easily. If you split the map into cells roughly the size of a single tile, then you can pre-proces the map, and generate special waypoints at cells, telling the A.I. the options it has when on that cell (like it's a cover point from the left direction, to progrees to the right, you need to jump, the path is completely block to the right, it's a vantage point from where you can snipe an area, it's a up-hill slope, it's a ladder, it's a grapple anchor point ...anything really). That stuff is used to create some flexible A.I. controlled enemies, and it can get hairy and pretty messed up (see Killzone for example). For a 2D platformer, It would be like a Soldat type of game, or a 2D Unreal Trounament.
for a simple platformer, I'd cut it short. Do you need rigid body dynamics? Do you need advanced physics and collisions? If not, and the dude just follows a pre-determined path stubbornly, you don't need to use rigid body dynamics, so you might as well put him on a path. It all depends from the scope of the game, what features you need, how you want the enemy to react (Mario versus a 2D Quake3).
The game I'm trying to make is of the first kind you mentioned, a 2D action game with the sort of content you find in FPS games: intelligent enemies, destructible environment and so on.
Your comment gave me a better idea about how to solve problems like detecting when the AI-controlled enemies are near edges of platforms or in cover - actually it makes a lot of sense to code this together with the map design.
I can see that a zone-divided map is a better idea than laying out waypoints.
Using zones rather than waypoints would be better suited to handle situations such as when an AI-enemy is blown off a ledge or goes off course. As long as it ends up inside a zone it will have new options.
What I'm wondering is how could the enemies react to dynamic changes - like if the path is blocked by a boulder or some wreckage that could be used for cover.
Either the enemy should continually scan its path with line-object-intersection tests or the AI zone map should be updated in some way.
Or perhaps this just gets too hairy. My first solution will probably just have the enemy bonk its head and keep bonking it...
Your comment gave me a better idea about how to solve problems like detecting when the AI-controlled enemies are near edges of platforms or in cover - actually it makes a lot of sense to code this together with the map design.
I can see that a zone-divided map is a better idea than laying out waypoints.
Using zones rather than waypoints would be better suited to handle situations such as when an AI-enemy is blown off a ledge or goes off course. As long as it ends up inside a zone it will have new options.
What I'm wondering is how could the enemies react to dynamic changes - like if the path is blocked by a boulder or some wreckage that could be used for cover.
Either the enemy should continually scan its path with line-object-intersection tests or the AI zone map should be updated in some way.
Or perhaps this just gets too hairy. My first solution will probably just have the enemy bonk its head and keep bonking it...
After reading a bit on related topics such as bot programming I think I am now ready to formulate my previous thoughts coherently.
I will divide the playfield into zones with waypoints at the edges. The zones have the property that all the waypoints inside them can be reached by foot by an enemy happening to be there. This will ensure that enemies thrown about in the battle can always find their way around again by first detecting which zone they are in and then choosing from the waypoints.
So the level design will include drawing zones around all walkable surfaces.
The waypoints at the limit of zones connect to form a graph with the edges describing if connection is one-way, such as for a ledge, or must be jumped, if there is a gap between them. Then the enemy can plan ahead or know what to do when it reaches the edge of a platform.
Actually quite obvious, I think.
My solution to impassable wreckage blocking the way will probably be to first: scan the path to the waypoint with a line intersection test to avoid collision and choose another route, second: if the collision does happen, then mark the rigid bodies so they do not get pushed in front of the enemies being propelled by their horizontal force toward the goal. Hopefully, my AI will detect that it is not going anywhere and take action or else it will end up looking pretty stupid.
I will divide the playfield into zones with waypoints at the edges. The zones have the property that all the waypoints inside them can be reached by foot by an enemy happening to be there. This will ensure that enemies thrown about in the battle can always find their way around again by first detecting which zone they are in and then choosing from the waypoints.
So the level design will include drawing zones around all walkable surfaces.
The waypoints at the limit of zones connect to form a graph with the edges describing if connection is one-way, such as for a ledge, or must be jumped, if there is a gap between them. Then the enemy can plan ahead or know what to do when it reaches the edge of a platform.
Actually quite obvious, I think.
My solution to impassable wreckage blocking the way will probably be to first: scan the path to the waypoint with a line intersection test to avoid collision and choose another route, second: if the collision does happen, then mark the rigid bodies so they do not get pushed in front of the enemies being propelled by their horizontal force toward the goal. Hopefully, my AI will detect that it is not going anywhere and take action or else it will end up looking pretty stupid.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement