Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Inspired by this example of using d3js, I challenge you to create a canvas (or your language-of-choice equivalent) in which the mouse pointer trails will be displayed, with the following twist:

The Twist

You should not display the trails of where the mouse pointer was, but the "trails" of where it will (might) be in future.

You can do it by using either:

  1. A time machine, or

  2. Probabilistic estimations based on previous mouse movements

Assumptions

In case you didn't choose the time machine implementation, when the mouse does not move for more than threshold milliseconds, you can display none of the trails. (The threshold value is up to you to choose).

The cursor image is up to you and does not have to be the same of the OS's cursor (you can even draw a plain small circles or dots).

No evil input will be tested: You can assume the movements are smooth. 'Smooth' definition for this case is: if the mouse movements were a function over the x and y axis of the canvas - it would be a continuous function.

Winning

The valid answer with the least characters in code will win. In case of a tie - the one that was posted first will win.

EDIT: The valid answer with the most upvotes will win. In case of a tie - the one that was posted first will win. You can be creational on the implementation, or be precise with the prediction. I'm not the judge anymore, we all are :)

  • A valid answer must include a way for me to play with (test! I meant test), either on an online tool or on a freely-downloadable compiler/interpreter/runtime/etc.
share|improve this question
2  
I think this question might be better suited to a popularity contest than a code-golf, because it's fairly subjective as to what qualifies as a good enough prediction. I would recommend clarifying that or changing the tag. Nevertheless, looks fun. –  isaacg Aug 24 at 9:05
2  
You're right. I edited the question and changed the tag. –  Jacob Aug 24 at 9:11
    
Time for someone to implement machine learning algorithms! –  Ingo Bürk Aug 24 at 9:29
6  
For testing purposes, which models of time machine do you have access to? And may we use standard libraries to interface with them? –  Peter Taylor Aug 24 at 12:45
1  
Just a mathematician whining here: smooth != continuous. In fact wild spikey movement will still be continuous. –  CompuChip Aug 25 at 9:10

4 Answers 4

up vote 31 down vote accepted

Javascript

My program predicts the direction of the pointer by using the average of the angular change in direction of the last 20 mouse moves. It also uses the variance of the angular change to create a "cloud" of possible locations and directions of the pointer. The color of each pointer in the "cloud" is supposed to represent the likelihood of it being the new position of the mouse pointer, where darker colors represents a greater likelihood. The distance of the pointer cloud ahead of the mouse is calculated using the speed of mouse movement. It doesn't make the best predictions but it looks neat.

Here's a fiddle: http://jsfiddle.net/5hs64t7w/4/

Increasing the size of the pointer cloud is interesting to see. It can be set by changing the cloudSize variable on the first line of the program. Here is a fiddle with a cloud size of 10: http://jsfiddle.net/5hs64t7w/5/

I used these sources to get formulas for circular mean and variance:
Circular Mean: http://en.wikipedia.org/wiki/Circular_mean
Circular Variance: http://www.ebi.ac.uk/thornton-srv/software/PROCHECK/nmr_manual/man_cv.html

Here is the code if anyone is interested:

    var cloudSize = 3;

    var canvas = document.getElementById('canvas_element');
    var c = canvas.getContext('2d');
    var prevX = -1;
    var prevY = -1;
    var curX = -1;
    var curY = -1;
    var distance = 0;
    var direction = 0;

    function drawMouse(x, y, angle, gray){
        var grayVal = Math.round(gray*255);
        var grayString = "rgb(" + grayVal + "," + grayVal +"," + grayVal + ")";
        c.fillStyle = grayString;
        c.strokeStyle = grayString;
        c.lineWidth = 1;
        c.beginPath();
        c.moveTo(x, y);
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 + Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 + Math.PI/8.0));
        c.moveTo(x, y);
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 - Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 - Math.PI/8.0));
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 + Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 + Math.PI/8.0));
        c.stroke();
        c.fill();
        c.beginPath();
        c.moveTo(x, y);
        c.lineTo(x + 24*Math.cos(angle + Math.PI/2), y + 24*Math.sin(angle + Math.PI/2));
        c.stroke();
    }

    function sum(array){
        var s = 0.0;
        for(var i=0; i<array.length; i++){
            s += array[i];
        }
        return s;
    }

    var sins = [];
    var coss = [];
    var lengths = [];
    var times = [];
    var index = 0;
    var limit = 20;
    var variance = 0;
    var prevTime = new Date().getTime();
    function updateDistanceAndDirection(x, y){
        var angle = Math.atan2(prevY - curY, prevX - curX);
        sins[index] = Math.sin(angle);
        coss[index] = Math.cos(angle);
        lengths[index] = Math.sqrt((curX-prevX)*(curX-prevX) + (curY-prevY)*(curY-prevY));
        var time = new Date().getTime();
        times[index] = time - prevTime;

        variance = 1.0 - Math.sqrt(sum(coss)*sum(coss)+sum(sins)*sum(sins))/sins.length;

        direction = Math.atan2(1/sins.length*sum(sins),1/coss.length*sum(coss));
        var speed = sum(lengths)/(sum(times)/200);
        distance = Math.min(Math.max(40, speed), 100);
        prevTime = time;
        index = (index+1)%limit;
    }

    function drawMice(count){
        c.clearRect(0, 0, canvas.width, canvas.height);

        for(var i=count; i>=0; i--){
            var dir = direction + i*variance;
            drawMouse(curX - distance*Math.cos(dir), curY - distance*Math.sin(dir), dir - Math.PI/2, i/count);
            dir = direction - i*variance;
            drawMouse(curX - distance*Math.cos(dir), curY - distance*Math.sin(dir), dir - Math.PI/2, i/count);
        }
    }

    canvas.onmousemove = function (event) {
        curX = event.clientX;
        curY = event.clientY;

        updateDistanceAndDirection(curX, curY);

        drawMice(cloudSize);

        prevX = curX;
        prevY = curY;
    };
