Q:

Java - Why does my game loop stutter randomly?

I'm a beginning game developer and I'm trying to make a game in Java, but for some reason, it keeps stuttering at random times. I believe what I'm experiencing could also be called microstuttering. 
At first, I though my framerate of 60 fps was the problem, so I've tried setting it to 30 and 120. In both cases, however, did not only the microstutters persist, but the player also started moving shakingly, as if it were moving back and forth while moving in one direction, the same way pigeons move their heads when walking.
Next, I've tried changing my game loop. I've read that sleep  based game loops are very unreliable, so I changed it to a timer based game loop. Unfortunately, that didn't work either. The microstutters still persisted, the player still moved shakingly and for some reason, my framerate also seemed to have halved.
I've been looking into this for a while now, but I haven't been able to fix the problem. Is there anyone with more experience who could help me, please?
Here's my game class for the sleep based loop:
package collisiondetection;

import java.applet.Applet;
import java.awt.Color;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.io.FileNotFoundException;
import java.net.URL;

@SuppressWarnings("serial")
public class Game extends Applet implements KeyListener, Runnable {

    final boolean DEBUG = true;

    public static int health = 13;

    public static Player player;
    public static Terrain terrain;

    public boolean running = true;

    public Graphics graphics;
    public Line line;
    public Image background, image;
    public URL base;

    @Override
    public void init() {
        setSize(1280, 720);
        setBackground(Color.WHITE);
        setFocusable(true);
        addKeyListener(this);
        Frame frame = (Frame) this.getParent().getParent();
        frame.setTitle("Collision Detection");

        base = getDocumentBase();

        background = getImage(base, "data/background.png");
    }

