Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have finished a simple 2D one-on-one indoor football Android game. The thing that it seemed so simple to me, a human being, turned out to be difficult for a computer: how to go around the opponent …

At the moment the game logic of the computer player is that if it hits into the human player will step back few points on the pixel greed and then try again to go towards the ball. The problem is if the human player is in-between then the computer player will oscillate in one place, which does not look very nice and the human opponent can use this weakness to control the game. You can see this in the photo – at the moment the computer will go along the red line indefinitely.

enter image description here

I tried few ideas but it proved not easy to do it when both the human player and the ball are constantly moving so at each step computer would change directions and “oscillate” again. Once when the computer player reaches the ball it will kick it with certain amount of random strength and direction towards the human’s goal.

The question here is how to formulate the logic of going around the ever moving human opponent and how to translate it into the co-ordinate system and frame by frame animation… any suggestions welcome.

share|improve this question
    
I saw football in the title and got excited, then I saw it was soccer... I like the A* recommendation though; and good luck. –  Nate Jun 25 '12 at 13:53
add comment

4 Answers

up vote 5 down vote accepted

First I will state that A* sounds like a lot of trouble. It is a pathfinding algorithm, great if you need to find a path, but this is simple obstacle avoidance. A* also requires recomputation every time the environment state changes, which is every frame in a real time game, or you'll need to use some clever variation that adapts to change.

I don't know how all of your game logic works so it's a little hard to give super-specific advice, but one solution that may be perfectly appropriate is using a potential function, an inverse-square function that calculates a repulsive force based on how close the two agents are to each other. The closer they get, the stronger the repulsive force. It's easy to work with because you don't have to do any high-level path calculation, you just let your agents try to go where they want to go, then calculate the potential force and add it to their movement vectors to displace their movement around obstacles.

The basic equation is (constant / (distanceToObstacle)^2) Compute this and use it to displace your agents' movement vectors opposite the direction to the obstacle. Being an inverse function, the further they are from the obstacle the smaller the force (insignificant beyond a short distance), the closer they get the larger the force, and it grows very quickly so the closer two guys get to each other, the more the repulsive force displaces their movement. You will need to mess around with the constant value and possibly try a cubic function or other exponent instead of square to get the right look. I used this in a space combat game and found inverse square worked well for ship/ship avoidance, as it gave the right effect of looking like the guys were driving around each other to avoid an impact, but for ship/planet avoidance a cubic function was better as I got a close-hugging path without oscillation. One thing that's particularly nice about dist^2 is that it's computationally cheap and often cached anyway for basic collision testing, etc.

I learned the technique from a section in AI For Game Developers. I didn't come up with any great looking resources in a quick search but you can probably find something free with a more complete explanation than mine.

share|improve this answer
    
+1 I like this idea better than mine. –  knight666 Jun 25 '12 at 19:18
    
Thanks, I toned down my response a little because I sounded like a jerk. –  Suboptimus Jun 25 '12 at 19:20
    
This is basically the avoidance or separation "steering" behaviour - red3d.com/cwr/steer –  Kylotan Jun 25 '12 at 19:39
    
That is a great advice. You helped me think out of the box for a moment - this is like a physical simulation of repelling magnets. I’ll try to implement it and see what happens... –  Lumis Jun 25 '12 at 22:32
    
Glad you like it. When I read about this technique it was a revelation. I was trying to accomplish the same thing but modeling spaceships and the directions I was going in myself were way more complicated than necessary, basically thinking about pathfinding, higher-level navigation, etc. This doesn't require any higher-level infrastructure, is pretty light computationally (certainly by today's standards) and can give very nice results given some time to tweak. –  Suboptimus Jun 25 '12 at 22:41
show 2 more comments

My first instinct would be this:

Draw a line between the human and the computer players, get the angle of this.

decide whether you're going to circle above or below (random? whether your y is above his?)

Add/subtract say 15 degrees from this angle depending on which direction you want to go

Using the human player as the origin draw a line in this new direction (either the same length as the original line or some minimum?)

find the coordinates of the other end of the line

move towards there

repeat every few frames

no idea how well this would actually work though

share|improve this answer
    
Thanks for the comment. The problem is that the computer player would calculate a new path on every frame - the question is for how long should it follow a certain path? This also depends on the movement of the ball and the human player... –  Lumis Jun 24 '12 at 9:54
    
Angles are computationally expensive (although you could probably get away with it this time). What's worse is the idea of using the relative Y coordinate to decide on which side to pass. That approach suffers from a division by zero when you're vertically aligned. –  MSalters Jun 25 '12 at 12:39
    
I was assuming they were to one side in this case, I think in reality you'd want to do the line perpendicular to the direction to the goal? Why would you be using division finding which side to pass on? –  zacaj Jun 26 '12 at 20:51
add comment

The easier solution may be to step a few pixels back and aside in a random direction. Not only will this typically solve your problem, but the unpredictability of the behavior is harder for the human player to counter or exploit.

share|improve this answer
add comment

As silly as this may sound, I think you should try using the A* search algorithm.

The Wikipedia page has quite a nice example:

A*

What you want to do in your game is define a grid of possible locations for the AI player and have the player come up as an area of really high resistance. The algorithm will try to find the shortest route between it and the ball. If a player is in between, it tries to find the shortest route to the ball around the obstruction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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