• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
rahulpawar

Pool/Billiard A.I. [New]

9 posts in this topic

How to do pool/billiard AI ?

Well actually I only need motion on XY-Plane(no rolling motion…cuz flat pieces as shown in the fig. below)

[center][img]http://i952.photobucket.com/albums/ae10/global_powers03/Carrom-AI-prob.jpg[/img][/center]


As in fig. During AI’s turn it needs to pit a piece (aka balls in pool) in hole, it only tries to pit its white/black pieces only.

Now the Final AI Function should return 3 values

1. Striker’s position on the Strip.
2. Striker’s Aim’s position (where to put cross-hair….where to hit !) and
3. Initial velocity (How hard to hit !)

Now lets assume for-now 100% hit rate….later random garbage value can then be added to these 100% Hit value to get lower difficulties of AI(missed hits !).

Now the Striker can hit a piece in a hole
1. Directly (Striker hits piece, piece falls in hole).
2. Indirectly (Striker hits a piece,……. that piece hits our intended piece then it falls in hole).
3. Rebound Shot (Striker hits a board wall and then rebounds to hit our intend piece which then falls in hole)

Now I was thinking like
[CODE]
Loop through all holes
{
For current hole -> Loop through all available piece to hit
{
Now if( a line passing through curr hole’s pos and curr piece’s pos also intersect Striker placing
strip and does not hit any other piece on the way)
{
Well, we got an answer for 1st case Striker Hit

Add this Shot to Available shots array along with its “Shot Weightage”.

Now How to get those other case also ?
}
}
}
[/CODE]
Then finally shot with highest/lowest Shot weightage will be chosen as current shot.

This will be required because we will be looping for every piece on board and every piece will probably be shot to hole using 2nd case of Striker Hit(multi-level collisions)….and we don’t want our AI to pull “Super Human” or “Vulcan” or “Rajnikanth” precision shots.

So how to put weight to these selected shots ?

Now this is what I came up with. Anyone with any other brilliant idea…….And people please talk !

[u][b]Some Points To Note :[/b][/u]

1] Now there is a StackOverflow post with exact same heading...(So the NEW in the Heading)
[url="http://stackoverflow.com/questions/2799785/pool-billiard-ai"]http://stackoverflow...ool-billiard-ai[/url]
But the guys there have discussed "What needs to be done"......we want [b]"How"[/b] so a functional code can be put together.

2] NO we cant go for "RandomShots>>genetic algo>>assessed using neural network" because we are in very limited CPU time and memory budget..Mobile platform.

3] We need to find those shots directly(without any kind of simulation) using maths,trigonometry,distance formula, etc

4] For velocity...we know final max velocity allowed to pit a piece so we just go on adding the amount of velocity reduce
due to friction and between collisions....to get initial velocity to fire the shot, which will be also in limited so if required initial
velocity is greater than "max allowed initial velocity" than assign Highest/lowest "Shot weightage" to current shot.

Thanks in advance for the patience. Edited by rahulpawar
0

Share this post


Link to post
Share on other sites
This is a tricky one, unlike most of AI it's a very continuous field, so hard to explore well. My suggestions:

1. Put in specific code for direct shots. Probably as simple as looking for any ball within x degrees of a straight line to any pocket. Check for obstacles, shoot.
2. Put in specific code for rebounds. Consider targets both before and after rebound. Could get hard if you allow multiple rebounds.
3. Crap shoot at a big bunch of balls, like a break. Very hard to predict the behaviour under physics, so perhaps just try each option with a few strengths and simulate the outcome to see if it's a good idea.
4. If you want a human-like good player rather than simply a computer-like good player, try some sort of minimax 1 or 2 levels deep to allow snookering your opponent. Based on the skills of computer and human odds of success could be assigned to each branch.

I would think that spin makes everything 10 times more difficult. Probably calculable with the right equations, but creates many more situations to explore.
1

Share this post


Link to post
Share on other sites
well thank you jefferytitan for your input.

the 3 point in your suggestion point to "running simulation to check how it looks", well as i already said that is out of question as pointed
out in my [u][b]"Some Points To Note :[/b][/u]" section point no 3.

although your suggestion 1 & 2 looks good but i need "Striker Hit" type 2 shots(Indirectly aka Multi-level collision) also....without running simulation
0

Share this post


Link to post
Share on other sites
Similar to step 1 you could check all the other balls and see if they could hit the ball you want to go in a pocket. Then just see if you can make the second ball hit into the first ball with the striker.
0

Share this post


Link to post
Share on other sites
[quote name='rahulpawar' timestamp='1338471116' post='4944968']
well thank you jefferytitan for your input.

the 3 point in your suggestion point to "running simulation to check how it looks", well as i already said that is out of question as pointed
out in my [u][b]"Some Points To Note :[/b][/u]" section point no 3.

