Velocity vector approximation in integers for aiming

.block

license: mit

README.md

Velocity vector approximation in integers for aiming.

Assumptions:

You have very stupid CPU, and it can't do too much. Or, you aiming for speed. You want to find out velocity vector of length V that aims from starting point, into destination point. All calculations in integers, thus only approximation is possible. We working in 2D. Length of velocity we want is fixed. It's constant in program.

Input: two points source = (x1, x2) destination = (y1, y2)
Output: vector (vx, vy) which length is close to V, and aiming from source to destination.

Rejected Ideas

Straight ahead rejected: all ideas with roots or inverse roots, because it anyway require multiplication. Also rejected following:

1. Split whole range of possible dx, dy into WxH blocks, where W and H are powers of two.
2. Precalculate all vectors aiming to corresponding blocks using modern machine.
3. When velocity is need, just select appropriate block using division by W and H, and read velocity from table. In my task: it would take space. Not much but I want to avoid that. Also, precision is not good.

Idea Draft

Maybe you've seen cannons in old games shoots in eight directions: four alighed to axis, and four diagonals. Lets think a bit about it. How is it done?

It should be done making virtual eight regions around cannon, and selecting velocity of bullet according to region. First question: what does the region looks like?

Intuitively it's easy to figure out that region of diagonal is all points that is closer to diagonal than axis. Thus borders of the regions is defined with equation where distance between diagonal and axis is same:

(x - y)/sqrt(2) = y

There is trouble for calculation it straight forward. Division by square root is pain.

If you rearrange you'll find out that slope angle is pi/8, because this line by difinition is bisection of pi/4 angle. Thus, slope itself is tg(pi/8) = 0.41421... Notice it's kinda close to 0.5 = 1/2. So, if aiming vector has angle with tg(angle) >= 1/2 then it's closer to diagonaly for sure. And if tg(angle) < 1/2 then it's either closer to axis, or in range [tg(pi/8), 1/2] we have error. But it's fine.

How to implement this approximated version? Just use definition of tg(). It is length of opposite side devided by length of adjacent side. y/x in our case. Thus, tg >= 0.5 if y/x = tg >= 0.5. Or y >= 0.5 x. So, for one quarter of plane we have:

if (y < x/2)
  closer_to_x_axis;
else if (x < y/2)
  closer_to_y_axis;
else
  closer_to_diagonal;

And all other quarters of plane is processed in same way but with preparation: invert x, and y if they are negative, and remember what was inverted. Then postprocess: invert velocity in same way after detection what line is closer. In result, we have eight possible directions of velocity.

Proposition

Extend this idea by adding new directions.

• First, notice that lines with slope 1/4 and 3/4 are splitting regions rougly equal.
• Then, notice that 1/2 is 2/4.
• Step a bit further: notice that slopes i/8 where i in range [0, 8] produce regions which roughly equal too. In short: find i/8 slope closest to direction vector, and use i as index from premade table. This means:

i/8 ~ tg(angle) = y/x
x*i/8 ~ y

Algorithm:

0. Split plane using i/8 slopes, and prebuild direction vectors for that regions using modern machine / programming language.
1. Remember signs which should be produced by subtraction in analytical math x2-x1, and y2-y1 before actual subtraction using comparison of corresponded values. This is need only in case if result can be stored only by unsigned integer (as in my case). Otherwise remember signs of result of subtraction at step 2.
2. Subtract: dx = x2 - x1; dy = y2 - y1
3. Invert those which analytical result should be negative. Now dx, dy is positive. Or at least treat it so.
4. If dx <= dy then swap. It's to make (dx, dy) placed in triangle of quarter of plane. Remember did you swap it.
5. Set dx to be dx/8 from now on. From now on we calculate angle, which is in range [0, 7] inclusive.
6. If dx is equal to zero, then source point and destination point is too close, and all we can do is set angle to zero.
7. Else find first slope i/8 which is higher than slope of (dx*8, dy). Notice that we previously devided dx by 8. This means that dy/(dx*8) < i/8 or dy < dx*8*i/8 = dx*i. Then angle = i - 1
8. Now ensure that angle is in range [0, 7] inclusive, if outside bring it back in range.
9. Retrive vx, vy from table generated at step 0 using angle.
10. If we did swap dx, dy at step 4, then swap vx, vy.
11. Invert vx, vy according to saved signs from step 1.
12. Return vx, vy as result of algorithm.

