How Would You Do This? - #6 - Pathing

21 posts

Flag Post

Let’s say you’ve got a map like this:

Spawn “enemies” on the left side of the line and have them walk along the path to the bottom of the line, similar to Bloons TD.

 
Flag Post

Set of points? For curves, maybe beizer based path.

 
Flag Post
Originally posted by UnknownGuardian:

Set of points? For curves, maybe beizer based path.

IMO Points would be a little bit choppy since they are curves.

 
Flag Post

So smooth it out a bit.

Related Question + Code Samples
Visual Demo

 
Flag Post
Originally posted by UnknownGuardian:

So smooth it out a bit.

I guess you could just do a lot of points, and use interpolation.

 
Flag Post

I suppose there’s a way of getting them to analyse the line itself and move accordingly, but I suppose it’d be far too complicated/slow.

If you use points going down to a pixel level, it is still going to be perfectly accurate, but probably slow. Find a happy middle-ground?

 
Flag Post

I’d use path list, (x,y,distance) and interpolate in 10-length increment, or alike. Analyzing the line I think should be way preprocessed, up to design time.

 
Flag Post

I’d fit the curve with a cubic spline and have the mobs walk along its parameter. (Splines are smooth.)

 
Flag Post

I don’t recommend defining the path with a bezier curve or spline. While it may be a simple matter to find a mathematical equation for a curve that reasonably fits the desired path, the real problem will be moving along it.

Let’s say that you have a creature whose movement rate is 3.5 pixels per frame. Given the creature’s current (x,y) coordinate, which is along the mathematically defined curve, how do you compute for the creature’s new position along the curve at the end of the frame? Note that the length along the curve between the current position and the new position has to be 3.5 pixels, assuming that the creature exhausted its full movement rate. Are you going to use numerical methods to integrate the formula and do a binary search for various (x,y) coordinates until you solve the problem? If so, imagine doing this for several creatures that have to travel along this very path at the same time. God forbid you should use such a method for a tower defense game.

I would recommend using a set of points to approximate the path instead. I was told that this technique was used in Bloons Tower Defense, which features curved paths. If the points are close enough, no one need know that the actual path is not smooth.

In the picture shown above, I used a set of points to define the path. I arrived at these points by drawing circles that are connected to each other and getting their center points.

From there, you can determine the new (x,y) coordinates from a creature’s starting point, movement rate, and ultimate destination by using sine law, cosine law, and the Pythagorean theorem.

 
Flag Post

I had to do it in Unity.

I went and got a tween engine specifically for it.

 
Flag Post

If you move an entity along a bezier curve walking along it’s parameter you’ll see the entity speeding up and slowing down in places.

You can treat a bezier curve simply as a lot of points and thus lots of little lines between these points. (Say a point every 0.01t depending on how accurate you want it to be).
However, this gives you lots of little straight lines of varying length meaning your speed varies if you increase the curve parameter at a consistent rate. To correct this you’d need to convert your physical speed into the line parameter delta of the current ‘little line’ of the curve your entity is on (and take into account that your speed may/will make you move to the next little line etc etc).

So while making a bezier curve is probably the easiest way to generate a curve, moving an object along it at a conssitent rate turns into a bit of a ballache.

Elyzius appraoch seems get around the bezier problem, but how do you go about generating all of those spheres apart from manually plotting them?

(This example of smooth bezzie movement with a ball walking along its parameter, though it has gravity to accelerate it)
http://www.newgrounds.com/dump/item/63b27287977180284707195b44ccd57e

 
Flag Post

I’d quantise the cubic spline because as others have said there is no trivial way to find evenly spaced points on one in its raw form. (You basically have to guess and then use N/R or something similar to converge on the right spot.) This seems to be something of a consensus.

 
Flag Post
Originally posted by JayHobsie:

If you move an entity along a bezier curve walking along it’s parameter you’ll see the entity speeding up and slowing down in places.

This is true, but for the game I was building, I was OK with this, as it was negligible in most places, and was simple to build. The game was only needed as a tech demo (it doesn’t even have a menu or help screen, or even any functional code when you win/lose).

 
Flag Post

Is there any overly-complicated maths which allow you to calculated the actual length of a line joining two points on a curve?

It’s easy enough if you let all the connections be straight lines, but is there any way to do it so that your distances are measured along the curve itself?

 
Flag Post

If you have a function sure. If not, you can approximate with some formulas, which I cannot recall what they were, but involve breaking up one of the axis into really small amounts and doing the sum of the pythagorean’s from each point on the curve.

 
Flag Post
Originally posted by UnknownGuardian:

If you have a function sure. If not, you can approximate with some formulas, which I cannot recall what they were, but involve breaking up one of the axis into really small amounts and doing the sum of the pythagorean’s from each point on the curve.

Ok, that would make sense. Kind of like finding an approximate instantaneous gradient, only you’re finding the distance instead?
 
Flag Post

There isn’t so much a formula as a general equation that links the functional form to the length of the path. The problem is that you then have to solve said equation which, in general, can be any flavor of f’d up. So yes, if speedups/slowdowns are a problem, you can try other forms of movement.

For instance, starting on the curve, compute the tangent direction and walk a fixed length step in that direction then project the end point back onto the curve. Repeat as necessary. If your steps are small enough and the curve is (locally) straight enough you’ll be fine. You can compute the radius of curvature at your starting point to determine the step size if you’re feeling fancy.

 
Flag Post
Originally posted by BobJanova:

I’d quantise the cubic spline because as others have said there is no trivial way to find evenly spaced points on one in its raw form. (You basically have to guess and then use N/R or something similar to converge on the right spot.) This seems to be something of a consensus.

Hrm I’m not very knowledgeable about this but I don’t see why it’s not doable… If you have a curve you can then parametrize it with the arclength parametrization and then increase the parameter at a constant rate. The math will probably be a bit involved though, but I’m sure there’s gotta be some research out there with closed form solutions for B-splines at least.

Of course, that’s not really a great use of the programmer’s time…

 
Flag Post

This probably wont work with curves, but for flat parts, I never understood why you couldnt just have a bitmap that covered everything but the path, and just hittest against it. Would this just be slow or something like that?

 
Flag Post
Originally posted by BluePriest:

I never understood why you couldnt just have a bitmap that covered everything but the path, and just hittest against it. Would this just be slow or something like that?

1) How does that solve the pathing issue?
2) Hells yea it’s slow

 
Flag Post
Originally posted by jonathanasdf:

Hrm I’m not very knowledgeable about this but I don’t see why it’s not doable… If you have a curve you can then parametrize it with the arclength parametrization and then increase the parameter at a constant rate.

The arc length parameterisation for a cubic spline is definitely not a ‘trivial way’ in my book, and quantising the path is likely to be faster and easier to deal with.