Path finding (creating) algorithm for game

Question

This is my first post in here. Maybe my tittle is not the best. Anyway, I'll try to be as more precise as possible describing my problem which you might help me with...

I'm a programmer, and I'm creating a game. In this game a particle has to move from one point A to a point B in a 2D space. In principle I want this particle to be intelligent and move in a kind of wave (sinusoidal). I don't care anything about the phase at the beginning nor at the end. I just want the particle to go from A to B.

However, my particle also has an intelligence coefficient, which makes it go straight forming a sinusoidal (if intelligent) to the end point or if the coefficient is really low it just takes totally random values.

My original idea was to have the intelligence coefficient between 0 and 1, in such a way that to calculate the next point P it is => P = sinPoint.intelligence + randomPoint.(1-intelligence). However, after thinking about it, I think it is my worst idea ever.... Yes it could work for very intelligent and very stupid particles, but for middle cases it just makes it so messed up....

So when I realized it I was so confused I decided to go into a mathematical forum to ask for some kind of hint or idea about what could I make.

And the final details...I have a piece of code that is going to recalculate the position and plot it constantly, about every 0.005 seconds. So my piece of code doesn't depend on time, although I could fix this, and the real problem is that for the middle cases I get lost on how to recover the sinusoidal trajectory after adding half of the new position randomly.

Thanks for the help.

Regards.

Answer 1

Why not make the sinusoidal part extra? That is, make the actual path more linear, but have a separate variable that moves it from side to side along whatever path it's following. That way you can make more irregular motion without making your path problem harder.

Or alternatively, I'd suggest some kind of skewing factor based on angle. Someone who knows more on distributions can probably give a better example than this, but I'll give it a shot.

If you can already get a uniformly distributed random number (common in programming languages) called x that represents the difference between the goal angle and travel angle, pass it into something like:

sgn(x) * 180 * (|x|/180)^(intelligence).

Where angles range from -180 to 180 and intelligence has a range of [1, some high value].

The idea is that if your difference is zero (i.e, on target), you'll go there. Same with direct reverse. But any angle between will be brought closer to zero (i.e, more on target) by higher intelligence. Since the lowest intelligence is 1, the distribution won't change anything in the dumbest case: your path will still be random. You'd have to play around with values of intelligence to get the variance you want, but this is the general idea I'd use if you can't keep track of time for whatever reason.

Note: The sgn() function is there because the function takes the absolute value of angle difference and you need to keep track of which side of the goal you're going towards. You can instead do this with an if statement or however else you wish.

Answer 2

My experience is that, for the eye that doesn't know what is going on, random walking looks just wrong. Much better results can be produced always going (using sinusoidal trajectory or whatever other path you wish) to some point, just this point being picked not really close to the target, if the particle is "stupid".

Simple approach would be to pick some $k$ points, such that $dist(p_i, p_{i+1}) = \frac{dist(A,B)}{k-1}$, but

• if intelligence is 1, then this would form a stright line,
• if intelligence is 0, every next direction would be random.

There are many ways of choosing the formula for intelligence between 0 and 1, e.g. $dir = correct\_dir + rand(-pi,+pi)*(1-intelligence)^\alpha$ might be one you could use (big $\alpha$ will make even small intelligence gain matter, $\alpha \ll 1$ will make particles stubbornly stupid, of course simple $\alpha = 1$ might be the best choice if nothing else depends on the intelligence).

Answer 3

For each step in the random walk, you can pick a random angle between $0$ and $(45 \times (1 - \text{intelligence}))$. If the particle is currently facing to the left of the target, it rotates to the right (clockwise?) these many degrees. Otherwise, it rotates these many degrees to the left.

Here's an example: You have a particle of a medium intelligence. Say that the particle is currently facing $5$ degrees too far to the right of the target. That is, from the particle's point of view, the target is $5$ degrees to the left from straight ahead. If you randomly choose $0$, then your particle keeps moving straight. If you randomly choose $5$, then the particle rotates $5$ degrees (to the left because it is facing to far too the right), so that is is now facing straight at the target. If you randomly choose $15$, then you rotate $15$ degrees to the left, so that it is currently facing $10$ degrees too far to the left of the target. This will repeat, with the particle alternating from moving to the left and then to the right, but always towards the target.

For a low intelligence, this would create a path that appears sporadic but will never travel away from the target, since the sporadic motions are in the direction to correct the course. For a perfect intelligence, this will become a straight line. If the intelligence is moderately high, then the path will not be a straight line, but will be wavy.