[solved] Multi-ball Pong AI, Finding/Following optimal ball

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
Shanulu
Prole
Posts: 21
Joined: Mon Jun 24, 2013 11:34 pm

[solved] Multi-ball Pong AI, Finding/Following optimal ball

Post by Shanulu »

I've ran into a wall when trying to create AI for my multi-ball pong. This is what I have in my head:

Step 1: Go through the list of balls and find the ones travelling towards my AI paddle
Step 2: Put them in a potentialTargets table
Step 3: Find out which potentialTargets will reach the bottom first by applying their current Y value (y) + their Vertical Velocity (v) over an undetermined period of time.
Step 4: Flag the ball to be a target
Step 5: move the ball towards the target

Here is what I have:

Code: Select all

function findTargetBall()
	--table to store our potential balls
	local potentialTargets = {}
	--index for our table above
	local j = 1

	for i = 1, #ballList do
		if ballList[i].v > 0 then
			--store all the balls moving down in our table
			potentialTargets[j] = ballList[i]
			j = j + 1
		end
	end

	for i = 1, #potentialTargets do
		--store our potentialTargets Y so we don't change it
		local y = potentialTargets[i].y
			--compare the y to our paddles
			while  y <= paddleList[2].y do
				--as long as its not passed our paddle we add some velocity
				y = y + potentialTargets[i].v
				--and count the steps
				potentialTargets[i].stepsToPaddle = potentialTargets[i].stepsToPaddle + 1
			end
		--now we sort by the steps putting the smallest in the front
		table.sort(potentialTargets, function(a,b) return a.stepsToPaddle < b.stepsToPaddle end)
	end
	
	for i = 1, #ballList do
		if ballList[i] == potentialTargets[1] then
			ballList[i].isTarget = true
		else
			ballList[i].isTarget = false
		end
	end
	
end
and the movement code, which doesn't work CORRECTLY and somehow my paddle skips. IE: teleports from one part of the screen in a single step instead of actually moving.

Code: Select all

--AI movement
	for i = 1, #ballList do
		local x = paddleList[2].x + .5 * paddleList[2].w
		if ballList[i].isTarget then
			if ballList[i].x >= x then
				--if its further than 5
				if ballList[i].x - x >= 5 then
					paddleList[2]:update(4.5) --Our max ball speed is 5, we want to be able to beat it
				else
					paddleList[2]:update(ballList[i].x - x)
				end
			elseif ballList[i].x < x then
				--if its further than 5
				if ballList[i].x - x >= -5 then
					paddleList[2]:update(-4.5)
				else
					paddleList[2]:update(ballList[i].x - x)
				end
			end
		end
	end
So if you've made it this far I have to ask: Is this a terrible approach? Suggestions?

I want to get this all set before I re-write my program to include/learn physics so I can implement my magnet and repel abilities!
Attachments
prototypePong.love
A and D to move top paddle
W spawns more balls
(2.82 KiB) Downloaded 156 times
Last edited by Shanulu on Mon Jul 15, 2013 2:52 am, edited 1 time in total.
User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by raidho36 »

Your first problem is that "x" is right side of the paddle and not it's center. I'm not sure for the rest though.

This is actually a good quesiton. I'm not entirely sure if there's an optimal approach at all. For this kind of task, I'd rather used genetically generated AI program, but that task itself is a big challenge.

I think that just trying to reflect one sweetestly looking ball, it should instead try to reflect as many incoming balls as possible, which includes deliberately letting certain balls through to get better chance to get the big crowd of them.
Shanulu
Prole
Posts: 21
Joined: Mon Jun 24, 2013 11:34 pm

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by Shanulu »

raidho36 wrote:Your first problem is that "x" is right side of the paddle and not it's center. I'm not sure for the rest though.

This is actually a good quesiton. I'm not entirely sure if there's an optimal approach at all. For this kind of task, I'd rather used genetically generated AI program, but that task itself is a big challenge.

I think that just trying to reflect one sweetestly looking ball, it should instead try to reflect as many incoming balls as possible, which includes deliberately letting certain balls through to get better chance to get the big crowd of them.
I did set x to my paddles x + 1/2 of the width, i think thats the only time i use X, but if not, can you be more specific...

Also, that is a good idea, trying to optimize multiple balls by allowing some to pass, though I bet its a pain to implement. I'll keep that in mind for later!
User avatar
chezrom
Citizen
Posts: 59
Joined: Tue May 28, 2013 11:03 pm
Location: France

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by chezrom »

Your problem with bot's paddle movement is due to this code :

Code: Select all

if ballList[i].x - x >= -5 then
	paddleList[2]:update(-4.5)
else
	paddleList[2]:update(ballList[i].x - x)
end
The comparaison must be inverted because -1 is greater than -5.

As an advice, don't use hard coded value as 5 or 4.5, use a variable to hold them, if latter you want tune the values, it will be more easy.

Be aware than your code depend of the frame rate because you don't use "dt", so it can be ok (and I agree it's easier to code) but it depends of the running system and the displayed object can have a not fluid movement.
Shanulu
Prole
Posts: 21
Joined: Mon Jun 24, 2013 11:34 pm

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by Shanulu »

Good catch!

I went ahead and decided to separate my code into their own files and re-write my AI functions at the same time but I kept the same approach. Thanks for the note about dt, I was aware I should be using it but when things start working for me it was unclear if it was necessary. I'll definitely put it in on my next complete re-write.

With that said my AI function now works a touch better. I still think it has trouble with new balls being created (I tried throwing in extra calls to my AI when I create them). I remembered last night that I need to flag '.isTarget' to being false after I hit it, to prevent it from following it.