share|improve this answer
2  
Can you display a sequence of mouse pointer (with fixed orientation) instead of a pointer pointing to variable direction? I was expecting to see "mouse trails" but can't see any, haha –  justhalf Aug 25 at 1:37
    
Very nice, but isn't it more plausible that the pointer should go up in the future when it currently goes down? Imho, the program should do exactly the opposite so the it predicts the pointer stays on screen. –  Menno Gouw Aug 25 at 17:26
    
@MennoGouw its not perfect but its pretty damned good –  NimChimpsky Aug 25 at 18:11
    
@nimchimpsky Just saying the probability of the mouse going up is higher if the mouse currently goes down. The program itself is great. –  Menno Gouw Aug 26 at 4:49
    
Do you think it's also possible to use the usual human behavior for mouse handling ? Like circles, straight lines... These could be predicted even further in the future (calculating the radius of the circle after a couple mesures, and finishing the circle even before you drafted it) –  Saffron Aug 27 at 15:59

Vanilla Javascript

Just to get things started, here is a simple prediction based on two values. The last n mouse postions are memorized and kept in a queue, the prediction is a simple linear extrapolation of the first and last element in the queue.

This is just the prediction code, the full code including the demo can be seen in this fiddle:

function predict(trail) {
    var b = trail.pop(),
        a = trail[0],
        d = {
            x: b.x - a.x,
            y: b.y - a.y
        },
        m = Math.sqrt( d.x * d.x + d.y * d.y );

    d.x = 5 * d.x / m;
    d.y = 5 * d.y / m;

    var predictions = [];
    for(var i = 1; i <= 10; i++) {
        predictions.push({
            x: b.x + i * d.x,
            y: b.y + i * d.y
        });
    }

    return predictions;
}

The demo contains a comment in the prediction that allows you to instead use the last two elements in the queue for the prediction. Makes the result more "real-time", but also less "smooth".

If anyone wants to use the boilerplate work to implement a different prediction algorithm, feel free. It's not a lot of work anyway.

share|improve this answer
    
Can you display a mouse pointer instead of a line? I was expecting to see "mouse trails" but can't see any, haha –  justhalf Aug 25 at 1:36
    
The question says it doesn't have to be a cursor ;) –  Ingo Bürk Aug 25 at 3:43

Java

I decided to take the time machine approach. It turns out the key ingredient of a time machine is java.awt.Robot. My program lets you move your mouse around for 10 seconds. After the 10 seconds it goes back in time and recreates your mouse movement, while predicting it perfectly.

enter image description here

Here's the code:

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Robot;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.util.ArrayList;
import java.util.TimerTask;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;


public class TimeMachine extends JPanel implements MouseMotionListener {

    Timer timer;
    int time = 10;
    java.util.Timer taskTimer;
    ArrayList<Point> mousePoints;
    ArrayList<Long> times;
    Robot robot;
    int width, height;
    ArrayList<Point> drawMousePoints;

    public TimeMachine(){
        width = 500;
        height = 500;
        drawMousePoints = new ArrayList<Point>();

        robot = null;
        try{
            robot = new Robot();
        }
        catch(Exception e){
            System.out.println("The time machine malfunctioned... Reverting to 512 BC");
        }
        mousePoints = new ArrayList<Point>();
        times = new ArrayList<Long>();

        taskTimer = new java.util.Timer();

        ActionListener al = new ActionListener(){
            public void actionPerformed(ActionEvent e){
                time--;
                if(time == 0)
                    rewind();
                repaint();
            }
        };
        timer = new Timer(1000, al);
        start();
    }

