2
\$\begingroup\$

Currently I have a 2D game in which the player and a computer controlled (non-player) sprite move from point to point collecting tokens in a continuous environment. The player and the non-player sprite are usually moving between two different points at different times, not together. One aspect of this game is tricking the player into believing that they are playing a multi-player game with another person, when in reality the other character is controlled by the computer.

The non-player sprites are currently controlled by a boid algorithm, which results in movement that is very smooth and linear. Since players use arrow keys to control their sprite, the smooth linear movement of the non-player sprites is not particularly convincing for tricking the player into believing the other character is human controlled. Adding random perturbations to the boid algorithm increases believe-ability, but does not exactly look natural.

I feel this should be easy, but for some reason I'm just not seeing it, so here is my question: Is there a simple algorithm for sprite motion between two 2D points that would realistically simulate a human controlling a sprite with arrow keys?

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Have you considered using the boids algorithm to produce a "desired" heading, then having your AI press virtual arrow keys according to how much this desired heading differs from its current velocity? \$\endgroup\$
    – DMGregory
    Jul 1 at 23:17
  • \$\begingroup\$ @DMGregory Yes, this is the first thing I tried. Implementing it requires computing a number of dot products between two vectors to determine the right combination of virtual arrow keys to press. Even though dot products are fast, this game runs in browser in javascript, and continually computing all these dot products significantly slows down performance of the browser, especially if the player has many tabs open, resulting in a sub par experience. Maybe I'm not implementing it well though. \$\endgroup\$
    – nguzman
    Jul 1 at 23:23
  • \$\begingroup\$ Try showing us your implementation if you'd like some help improving it. \$\endgroup\$
    – DMGregory
    Jul 1 at 23:26
  • \$\begingroup\$ Did you consider pre-recording the movements, and just re-playing them? \$\endgroup\$
    – Vaillancourt
    Jul 2 at 0:15
  • 1
    \$\begingroup\$ @Vaillancourt Given the length of the game and desired variability of the sprite trajectories, this is unfortunately not a feasible solution. I reworked the algorithm suggested above, and while browser performance is good, the trajectories are not as human-like as would be desired. Working on a potential solution, which I will post if it works out. Thanks for the suggestions. \$\endgroup\$
    – nguzman
    Jul 3 at 19:33
0
\$\begingroup\$

Ok, here is a heuristic solution that results in sprite motion qualitatively similar to what one would expect from a human player using arrow keys. This solution works for motion from an initial position (A) in 2D to a goal position (B) in 2D:

  1. First, define vectors corresponding to the arrow key directions.
  2. Then, compute the heading vector between A and B.
  3. Compute the angle between the heading vector and all of the arrow key direction vectors.
  4. Select the arrow key direction vector with the smallest angle between itself and the heading vector. Assign this direction to some variable v.
  5. On every update step, with some probability p, increment the sprite's position by v, and with probability 1-p, repeat steps 2-4 to compute a new v, replacing the original point A by your current position.

Values above 0.5 for p seem to work best. Here is some pseudocode (with arbitrary assumption that velocity = 1):

UP = [0,1]
DOWN = [0,-1]
RIGHT = [1,0]
LEFT = [-1,0]

DIRS = [UP, DOWN, LEFT, RIGHT]

get_direction(sprite_X, sprite_Y, goal_X, goal_Y, DIRS):
    A = [sprite_X, sprite_Y]
    B = [goal_X, goal_Y]
    heading = (B - A) / |B - A|
    angles = []
    for DIR in DIRS:
        angles.append(angle_between(DIR,heading))
    v = DIRS[index_of_minimum(angles)]
    return v

update(sprite_X, sprite_Y, goal_X, goal_Y, v, DIRS, p):
    sprite_position = [sprite_X, sprite_Y]
    if (random(0, 1) <= p):
        sprite_position += v
    else:
        v = get_direction(sprite_X, sprite_Y, goal_X, goal_Y, DIRS)
        sprite_position += v
    return sprite_position
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.