Check this graph here

Features:

• 8*8 = 64 directions. Optionaly you can change 8 into 16 or higher power of two.
• Only add, sub and division by powers of two.
• Only integers.
• Almost no memory overhead.

Demo Features

• Pan & Drag + Zoom. Everyone likes zoom.
• Velocity vectors. Blue - using floating point arithmetic. Orange - using proposed algorithm.
• Velocity selection.
• Snap to grid of integer coordinates.

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.axis line {
	fill: none;
	stroke: #ddd;
	shape-rendering: crispEdges;
	vector-effect: non-scaling-stroke;
}

</style>
<p style="position:fixed">
	<label for="velocity" style="display: inline-block; width: 240px; text-align: right">
		velocity = 
	</label>
	<input type="number" min="0.01" max="256" step="1" value="20" id="velocity">
	<label for="snap">
		snap to grid 
	</label>
	<input type="checkbox" id="snap">
	<span id="info"> </span>
</p>
<svg width="960" height="500"></svg>
<script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script>
var radius = 2;
var velocity = 20;

var c1 = {x: 100, y: 0, r: radius, color: "orange"},
    c2 = {x: 150, y: 50, r: radius, color: "blue"};

var a_scale = 0.5;

var v1 = {x1: 0, y1: 0, x2: 0, y2: 0, color: "orange"};
	v2 = {x1: 0, y1: 0, x2: 0, y2: 0, color: "blue"};

var vx = [];
var vy = [];

function getangle(x, y)
{
	var tx = Math.floor(x / 8);
	if (tx == 0)
		return 0;
	var a = 0;
	var na;
	var r = 0;
	while (true)
	{
		na = a + tx;
		if (na >= y)//((int(r+1)*int(x))/8 > y)
			break;
		a = na;
		++r;
	}
	if (r > 7)
		r = 7;
	return r;
}

function getv(a, b)
{
	var sign1 = false;
	var sign2 = false;
	var sign3 = false;
	var dx, dy;
	dx = Math.round(b.x) - Math.round(a.x);
	if (Math.round(b.x) < Math.round(a.x))
	{   // abs & save sign
		sign1 = true;
		dx = -dx;
	}
	dy = Math.round(b.y) - Math.round(a.y);
	if (Math.round(b.y) < Math.round(a.y))
	{   // abs & save sign
		sign2 = true;
		dy = -dy;
	}
	if (dx <= dy)
	{   // swap
		var tmp = dy;
		dy = dx;
		dx = tmp;
		sign3 = true;
	}
	var angle = getangle(dx, dy);
	dx = vx[angle];
	dy = vy[angle];
	if (sign3)
	{   // swap
		var tmp = dy;
		dy = dx;
		dx = tmp;
	}
	if (sign1)
		dx = -dx;
	if (sign2)
		dy = -dy;
	return {x:dx, y:dy};
}

function build()
{
	for (var i=0; i<8; ++i)
	{
		var x1 = 1.0;
		var y1 = i/8.0;
		var x2 = 1.0;
		var y2 = (i+1)/8.0;
		var l = Math.sqrt(x1*x1+y1*y1);
		x1 /= l;
		y1 /= l;
		l = Math.sqrt(x2*x2+y2*y2);
		x2 /= l;
		y2 /= l;
		var x = (x1+x2)/2.0;
		var y = (y1+y2)/2.0;
		l = Math.sqrt(x*x+y*y);
		vx[i] = Math.floor(x*velocity/l+0.5);
		vy[i] = Math.floor(y*velocity/l+0.5);
		console.log("(" + vx[i] + ", " + vy[i] + ")");
	}
}