although your suggestion 1 & 2 looks good but i need "Striker Hit" type 2 shots(Indirectly aka Multi-level collision) also....without running simulation
[/quote]

I will have a think about how one would do type 2 shots analytically. Regarding type 3 shots... it is my opinion from reading a lot of literature that this is impossible without running a simulation. The traditional approach for physics engines AFAIK is iterative solvers. If there were an analytical solution the physics guys would be all over it. My suggestion is to accept the simulation and think outside the box. For example, run the simulation with increased velocities and reduced iterations. Add a "talking smack" component to cover while you calculate, e.g. "oh man, you really snookered me here!", "can I get the 7... no...", etc. A human-like delay could be turned into a feature rather than a bug. Edited by jefferytitan
1

Share this post


Link to post
Share on other sites
I think that doing a simulation of many randomized shots and then picking the best one would work pretty well. If you calculated where the balls would all end up before starting the animation of the players shot you would have the entire graphical animation period to do some calculations along with the normal computer move making time. With 100 shots you would probably end up with something decent especially if you have parameters like minimum of 50% power which would prevent 0 power options from taking up computing time.
0

Share this post


Link to post
Share on other sites
[quote name='bloodisblue' timestamp='1338510210' post='4945137']
I think that doing a simulation of many randomized shots and then picking the best one would work pretty well. If you calculated where the balls would all end up before starting the animation of the players shot you would have the entire graphical animation period to do some calculations along with the normal computer move making time. With 100 shots you would probably end up with something decent especially if you have parameters like minimum of 50% power which would prevent 0 power options from taking up computing time.
[/quote]

I think that randomized is a waste of CPU. You should at least analytically determine that you'll hit at least one ball before running a simulation. Good point, you could do some calculations during animation of the player's turn (assuming you can determine the outcome of their turn quickly). You'd end up in trouble if the normal speed physics for their turn gave different results than your estimate that you based your turn on. You could run the physics high speed, record the positions, then perform a simple animation of their turn with no physics.
0

Share this post


Link to post
Share on other sites
Standard pool AI doesn't work from the cue forwards but rather from the pockets backwards. For each pocket, check the apparent angle to each "ball" to see if it is feasible, then check to see if that unblocked, then check to see what the angle to the cue is (feasibility again). Rate each shot based on difficulty and pick the easiest (or use a weighted random to mix it up a bit).

For actual performance, there are plenty of places you can fuzzy things up so that the AI doesn't look perfect and can even miss. Mostly, you just need to put some noise in the cue angle and the rest cascades through the shot process.
1

Share this post


Link to post
Share on other sites
[quote name='IADaveMark' timestamp='1338658785' post='4945616']
Standard pool AI doesn't work from the cue forwards but rather from the pockets backwards. For each pocket, check the apparent angle to each "ball" to see if it is feasible, then check to see if that unblocked, then check to see what the angle to the cue is (feasibility again). Rate each shot based on difficulty and pick the easiest (or use a weighted random to mix it up a bit).

For actual performance, there are plenty of places you can fuzzy things up so that the AI doesn't look perfect and can even miss. Mostly, you just need to put some noise in the cue angle and the rest cascades through the shot process.
[/quote]

I can see how that might work for a simple situation like cue ball + x rebounds + target. I still doubt that a perfect pool player is possible when multiple collisions are involved. The extreme would be a pool break, where I think only shoot-and-pray or hardcoding targets/strengths would work.
0

Share this post


Link to post
Share on other sites
I also think that the probe shot method is the simplest and the most flexible.

Sure, it takes time for the AI to calculate, but so does thinking about a shot in real life. I wouldn't be worried if it took say 5 seconds for the AI to think.

I once made an AI for a scorched earth clone. It took some 20000 probe shots in the worst case (with no early exit). Probe shooting included actual simulation of the bullet, checking with collision with the ground, and a lot of additional checks to rank each shot. collision detection was pretty much pixel color checks all along the trajectory (it was a DOS game). Getting the pixel color was dead slow on DOS and 640x480 resolution (because there has to be memory paging, since 640x480 cannot fit in the 16 bit VRAM address space).
Even with this dead slow method, it took at most 6 seconds for the AI to think.

Probe shooting even solves the complex shoot problem, in my game, AI could take pretty badass shots on bouncing border games with multiple bounces and nukes or lasers.

If you optimize the collision and simulation a bit, and use a bigger virtual delta time for the physics, or even a bit simplified physics (this also adds some error), probe shooting is feasible.


So again, for a turn based game, where the AI doesn't have to be anything real-time, I wouldn't be concerned if it took seconds for the AI to make a decision.


EDIT: maybe I'm wrong and you are using complex physics. Even so, I'd do some measurements. Probably calculating the positions after shots with the same starting conditions (same positions of balls, same angles etc), but with radically different delta times, and see how delta time affects the resulting positions of the balls. Edited by szecs
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0