Archive for May, 2010
Determining if a point is in a 2D triangle
For this one I needed to read in a file of a ton of triangles and then process them to determine if a point is contained in the triangle. I thought of a couple different algorithms to solve this but ultimately decided to use the cross product between the generated segments to determine if it is contained. I had been needing a basic File class for reading and writing files, so I set one of those up, then I moved to the 2D integer vector class that I used for the math needed to solve it. The parsing is very basic I just scan for the integers, then i sorted the points from left to right so I knew how to process the triangle.
Anyway check it out and leave some feedback.
A lot of the problems that I keep attempting on projecteuler.net require more bits than than unsigned __int64, so I started thinking about making my own LargeInt class. For the particular problem I’m solving I need the following operators.
I need to be able to have numbers of nearly infinite size with fast indexing to perform operations on. I decided to utilize the vector class in the Standard Template Library, but you can pretty much use any dynamic array. (more…)
Given a triangle filled with values find the maximum sum that can be achieved by traversing from top to bottom.
I spent a bit of time thinking about the best way to accomplish this since on Project Euler one of the triangles is 100 lines in the text file. I thought about an algorithm that basically traverses the largest branch in the tree, but that doesn’t always yield the maximum sum. So then I realized that I don’t really need to know the actual values of the triangle, only the sum of up to that point. So I basically came up with a way that calculates the maximum value at a point in the triangle by starting from the top and working my way down. So for example A triangle like this: (more…)
I’ve seen a lot of implementations of array based binary heaps, and really only talk about tree based implementations. Granted the array based versions that use dynamic arrays are probably better for most things since the average cost of insertion is of constant time O(1), and sorting the array based versions is much easier. With that said I wanted to attempt a tree based version for some comparisons. One thing to note is this a max based binary heap meaning the largest value will always be at the root. I got some suggestions for speeding up my insertions, which turned out to be highly needed. I’m sure theres a few ways I can improve the insertion algorithm which runs at O(log(n)) instead of the O(1) that the array based insertions take. I’ve tested this class with over 10 million inserts and removals of varying types, and it gets the job done, but I do see that the array based implementations are superior.
Check out the code here
Rise of the Eldrazi is the newest set in the trading card game Magic the Gathering. I made it to the pre-release at midnight to find about 80 other people there. After playing until 4:00 AM I ended up dropping with a record of 2-1. I hadn’t lost a match all night until round 3, where I played someone that had an amazing deck. I still feel I could of made top 8 that night, but seeing as it was already eating into my weekend I had to call it a night.
I am very competitive at every game I play, but lately I’ve found EDH to be a nice break. It gives me a chance to play crazy cards that I would never be able to play in Standard. I have been playing a slightly modified version of EDH at lunch at work for the last year. The modifications we made were basically so we could finish a game in our lunch break. We all start with 20 life, with no general damage rules. After the pre-release I had to update my mono-red EDH deck to now a Red/Green Rosheen the meander deck. I put in a copy of all the big Eldrazi’s including Emrakul himself. I’ve been able to hard cast him in 3 different games, and I still lost one of those by getting overrun by tokens. Sometimes I feel like the games go until someone casts Emrakul, as we all run a copy now, but I don’t think it ruins the game in anyway as some people predicted. So far my favorite card for EDH from the ROE set has been Momentous Fall, which is a card that makes you sacrifice a creature, and you draw cards equal to its power, and gain life equal to its toughness. That card has saved my life so many times! In my last game I had 6 mana and Rosheen on the table. I was being attacked by an opponent for 50 damage or something insane. He was at one life and I had no burn spells in my hand. I paid 4 to sacrifice my 16/16 dragon that was equipped to a Sigil of Distinction. I was lucky enough to draw into a comet storm and was able to tap Rosheen for 4 and my remaining two red lands to kill my opponent and win the game the following turn.
I can’t wait to see what the next set has in store.
I’m starting a new section on my website for personal posts. Be on the look out for everything from crazy rants to video game reviews.
Shipped on Playstation 3
This is the most recent game that I shipped. This game was one of the most intense projects I worked on. With a very short development time, we had to make decisions and stick with them. The end result is a game that is a complete blast to play. This game is very much like the old Ninja Turtle games I use to play. I got to work with an amazing team of people including an new employee to Frozen Codebase a Call of Duty lead designer. I was able to learn a lot from him in the time we worked together. I managed the combat system, the camera, all PS3 TRC’s, player controls, and animations.
Shipped on Xbox 360
I primarily worked on the UI and game optimizations. This game used the Torque 360 engine, the same engine that powered Marble Blast Ultra for XBLA. I learned a lot while working on this project. Theres also a PC version of this game.
I worked on some of the AI for this game, along with the audio build system. I think this is a fun budget title, and I enjoyed working on it.
Shipped on Xbox 360
I worked on this game for about 10 months, where I mostly did player controls, camera, combat, Xbox 360 TCR’s, network code, leaderboards, matchmaking and a progressive lobby. Build nights where we’d get to play this game were always a blast. As with every game theres a million things you can’t quite get in before the game ships, but overall I am super proud of the work I did on this title.