function point_str(x, y)
{
	return "("+Math.round(x*100)/100+","+Math.round(y*100)/100+")";
}

function plain(x) { return x; }

var snap = plain.bind(this);

function update_pos(t)
{
	var v = getv(c1, c2);
	v1.x1 = snap(c1.x);
	v1.y1 = snap(c1.y);
	v1.x2 = v1.x1 + v.x;
	v1.y2 = v1.y1 + v.y;

	var dx = snap(c2.x) - snap(c1.x);
	var dy = snap(c2.y) - snap(c1.y);
	var len = Math.sqrt(dx*dx + dy*dy);
	v2.x1 = v1.x1;
	v2.y1 = v1.y1;
	v2.x2 = v2.x1 + dx*velocity/len;
	v2.y2 = v2.y1 + dy*velocity/len;

	var s = point_str(v1.x1, v1.y1);
	s += " " + point_str(snap(c2.x), snap(c2.y));
	s += " " + point_str(v2.x2-v2.x1, v2.y2-v2.y1);
	s += " " + point_str(v.x, v.y);
	d3.select("#info").text(s);
}

build();

var color = d3.scale.category10();

d3.select("#velocity").on("input", function() {
	velocity = +this.value;
	build();
	update_pos(0);
	update();
});

d3.select("#snap").on("change", function () {
	if(d3.select("#snap").property("checked")) {
		snap = Math.round.bind(Math);
	} else {
		snap = plain;
	}
});

var svg = d3.select("svg");

svg.style("pointer-events", "all");
var width = svg.attr("width");
var height = svg.attr("height");

var initial = [0+width/2,128+height/2];
svg = svg.call(d3.behavior.zoom().translate(initial).scaleExtent([1, 40]).on("zoom", zoom));
svg.append("rect")
	.attr("width", width)
	.attr("height", height)
	.style("fill", "none");

svg = svg.append("g").attr("transform","translate("+initial[0]+","+initial[1]+")");

var drag = d3.behavior.drag()
	.origin(function(d) { return d; })
	.on("dragstart", dragstarted)
	.on("drag", dragged)
	.on("dragend", dragended);

svg.append("g")
	.attr("class", "x axis")
	.selectAll("line")
	.data(d3.range(0, 256+1, 8))
	.enter().append("line")
	.attr("x1", function(d) { return d; })
	.attr("y1", -128)
	.attr("x2", function(d) { return d; })
	.attr("y2", 128);

svg.append("g")
	.attr("class", "y axis")
	.selectAll("line")
	.data(d3.range(-128, 128+1, 8))
	.enter().append("line")
	.attr("x1", 0)
	.attr("y1", function(d) { return d; })
	.attr("x2", 256)
	.attr("y2", function(d) { return d; });

var circles = svg.selectAll("circle")
	.data([c1, c2]);
var circle = circles
	.enter().append("circle")
		.attr("r", function(d) { return d.r; })
		.attr("cx", function(d) { return d.x; })
		.attr("cy", function(d) { return d.y; })
		.style("fill", function(d) { return d.color; })
		.call(drag);

circle.append("circle")
	.attr("r", function(d) { return d.r; });

var vectors = svg.selectAll(".vector")
	.data([v1, v2]).enter()
	.append("path")
	.attr("class", "vector")
	.style("stroke", function (d) { return d.color; });

function zoom() {
	svg.attr("transform", "translate(" + d3.event.translate + ")scale(" + d3.event.scale + ")");
	svg.select("path").style("stroke-width", 1/d3.event.scale);
	vectors.style("stroke-width", 2/d3.event.scale);
	a_scale = Math.min(5/d3.event.scale, 0.5);
}

function dragstarted(d) {
	d3.event.sourceEvent.stopPropagation();
}

