Friday, December 30, 2011

Code Snippets

This post has moved to blog.stevearc.com/2011/12/30/code-snippets.html

11 comments:

  1. What you have written here is great!! thanks for taking the time to write it.

    Only one small issue however ;)

    There is (I think) a bug in your FastIterableLocSet Code. I'll not say where on the off chance it was deliberate.

    ReplyDelete
    Replies
    1. Yup, I forgot to put "size = 0" in the clear() method. Good catch! Or did you spot something else?

      Delete
  2. Yep, that's it.
    I have shamelessly copied it, and when you call clear() followed by getKeys() a little later, you get all sorts of interesting things happen :)

    ReplyDelete
    Replies
    1. Sorry about that. Even though we wrote that method, I don't think we actually used it anywhere. So we never noticed the bug.

      Delete
  3. I like a lot of the individual components, but I don't quite understand where some code plays in the scheme of things. Like you run your post yield, that only seems to deal with sense code. Then you consider a state change based on changed objectives. But after that point, I get lost for where things should go. Like, for example, the move code that deals with more than just moving itself,when does this get called? Trying to chart it out gets a bit annoying since on one hand, post yield has this custom behavior whereas move takes a more one sized fits all approach. On top of that, I find it had to tell if certain functionality like messaging and mapping is in their own class, or implemented in info cache. I guess I'm just saying, that while I understand the components and brilliance behind them, I'm just not getting an idea of program flow. Clarification would be great but regardless it is really good stuff and probably the best battlecode resource out there.

    ReplyDelete
    Replies
    1. Yeah, I didn't really chart out the overall structure and flow of the code at all. It was kind of intentional. Writing and diagramming up the overall structure was just...a bit daunting. And by the end of the postmortem I was feeling lazy, so I just put up these code snippets instead. Since there's interest, I may at some point get around to doing that properly. Or maybe I should just open source my team's player and let people figure it out on their own...

      Delete
  4. Hmm, how do you know that code# of '^' is not a valid MapLocation coordinate?
    If you ever get a MapLocation with one coordinates of 94 that would completely throw off the FastIterableLocSet would't it?

    ReplyDelete
    Replies
    1. You are absolutely right. And in fact, at one point I had code that would sense your starting MapLocation and detect if such a collision was possible. If so, it would encode the MapLocation integer *plus* a constant offset. I later took that code out for performance reasons. The reason why I still wasn't worried about it is that there are 2^32 values for an integer. If the maximum board width is 60, then there are 121 possible random starting values that will cause such a collision (94-60 through 94+60, inclusive). Factor in 121 more for the height, and you have 121/2^32 + 121/2^32, or 0.0000056% chance of that happening. Someone should check my math because I didn't do so well in 18.440.

      Delete
  5. That makes sense. Thanks.

    Also could you explain why you said indexOf in StringBuilder is constant cost? Does it build a hash table for all possible substrings. That seems way too expensive. Shouldn't it be linear cost (in length of the string)? Or is there some bytecode magic that I am not aware of? You made the good point that operations expensive in time may not be proportionally so in bytecodes.

    ReplyDelete
    Replies
    1. If you look inside of MethodCosts.txt, you will see that StringBuilder.indexOf() costs 20 bytecode, as set by the devs. And this is why optimizing your code for battlecode is sometimes really stupid. Because you end up building a hash table with StringBuilders that's "faster" than an actual hash table.

      Delete
    2. Wow! Thanks. May come handy next year. :-)

      Delete