Two Guys Arguing

tour de mario – jumping

Posted in ai, challenge, java, mario by youngnh on 08.10.09

My co-blogger Ben and I are working on an entry for the Mario AI Competition 2009. The idea is to develop a Java program that simulates button presses to guide Mario through randomly generated levels of increasing difficulty. The competition is aimed at exploring Artificial Intelligence methods in gaming, but before Ben and I can even get to that, I think a short tour of the code we will be working with is in order.

Jumping is key in Mario. Maybe more precisely, landing is key. Controlling where you land will stomp an enemy or clear a gap. Jumping is easy, landing is hard.

Since this is so integral, let’s take a look at the code that makes Mario tick.

The class ch.idsia.mario.engine.sprites.Mario controls Mario’s behavior.

The tick() method of Mario’s superclass, Sprite is called once for every frame of the game, 24/sec. tick() is pretty simple, it just calls move(), which Mario happens to implement.

The move() method has a lot of code in it — 224 lines — but at it’s core, it just sets the xa and ya variables — x-acceleration and y-acceleration — and then uses them to increment Mario’s current x and y position variables.

move() starts on line 156, but doesn’t start doing anything we’re interested in until line 211:

        float sideWaysSpeed = keys[KEY_SPEED] ? 1.2f : 0.6f;

Mario moves horizontally at a rate 0.6 per frame at normal speed and 1.2 when the SPEED key is pressed.

The jumping code starts on line 234. I’ve left out the conditions we don’t care about:

