Archived

This topic is now archived and is closed to further replies.

Erkki

AI movement along bezier curves

Recommended Posts

Erkki    122
In my game prototype (top down 2D), I want to create roads / paths with the help of lines and bezier curves. I also want the AI to be able to travel along those lines and curves. Umm... I had a technical question, but I already figured it out while typing. So I''ll ask something else: Has anyone here done this? Know any samples with source code? Do bezier curves tax the CPU a lot?

Share this post


Link to post
Share on other sites
IADaveMark    3731
I would suspect that there is likely a level of detail that you can address without needing the full bezier curve.

Here''s an odd example. In our game, the aircraft are travelling Great Circle routes from city to city. This is being plotted on the latitude/longitude coordinate system. Moving the aircraft is no big deal since I have the formula for moving along GC routes. However, when I want to plot the route on the map, I need to pull a couple of tricks. Since we are not using polar maps, the route would be displayed on the map as a curved line rather than a straight one. In order to display this accurately, I would have to do a lot of calculations. Rather than draw the full curve, we are dividing the trip into a number of segments (the number depends on the overall length of the trip) and drawing each segement as a straight line. As the flights move, they will occasionally deviate from being over the line (midway between the segment endpoints) and then re-intersect the line... but this effect is negligible and acceptable. Since there can be scores of route lines drawn on the screen at one time, it sure beats calculating all of those curves in detail.

The answer is, then... are you asking the right question? Do your agents REALLY need to travel the curves exactly or is there a way you can simplify the problem?

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Timkin    864
quote:
Original post by Erkki
Has anyone here done this? Know any samples with source code? Do bezier curves tax the CPU a lot?


This question has been asked and answered many, many times in the Maths & Physics forum. Search the archives of the forum for your answers, as I can assure you that there is more than enough information and (pseudo-)code snippets there to help you out.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Erkki    122
I want them to move on the curves *sometimes* -- when they are traveling in a vehicle on a road. I guess I don''t need very precice movement -- I could make the road wide enough to compensate for low level of detail. But the roads themselves will be lines & bezier curves.

And also I planned to do player movement by clicking the mouse on a destination. So when the player is in a car and clicks on the road, the car should not travel straight but following the roads curves.

From what i''ve messed around with so far, I figure I could even get away with having only 2-5 points calculated by the bezier curve algorithm (I''ve tested with the one in SDL_gfx).

Share this post


Link to post
Share on other sites
IADaveMark    3731
Now that you have explained the situation better, another approach may be in order. If you have a way of having the unit "see" the road somehow, perhaps a path following algorithm is needed. Rather than following the actual curve, the unit just needs to know how to stay on the road properly... wherever that may lead. Check out this link for some fantastic examples of flocking, following, etc.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

Share this post


Link to post
Share on other sites
Erkki    122
Timkin, sorry, should have searched.

Thanx, InnocuousFox. I''m very intersted in flocking and related things, but so far I haven''t really digged into it. I may give it a try tomorrow. Somewhy it didn''t hit me that steering/following would apply to my roads even though I''ve visited that site before

But looking at the path following demo on the site, I see there is a target for the agent that is moving exactly along the path. So I would still need to keep something following the curve exactly, because I don''t know of any other way the agent could "see" the road (and know which direction to travel in). But the target movement could use much less detail I guess.

Share this post


Link to post
Share on other sites