Overall the only large problem I see is it sometimes picks the wrong ball, which may be non-use of the dt on my velocities. I simplified the way I estimate how long it will take to reach the bottom by using:

Code: Select all

(height of my window - ball y)/ball velocity
I believe this will yield a number in which the smallest will be the one I need to target.

If anyone out there cares to bother with it and provide assistance (more thought assistance than writing code assistance, though any/all is appreciated) feel free. Here is the github: https://github.com/Shanulu/prototypePong

I've also attached the repackaged file.
Attachments
ShanuluPong.love
(4.38 KiB) Downloaded 148 times
User avatar
chezrom
Citizen
Posts: 59
Joined: Tue May 28, 2013 11:03 pm
Location: France

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by chezrom »

I don't understand why you do all this actions (copy, sort, multiple scan of two tables) to get the target ball. You have multiple ball records than have the flag on ...

You can do it asier by scanning the list of balls and keeping the min step value and current target ball.
If the current ball has a less step value than the current target, the the current ball becomes the current target.
If at the end you have no target, you can displace the paddle to be in center of the screen.

Here's the code, I don't use another table than ballList :

Code: Select all

function findOptimal()

	local target
	local minSteps=math.huge

	for _,b in ipairs(ballList) do
		if b.v > 0 then
			local steps = (height - b.y)/b.v
			if steps < minSteps then
				minSteps=steps
				target=b
			end
		end
	end

	local xobj
	if target then
		xobj = target.x
	else
		xobj = love.graphics.getWidth()/2
	end
	local xdelta = xobj - paddleList[2].x - paddleList[2].w/2
	if xdelta < -4 then xdelta = -4 end
	if xdelta > 4 then xdelta = 4 end
	paddleList[2]:update(xdelta)
end
In this code :
  • target is the current target ball
  • minSteps is the current minimal steps
  • xobj is the taget x coordinate (the target ball or the center of the line if no target)
Now this algorithm is not optimal, you select the ball than come first even if you cannot catch it and follow the x coord
However, it can give good result.

For a more effective method, you must not only know when the ball comes but also where, at which x coordinates, so the ai can be able to select balls and skip the uncatchable, and be more effective to place the paddle (not follow the x coord of the target ball)

The computation of target x (with bounce) is not complex but has some tricks. But I am tired, and speak about that in another post if possible.
Last edited by chezrom on Mon Jul 15, 2013 8:34 am, edited 1 time in total.
Merlin_ua
Prole
Posts: 4
Joined: Fri Jun 21, 2013 7:34 am

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by Merlin_ua »

I totally agree with what chezrom said. Below is a short snippet with a possible implementation of findOptimal that predicts where the ball will hit the paddle. Note that I didn't include chezrom's modifications, you should try merging the code if you want.

Code: Select all

function findOptimal()
 for i = 1, #potentialTargets do
  --count steps until the ball hits the paddle
  potentialTargets[i].stepsToPaddle = (paddleList[2].y - potentialTargets[i].r - potentialTargets[i].y)/potentialTargets[i].v
 end
 --sort the table now and put the shortest stepsToPaddle in the front
 table.sort(potentialTargets, function (a,b) return a.stepsToPaddle < b.stepsToPaddle end )

  --flag the ball that is our target
  targetX = love.graphics.getWidth() / 2
  if #potentialTargets > 0 then
    --predict the X coordinate where the ball will hit the paddle
    local destination = potentialTargets[1].x + potentialTargets[1].stepsToPaddle * potentialTargets[1].h
    local boundLeft = potentialTargets[1].r
    local boundRight = width - potentialTargets[1].r
    local fieldWidth = boundRight - boundLeft
    local offset = (destination - boundLeft) % fieldWidth
    local cycles = (destination - boundLeft - offset) / fieldWidth
    if cycles % 2 == 0 then
      targetX = offset + boundLeft
    else
      targetX = boundRight - offset
    end
  end
  targetX = targetX - paddleList[2].w / 2

  --using targetX-4 prevents oscillating around the target position
  if paddleList[2].x < targetX - 4 then
    paddleList[2]:update(4)
  elseif paddleList[2].x > targetX then
    paddleList[2]:update(-4)
  end
end
Three things worth mentioning here:
  • I modified potentialTargets.stepsToPaddle to correctly calculate the time until impact with the paddle. Take into account that ball.y is just the center, while point of impact is ball.y + ball.r
  • The logic of destination calculation is to predict how many times the ball will bounce. There are few caveats about this part, I can elaborate on it if you have any questions.
  • You previous code had a problem of paddle oscillating around X coordinate of slow balls. To understand this consider an example: our target X is 2, current paddle X is 0. First you jump right, your X becomes 4. Next frame you jump back, your X becomes 0 again. And this goes on. The reason is that we can't reach 2 in steps of 4. To solve this I changed the comparison to "paddleList[2].x < targetX - 4"


Sorry if any of this sounds confusing, I though it would be easier to explain when I started writing the post :-)
Shanulu
Prole
Posts: 21
Joined: Mon Jun 24, 2013 11:34 pm

Re: Multi-ball Pong AI, Finding and Following the optimal ba

Post by Shanulu »

Thanks for the replies everyone, really! As for copying and then modifying the table I guess I just really didn't think of using the one I already had, hence why I ask about. I definitely am going to dissect your code.

As for the y plus the radius, that's a good catch thanks! And yes on my second attempt I didn't bother making it track the ball perfectly as I was sure to re-write it, so when it latches on it staggers between the two.
Post Reply

Who is online

Users browsing this forum: Bing [Bot] and 2 guests