    @Override
    public void start() {
        player = new Player();

        try {
            terrain = new Terrain();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        Thread thread = new Thread(this);
        thread.start();
    }

    @Override
    public void stop() {

    }

    @Override
    public void destroy() {

    }

    // fix lag
    @Override
    public void run() {
        while (running) {
            if (health <= 0)
                running = false;

            player.update();
            terrain.update();
            repaint();

            try {
                Thread.sleep(1000 / 60);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    @Override
    public void update(Graphics g) {
        if (image == null) {
            image = createImage(this.getWidth(), this.getHeight());
            graphics = image.getGraphics();
        }

        graphics.setColor(getBackground());
        graphics.fillRect(0, 0, getWidth(), getHeight());
        graphics.setColor(getForeground());
        paint(graphics);

        g.drawImage(image, 0, 0, this);
    }

    @Override
    public void paint(Graphics g) {

        if (running) {
            g.drawImage(background, 0, 0, this);
        } else {
            // handle death
        }

        if (DEBUG) {
            g.setColor(Color.BLUE);
            g.fillRect(player.hitbox.x, player.hitbox.y, player.hitbox.width, player.hitbox.height);

            g.setColor(Color.RED);
            for (int i = 0; i < terrain.lines.size(); i++) {
                line = terrain.lines.get(i);
                g.drawLine((int) line.line.getX1(), (int) line.line.getY1(), (int) line.line.getX2(),
                        (int) line.line.getY2());
            }
        }

    }

    @Override
    public void keyPressed(KeyEvent e) {
        switch (e.getKeyCode()) {
        case KeyEvent.VK_LEFT:
            player.moveLeft();
            break;

        case KeyEvent.VK_RIGHT:
            player.moveRight();
            break;

        case KeyEvent.VK_UP:
            player.jump();
            break;
        }
    }

    @Override
    public void keyReleased(KeyEvent e) {
        switch (e.getKeyCode()) {
        case KeyEvent.VK_LEFT:
            player.stopLeft();
            break;

        case KeyEvent.VK_RIGHT:
            player.stopRight();
            break;
        }
    }

    @Override
    public void keyTyped(KeyEvent e) {

    }

    public static Player getPlayer() {
        return player;
    }

    public static Terrain getTerrain() {
        return terrain;
    }

}

And my game class for the timer based loop:
package collisiondetection;

import java.applet.Applet;
import java.awt.Color;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.io.FileNotFoundException;
import java.net.URL;
import java.util.Timer;
import java.util.TimerTask;

@SuppressWarnings("serial")
public class Game extends Applet implements KeyListener {

    final boolean DEBUG = true;

    public static int health = 13;

    public static Player player;
    public static Terrain terrain;

    public boolean running = true;

    public Graphics graphics;
    public Line line;
    public Image background, image;
    public Timer timer;
    public URL base;

    @Override
    public void init() {
        setSize(1280, 720);
        setBackground(Color.WHITE);
        setFocusable(true);
        addKeyListener(this);
        Frame frame = (Frame) this.getParent().getParent();
        frame.setTitle("Collision Detection");

        base = getDocumentBase();

        background = getImage(base, "data/background.png");
    }

    @Override
    public void start() {
        player = new Player();

        try {
            terrain = new Terrain();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        timer = new Timer();
        timer.schedule(new TimerTask() {

            // fix lag
            @Override
            public void run() {
                if (health <= 0) {
                    running = false;
                    timer.cancel();
                }

                player.update();
                terrain.update();
                repaint();

            }

        }, 0, (long) (1000.0 / 60.0));
    }

    @Override
    public void stop() {

    }

    @Override
    public void destroy() {

    }

    @Override
    public void update(Graphics g) {
        if (image == null) {
            image = createImage(this.getWidth(), this.getHeight());
            graphics = image.getGraphics();
        }

        graphics.setColor(getBackground());
        graphics.fillRect(0, 0, getWidth(), getHeight());
        graphics.setColor(getForeground());
        paint(graphics);

        g.drawImage(image, 0, 0, this);
    }

    @Override
    public void paint(Graphics g) {

        if (running) {
            g.drawImage(background, 0, 0, this);
        } else {
            // handle death
        }

        if (DEBUG) {
            g.setColor(Color.BLUE);
            g.fillRect(player.hitbox.x, player.hitbox.y, player.hitbox.width, player.hitbox.height);

            g.setColor(Color.RED);
            for (int i = 0; i < terrain.lines.size(); i++) {
                line = terrain.lines.get(i);
                g.drawLine((int) line.line.getX1(), (int) line.line.getY1(), (int) line.line.getX2(),
                        (int) line.line.getY2());
            }
        }

    }

    @Override
    public void keyPressed(KeyEvent e) {
        switch (e.getKeyCode()) {
        case KeyEvent.VK_LEFT:
            player.moveLeft();
            break;

        case KeyEvent.VK_RIGHT:
            player.moveRight();
            break;

        case KeyEvent.VK_UP:
            player.jump();
            break;
        }
    }

    @Override
    public void keyReleased(KeyEvent e) {
        switch (e.getKeyCode()) {
        case KeyEvent.VK_LEFT:
            player.stopLeft();
            break;

        case KeyEvent.VK_RIGHT:
            player.stopRight();
            break;
        }
    }

    @Override
    public void keyTyped(KeyEvent e) {

    }

    public static Player getPlayer() {
        return player;
    }

    public static Terrain getTerrain() {
        return terrain;
    }

}

If you want to import the game in Eclipse to see how it works for yourself, you can download both the sleep and timer based projects from here.
Thanks in advance.

A:

Java is quite not controllable enough to allow you to enforce a constant framerate. The best you can do is try to make each run() begin on a 1/60 second boundary. Your Timer method might be as good as you're going to get. Even so, it's making a really big assumption, which is that your game's process will be running exactly when that 1/60 second interval ends. That may not happen, and so you'll need to deal with the cases where it has not.
To deal with this, there are two standard methods.
Method 1:
Set a fixed "update rate", say 1/60 second. At the start of your run() method, figure how much time passed since the last run(). Divide that time by the update rate, and update that many times. The update rate probably will not divide the time change evenly. If you want to interpolate (note: I know, you said you don't want to. Still...) you update one more time, and then interpolate between the two positions. If you don't want to interpolate, you store the amount of extra time and add it into the next frame's time change.
Method 2:
At the start of your run() method, calculate how much time passed since the last run(). In your game's update code, accelerate and move objects in proportion to the time change.

Method 1 is particularly useful for fast-action games where precision in movement and physics is an absolute necessity. Method 2 is far simpler, and in many cases will behave well enough (or exactly the same as method 1) in practice.
[Note: The Thread.sleep() method you posted isn't quite correct, because it sleeps for 1/60 second after updating the game. This is adding 1/60 second to the amount of time that the frame already took to run. You should be subtracting the time it took to run the update code from 1/60, and sleeping for that amount of time.]