function dragged(d) {
	d3.select(this).attr("cx", snap(d.x = d3.event.x)).attr("cy", snap(d.y = d3.event.y));
	update_pos(0);
	update();
}

function dragended(d) {
}

function vectorP(v)
{
	var path = ["M", v.x1, ",", v.y1];
	path.push("L", v.x2, ",", v.y2);
	var dx = v.x2 - v.x1;
	var dy = v.y2 - v.y1;
	var len = dx*dx + dy*dy;
	if (Math.abs(len) > 1e-7)
	{
		len = Math.sqrt(len);
		dx /= len;
		dy /= len;
		path.push("L", v.x2 - dy * a_scale - dx * a_scale, ",", v.y2 + dx * a_scale - dy * a_scale);
		path.push("L", v.x2 + dy * a_scale - dx * a_scale, ",", v.y2 - dx * a_scale - dy * a_scale);
		path.push("L", v.x2, ",", v.y2);
		path.push("Z");
	}
	return path.join("");
}

function update() {
	vectors.each(function(d) {
		d3.select(this).attr("d", vectorP(d));
	});
}

update_pos();
update();

</script>

preview.png

regions.png

slopes.png

source.cpp

#include <cstdio>
#include <string>
#include <cmath>

// idea verification using C++
// src, dest
// x is in range [0,256]
// y is in range [-128, 128]

unsigned char vx[8];
unsigned char vy[8];

struct Point
{
    char x, y;
    Point (char x=0, char y=0) : x(x), y(y) {}
};

char getangle(unsigned char x, unsigned char y)
{
    unsigned char tx = x / 8;
    if (!tx)
        return 0;
    unsigned char a = 0;
    unsigned char na;
    char r = 0;
    while (true)
    {
        na = a + tx;
        if (na >= y)//((int(r+1)*int(x))/8 > y)
            break;
        a = na;
        ++r;
    }
    if (r > 7)
        r = 7;
    return r;
}

Point getv(const Point &a, const Point &b)
{
    char sign1 = false, sign2 = false, sign3 = false;
    unsigned char dx, dy;
    dx = b.x - a.x;
    if (b.x < a.x)
    {   // abs & save sign
        sign1 = true;
        dx = -dx;
    }
    dy = b.y - a.y;
    if (b.y < a.y)
    {   // abs & save sign
        sign2 = true;
        dy = -dy;
    }
    if (dx <= dy)
    {   // swap
        char tmp = dy;
        dy = dx;
        dx = tmp;
        sign3 = true;
    }
    char angle = getangle(dx, dy);
    dx = vx[int(angle)];
    dy = vy[int(angle)];
    if (sign3)
    {   // swap
        unsigned char tmp = dy;
        dy = dx;
        dx = tmp;
    }
    if (sign1)
        dx = -dx;
    if (sign2)
        dy = -dy;
    return Point(dx, dy);
}

void build()
{
    const int v = 20;
    for (int i=0; i<8; ++i)
    {
        double x1 = 1;
        double y1 = i/8.0;
        double x2 = 1;
        double y2 = (i+1)/8.0;
        double l = sqrt(x1*x1+y1*y1);
        x1 /= l;
        y1 /= l;
        l = sqrt(x2*x2+y2*y2);
        x2 /= l;
        y2 /= l;
        double x = (x1+x2)/2.0;
        double y = (y1+y2)/2.0;
        l = sqrt(x*x+y*y);
        vx[i] = (unsigned char)(x*v/l+0.5);
        vy[i] = (unsigned char)(y*v/l+0.5);
        printf("(%d, %d)\n", int(vx[i]), int(vy[i]));
    }
}

int main()
{
    build();
    for(;;)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
        if (x1 < 0)
            break;
        Point r = getv(Point(x1, y1), Point(x2, y2));
        printf("%d %d\n", int(r.x), int(r.y));
    }
    return 0;
}

thumbnail.png