    public void paint(Graphics g){
        g.clearRect(0, 0, width, height);
        g.drawString("Time Machine activiates in: " + time, 15, 50);
        for(int i=0; i<drawMousePoints.size(); i++){
            Point drawMousePoint = drawMousePoints.get(i);
            drawMouse(drawMousePoint.x-getLocationOnScreen().x, drawMousePoint.y-getLocationOnScreen().y, g, Color.BLACK, Color.LIGHT_GRAY, (double)i/drawMousePoints.size());
        }
    }

    public void drawMouse(int x, int y, Graphics g, Color line, Color fill, double alpha){
        Graphics2D g2d = (Graphics2D)g;
        g2d.setColor(new Color(fill.getRed(), fill.getGreen(), fill.getBlue(), (int)Math.max(Math.min(alpha*255, 255), 0)));
        g2d.fillPolygon(new int[]{x, x, x+4, x+8, x+10, x+7, x+12}, new int[]{y, y+16, y+13, y+20, y+19, y+12, y+12}, 7);

        g2d.setColor(new Color(line.getRed(), line.getGreen(), line.getBlue(), (int)Math.max(Math.min(alpha*255, 255), 0)));
        g2d.drawLine(x, y, x, y + 16);
        g2d.drawLine(x, y+16, x+4, y+13);
        g2d.drawLine(x+4, y+13, x+8, y+20);
        g2d.drawLine(x+8, y+20, x+10, y+19);
        g2d.drawLine(x+10, y+19, x+7, y+12);
        g2d.drawLine(x+7, y+12, x+12, y+12);
        g2d.drawLine(x+12, y+12, x, y);
    }

    public void start(){
        timer.start();
        prevTime = System.currentTimeMillis();
        mousePoints.clear();
    }

    public void rewind(){
        timer.stop();
        long timeSum = 0;
        for(int i=0; i<times.size(); i++){
            timeSum += times.get(0);
            final boolean done = i == times.size()-1;
            taskTimer.schedule(new TimerTask(){
                public void run(){
                    Point point = mousePoints.remove(0);
                    drawMousePoints.clear();
                    drawMousePoints.addAll(mousePoints.subList(0, Math.min(mousePoints.size(), 30)));
                    robot.mouseMove(point.x, point.y);
                    repaint();
                    if(done)
                        System.exit(0);
                }
            }, timeSum);
        }
    }

    long prevTime = 0;
    public void record(MouseEvent m){
        if(timer.isRunning()){
            long time = System.currentTimeMillis();
            mousePoints.add(new Point(m.getXOnScreen(), m.getYOnScreen()));
            times.add((time-prevTime)/10);
            prevTime = time;
        }
    }

    public static void main(String[] args){

        TimeMachine timeMachine = new TimeMachine();

        JFrame frame = new JFrame("Time Machine");
        frame.setSize(timeMachine.width, timeMachine.height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
        frame.addMouseMotionListener(timeMachine);

        frame.add(timeMachine);
    }

    public void mouseDragged(MouseEvent m) {
        record(m);
    }

    public void mouseMoved(MouseEvent m) {
        record(m);
    }

}
share|improve this answer
    
Code slightly optimized by Netbeans (got rid of the warnings): pastebin.com/E57LZ4zY –  Mew Aug 25 at 7:53

Javascript

The past is the best prediction for the future - me, and propably someone else too

My solution is very simple. First, here is the >>> Fiddle! <<<

All it does is shifting the past trail, so it looks like the future trail. Basically no Math is involved (I Know, pretty boring). You can easily see the errors, especially when moving the cursor in circles. That's why I made the trail so short ;)

The code:

<!DOCTYPE html>
<html>
    <head>
        <style type="text/css">
            .cursor {
                width: 13px;
                height: 23px;
                position: absolute;
                background-image: url(http://speedcube.de/images/cursor.png);
            }
        </style>
        <script type="text/javascript">

            var x, y;
            window.onmousemove = function(e) {x=e.clientX; y=e.clientY;}

            var p = [0,0,0,0,0,0,0,0,0,0];
            window.setInterval(function() {
                p.shift();
                p.push([x, y]);
                var diff = [x-p[0][0], y-p[0][1]];
                for (var i = 0; i < 10; i++) {
                    var e = document.getElementById(i);
                    e.style.left = (p[9-i][0]+diff[0])+"px";
                    e.style.top = (p[9-i][1]+diff[1])+"px";
                }
            }, 10);

        </script>
    </head>
    <body>
    <div id="0" class="cursor"></div>
    <div id="1" class="cursor"></div>
    <div id="2" class="cursor"></div>
    <div id="3" class="cursor"></div>
    <div id="4" class="cursor"></div>
    <div id="5" class="cursor"></div>
    <div id="6" class="cursor"></div>
    <div id="7" class="cursor"></div>
    <div id="8" class="cursor"></div>
    <div id="9" class="cursor"></div>
    </body>
</html>
share|improve this answer
    
haha I just had a look at the date. Whatever, I like it –  Felk Sep 12 at 16:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.