Page 1 of 1
[solved] Multi-ball Pong AI, Finding/Following optimal ball
Posted: Sat Jul 13, 2013 7:09 pm
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!
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 12:01 am
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.
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 2:09 am
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!
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 1:33 pm
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.
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 3:52 pm
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.
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 7:29 pm
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.
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Sun Jul 14, 2013 11:35 pm
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 :-)
Re: Multi-ball Pong AI, Finding and Following the optimal ba
Posted: Mon Jul 15, 2013 1:53 am
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.