if(keys[KEY_JUMP] || ...) {
    if(onGround && mayJump) {
        xJumpSpeed = 0;
        yJumpSpeed = -1.9f;
        jumpTime = 7;
        ya = jumpTime * yJumpSpeed;
        onGround = false;
        sliding = false;
    else if(jumpTime > 0) {
        xa += xJumpSpeed;
        ya = jumpTime * yJumpSpeed;

This is the heart of the jump. jumpTime is a frame counter variable, and a jump lasts 7 frames. I’m not positive, but I think that the y-origin is in the upper right of the screen, hence the negative yJumpSpeed. After 7 frames, jumpTime is reset to 0.

There are extra bits of code that limit Mario’s maximum acceleration to 8, cut Mario’s xa and ya to 85% of their value and every frame that Mario isn’t on the ground his y-acceleration is is decreased by 3.

        ya *= 0.85f;        
        if (!onGround) {
            ya += 3;

But it’s enough to figure out where you’re going to land.

I made a couple of mistakes, which are crossed out above, and besides the mention of sideWaysSpeed I didn’t mention anything about horizontal speeds. As you can see above, when you are in the air xJumpSpeed starts out as 0 and you don’t gain any acceleration from it for the duration of your jump. The code that sets your horizontal acceleration regardless of whether you are on the ground or not is at line 288:

        if (keys[KEY_RIGHT] && !ducking) {
            if (facing == -1) sliding = false;
            xa += sideWaysSpeed;
            if (jumpTime >= 0) facing = 1;

which merely sets your acceleration depending on what direction you are pressing.

Tagged with: , , ,

Long Walk After the Sun – Challenge

Posted in challenge by benjaminplee on 05.28.09

This question popped into my head the other day out of nowhere but sounded really interesting.  It may involve, but is not limited to, programming, geometry, 3d data visualization and astronomy.

Setup: At 12:00 AM, January 1st, 2009 a man is standing in his front yard.  That morning, as soon as the sun breaches the horizon, he begins walking at a constant rate in the direction of the sun.  He walked all day, always in the direction of the sun, until nightfall when he stops and sleeps.  He does this every day for an entire year.  As the sun climbs higher in the sky each day, he always walks in the direction of the sun relative to directly above his head (assume he has a magical sundial that is very accurate).  Oh, and he can walk on water and through mountains (terrain doesn’t slow him down nor stop his motion).

Challenge: Given he lives in downtown St. Louis, Missouri, and that he walks at a constant rate of 3 miles/hour, where will the man be sleeping on December 31st, 2009 after the sun has set?

Bonus points for solutions that can compute his final location based on an arbitrary starting location and/or walking speed.  Averaged sun rise and sun set times can be used, but using some historical monthly/daily averages would be even better.  Also the changing location of the sun’s arc during the year could/should be taken into consideration.  I can imagine this is a fairly hard problem, but it seems doable with some effort.  I will make an honest attempt at solving it myself, but if anyone is up to the challege, please post your thoughts and findings.  I found the problem interesting b/c several “easy” answers jump out initially but without the math, I can’t be sure which one if any are true (will he end up in the same place?  somewhere near the equator? at a pole?  go in circles?

my word shift solution

Posted in challenge by youngnh on 04.14.09

I’m a bit obsessed with the unix programs tr, uniq, sort and paste after reading Unix for Poets in college, and Ben’s problem falls very nicely into the category of problems that these programs solve effortlessly.

The basic algorithm I decided to implement is plain-english simple: take a dictionary of words, transform all of them by shifting their characters and then removing any words that are no longer in that same dictionary.

Step 1: Move characters to the right. The unix program tr does nothing but this:

tr 'qwertyuiop' 'wertyuiop['

will translate just the first row of characters

tr 'qwertyuiopasdfghjklzxcvbnm1234567890' 'wertyuiop[sdfghjkl;xcvbnm,234567890-'

Each letter in tr‘s first argument gets replaced with the corresponding letter in the second argument.  The above command will shift all three rows of letters and the top row of number keys.  I’m going to write a truncated version for the rest of the post to save me some typing.

Step 2: Remove any words that aren’t in the dictionary.  For this step, I used cat to append the list of actual words to our list of translated words, like so:

cat dict | tr 'qwerty' 'wertyu' | cat - dict

Once you have a big long list of words and non-words, you want to sort them all which has the effect of putting any actual words created by shifting right next to a real word from the dictionary file.  The program uniq has a flag to print only duplicates that appear in its input.

cat dict | tr 'qwerty' 'wertyu' | cat - dict | sort | uniq -d

That’s it, go make yourself a drink.

Well….its kinda hard to look at that list and be confident that our little unix one-liner did its job.  (bb? is that even a word?) It would help a great deal if we could see what original hand positions were translated to form these new words. In other words, what words did we think we were typing?  To do this, I’d like to take our shifted words file, shift them back and then display both lists side by side.

To redirect output to a file, we use >.  To shift back we’ll use tr again and finally for the side by side display we’ll use paste.  You can swap the arguments to tr and that will take care of the leftward shift.
Our full program then becomes:

cat dict | tr 'qwerty' 'wertyu' | cat - dict | sort | uniq -d > shifted.txt
cat shifted.txt | tr 'wertyu' 'qwerty' | paste - shifted.txt

Simple. On my modest machine, this runs over a 120K dictionary just under 3 seconds. Some of my favorites:

sweet -> derry
waxier -> escort
awed -> serf
dye -> fur
gust -> hidy
rust -> tidy
tyer -> yurt

Tagged with:

Wrong Word, Right Key Strokes Challenge

Posted in challenge by benjaminplee on 04.07.09

Back in the metaphorical “day” I remember an incident where I tried to quickly type a message to someone and only after hitting Enter, noticed that in my haste my fingers were not lined up in their normal position.  The strange thing was that despite my fingers being off my a key (I can’t remember which direction), I had succeeded in typing a real word.  Unfortunately I can’t remember what the word was (intended or accidental).

Therefore, I put forth this challenge write a script which based on a English word list and the standard QWERTY key layout, find all of the real words that can be accidentally typed if another real word is typed with each keystroke offset by one key.  (e.g. if the word SAD was typed with your hands shifter right one key, it would come out DSF … which isn’t a word but you get the idea).  Key offset should be only one key distance, but I will leave it up to the implementer to decide what to do about moving up and down.

I fully intend to write this up at some point, but just haven’t had the time yet.  If anyone wants to take a stab at it, please let me know.

FYI … the National Puzzlers’ League has some nice word lists under “Solving Tools of the NPL”.