Archive for January, 2010

Probably Unfinished Game

January 30, 2010

I don’t think I’ll get this finished. Either way, I’m willing to share the code I have so far (just e-mail, or just post a comment here). Also, this is the strategy I was considering: all of the following presumes you understand the game rules as given

  • first, sans bumpers, my initial thought was to find the closest puck of my color, and (two — maybe more) nearby grey pucks and encircle both — checking that it was possible (able to move the sled “around,” smaller than 600 units, enough time remains to complete, etc.)
  • the bumpers could be added to that to move pucks inside that area;
  • alternatively, find a blue puck or two and enclose in with a red puck [presuming the opponent is blue and I am red — the game always presents each player thus, doing translations as necessary] thus greying out all the above…

The difficulty I encountered first was that I can’t figure out how to calculate the path(s) for the sled — I think I would do thus now (pictures would help, but I am not going to work on that. If anything I’d be coding from hand-drawn diagrams…): Figure the smallest circle for the sled (radius 30, approximately). If the point fell inside that, you couldn’t move there (actually you could, it would just be a lot more work, maybe). Also, figure the minimum “approach” to the point/direction desired (basically, figure the smallest circle from the point reversing the direction), then, if there is a distance between, move on a line tangent to both circles

  • Alternative strategy would be just to move the sled in the largest possible circle and use the bumpers to push pucks into that area:
    • if there are opponent pucks inside that circle, get them out
    • make sure at least one of my own [red] pucks is inside that circle
    • bump as many grey pucks as possible into the circle in the time remaining

I may still, but even if not, I’m publishing my thoughts

Would you like to code a game?

January 15, 2010

ACM Queue magazine is offering an online programming competition” — and I’m interested!  The competition description is here.  Game rules are here.

I’m trying to develop a player (in Java) — I’ll post updates to this post.

Update Sat. 16 Jan. 2010:

(not in ‘blog order’ or I’d put this at the top).

So I have something working that doesn’t do much (spins the sled in a small circle); but I have one part done, and one mistake to report —

First, I implemented a Board object to encapsulate all the reading of the input and access of various components.  So the main loop looks like this:

public class Captur1 {
 public static void main(String[] args) {
 Scanner in = new Scanner( System.in );

 // Keep reading states until the game ends.
 int tnum = in.nextInt();
 Board b = null;
 while (tnum >= 0) {
   if (b == null)
     b = new Board(new Sled(new Point2D.Double(100.0, 400.0), 0.0));
   else
   {
     // System.err.println("next board");
     b = new Board(b);    // new board references previous board
   }
   b.readBoard(in);
   System.err.println("turn " + tnum + ":\n" + b);

   Response r = new Response();
   double dbg = r.changeSledDir(-0.3);
   System.err.println("new sled direction = " + dbg);

   r.sendResponse(System.out);
   // System.err.println("looping...");
   tnum = in.nextInt();

 } // end while
 System.err.println("end while.");
 }

Never mind the debugging, and the slightly odd start [if (b == null)] the first time, the main function is seven lines of code.  It will only grow slightly longer, according to literate coding, approximately thus:

Strategy strat = new SmartPlay();  // which implements a Strategy interface, or similar
if (strat.dependenciesChange(b) || strat.prevPlayComplete())
  strat.computePlay(b);
Response r = strat.setResponse(tnum /* perhaps */, b);

Of course, the real work needs to be done, but that’s it, initially — anyone want to help me come up with a strategy??

Secondly, I made one mistake.  I was storing the pucks in a TreeMap<Integer, Puck>

/**
 * Object to represent the game board itself; general operations should all go here.
 * Also, generic geometry operations (those 'inherited' from the sample).
 * @author GParks
 *
 */
public class Board {
 protected Board prevBoard = null;
 // contents of the board:
 //     two sleds,
 // four bumpters
 // n (112) pucks
 //
 protected Sled mySled, oppSled;
 protected Bumper myBumprs[], oppBumprs[];
 // *****
 // The tree of pucks is thus:
 //      - an Integer "key", which is the "proximity" to mySled
 //      - the puck itself, which has an index (it's order presented to us) 

 // http://java.sun.com/docs/books/tutorial/collections/interfaces/collection.html
 // http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeMap.html
 protected TreeMap<Integer, Puck> lstPucks;

Where the Integer key is (currently) an abbreviated computation of the “proximity” of the puck to the (previous) sled position — avoiding squaring and square root calcs. for actual distance, but because there may be more than one puck the same “proximity,” and because the keys must be unique, some pucks (okay, maybe a lot of them) weren’t being stored properly — I’m going to fix that next.  I think probably by not using that data structure, but some other sorted list…  (unless someone can give me a good reason to do otherwise, or a better method — I could compute proximity using the direction the sled is currently facing, also, giving a unique value to each puck, or at least more likely so…)