Selecting the nearest point, in the more intelligent way

Hi everyone,

I’m sketching a new game. I won’t give you full details here, because this is not the subject. Based on this picture :

Sprite-0001

The player can “select” a point. I want the player to be able to “navigate” between those points : every time he moves with an arrow button, it will select another point.

Let’s imagine the player is on the blue point. This is just only my point of view :

  • From blue, he presses right button : the red one should be selected
  • From blue, he presses the down button, the player should be moved to the green point

I won’t go further onto the explanations, because I’m pretty sure this problem has a name, but… I simply don’t know it.

First, do you think I was right on my two assumptions ?
Second, could you help me to put a name on this problem, so I could check some documentation on it.

Thanks !

I can’t name it, but I describe it and solve it using vectors and dot products.

Essentially you’re looking for the circle that’s closest to the axis-aligned vector pointing in a particular direction dictated by a button press.


As for how to go about solving it…

Consider each circle to consist of an x coordinate, a y coordinate and a radius.
E.g.

struct Circle
{
  float x;
  float y;
  float radius;
};

Now consider the concept of a vector to consist of an x component and a y component:

struct Vector
{
  float x;
  float y;
};

(If you don’t know much about vectors, see here.)

First, generate your button direction vector (which will always be an axis-aligned unit vector):

  • If the right button is pressed, use { 1.0f, 0.0f }
  • If the left button is pressed, use { -1.0f, 0.0f }
  • If the up button is pressed, use { 0.0f, -1.0f }
  • If the down button is pressed, use { 0.0f, 1.0f }

Iterate through all non-selected circles and generate the vectors between those circles and the selected circle by subtracting the position of the non-selected circle from the selected circle.
(There’s a good video about vector subtraction here.)

That gives you the vectors between the selected circle and the non-selected circles.
Now calculate the dot products between those vectors and the button direction vectors.
(For more information about the dot product, see here, or this video.)

Finally, figure out which dot product is the largest.
The circle that generated that dot product is the circle that you should move to.

Note that this will give odd results if the selected circle is already the leftmost/rightmost/upmost/bottomost circle.
That condition will have to be handled separately.

Also this will select the circle closest to the axis line,
which isn’t necessarily the closest circle in that direction.
If the closest circle is required, that would require a different approach.


E.g.

Circle circles[4]
{
	// Define the circles
};

constexpr size_t circleCount = 4;

size_t selectedIndex = 0;

Vector getButtonDirection()
{
	if(arduboy.justPressed(RIGHT_BUTTON))
		return { 1.0f, 0.0f };
		
	if(arduboy.justPressed(LEFT_BUTTON))
		return { -1.0f, 0.0f };
		
	if(arduboy.justPressed(UP_BUTTON))
		return { 0.0f, -1.0f };

	if(arduboy.justPressed(DOWN_BUTTON))
		return { 0.0f, 1.0f };

	return { 0.0f, 0.0f };
}

float dot(const Vector & left, const Vector & right)
{
	return ((left.x * right.x) + (left.y * right.y));
}

size_t findNextPoint(const Vector & direction)
{
	const Circle & selected = circles[selectedIndex];

	size_t nextIndex = selectedIndex;
	
	float maximumDot = -1.0f;
	
	for(size_t index = 0; index < circleCount; ++index)
	{
		if(index == selectedIndex)
			continue;
			
		const Circle & circle = circles[index];
		
		Vector vector { (circle.x - selected.x), (circle.y - selected.y) }:
		
		float dotProduct = dot(direction, vector);
		
		if(dotProduct > maximumDot)
		{
			maximumDot = dotProduct;
			nextIndex = index;
		}
	}
	
	return nextIndex;
}

void selectNextPoint()
{
	Vector direction = getButtonDirection();
	
	if((direction.x == 0) && (direction.y == 0))
		return;
		
	selectedIndex = findNextPoint(direction);
}

(Completely untested code. Might not work.)

1 Like

Thanks @Pharap, I’ll try things like that, and post the code here if I can produce something !

1 Like

Thanks for the resources on Vectors, didn’t really know about this. Time to read !

1 Like

Hi !

So, I had to take everything from the beginning, because first, I did not remember at all what a vector is !

I tried a simple implementation of those concepts that is organized in two classes. I know it’s a bit out of the subject of this post, but I got a “C++” mistake. Here are my two classes.

#ifndef POINT_H
#define POINT_H

#include "Vector2D.h"

namespace Benov
{

struct Point
{

    int8_t x;
    int8_t y;

    Vector2D vector2D;

    /**
     * Make the point moving to another point
     */
    void moveTo(const Point &point)
    {
        // Creates the vector between those two points
        Vector2D vector = vector2D.moveBetween(*this, point);

        // Moving
        x = round(x + vector.x);
        y = round(y + vector.y);
    }
};
}

#endif

And :

#ifndef VECTOR2D_H
#define VECTOR2D_H

namespace Benov
{

struct Vector2D
{

    float x;
    float y;


    Vector2D() = default;

    Vector2D(float X, float Y)
    {
        x = X;
        y = Y;
    }

    // [...]

    /**
     * Returns a vector that represents the movement
     * needed to get to another point, from our actual point
     * 
     * This is the same as doing a vector substitution.
     */
    Vector2D moveBetween(Point &from, const Point &to)
    {
        return Vector2D(
            to.x - from.x * 1.0,
            to.y - from.y * 1.0
        );
    }

    // [...]
    
};
}

#endif

When i compile, I got :

In file included from /tmp/arduino_build_943875/sketch/src/Ball.h:6:0,
from /home/bjupille/code/games/tabilo/tabilo/tabilo.ino:18:
/tmp/arduino_build_943875/sketch/src/Math/Point.h: In member function ‘void Benov::Point::moveTo(const Benov::Point&)’:
/tmp/arduino_build_943875/sketch/src/Math/Point.h:23:64: error: no matching function for call to ‘Benov::Vector2D::moveBetween(Benov::Point&, const Benov::Point&)’
Vector2D vector = vector2D.moveBetween(*this, point);
^
In file included from /tmp/arduino_build_943875/sketch/src/Math/Point.h:4:0,
from /tmp/arduino_build_943875/sketch/src/Ball.h:6,
from /home/bjupille/code/games/tabilo/tabilo/tabilo.ino:18:
/tmp/arduino_build_943875/sketch/src/Math/Vector2D.h:46:18: note: candidate: Benov::Vector2D Benov::Vector2D::moveBetween(Point&, const Point&)
Vector2D moveBetween(Point &from, const Point &to)
^~~~~~~~~~~
/tmp/arduino_build_943875/sketch/src/Math/Vector2D.h:46:18: note: no known conversion for argument 1 from ‘Benov::Point’ to ‘Point&’

I’m pretty sure I’m missing something on pointers and reference, but I was also wondering if namespace could be the origin of my issue.

Maybe you could bring me some leads please ?

If you change from this:

Vector2D vector = vector2D.moveBetween(*this, point);

to

Vector2D vector = vector2D.moveBetween(this, point);

Thanks for your answer @filmote, but I got something similar :

n file included from /tmp/arduino_build_726771/sketch/src/Ball.h:6:0,
from /home/bjupille/code/games/tabilo/tabilo/tabilo.ino:18:
/tmp/arduino_build_726771/sketch/src/Math/Point.h: In member function ‘void Benov::Point::moveTo(const Benov::Point&)’:
/tmp/arduino_build_726771/sketch/src/Math/Point.h:23:63: error: no matching function for call to ‘Benov::Vector2D::moveBetween(Benov::Point*, const Benov::Point&)’
Vector2D vector = vector2D.moveBetween(this, point);
^
In file included from /tmp/arduino_build_726771/sketch/src/Math/Point.h:4:0,
from /tmp/arduino_build_726771/sketch/src/Ball.h:6,
from /home/bjupille/code/games/tabilo/tabilo/tabilo.ino:18:
/tmp/arduino_build_726771/sketch/src/Math/Vector2D.h:46:18: note: candidate: Benov::Vector2D Benov::Vector2D::moveBetween(Point&, const Point&)
Vector2D moveBetween(Point &from, const Point &to)
^~~~~~~~~~~
/tmp/arduino_build_726771/sketch/src/Math/Vector2D.h:46:18: note: no known conversion for argument 1 from ‘Benov::Point*’ to ‘Point&’

That’s just trying to pass it a pointer instead.
The circular reference is the source of the problem.


The main problem is that you’ve got some circular references.

Point depends on Vector2D and Vector2D depends on Point.
Normally the solution to that would be to start splitting things into .h and .cpp files, but there’s an easier option: just move moveBetween into Point.h instead.

If you move moveBetween into Point.h and make it a free function (or a static member function if you’d rather), everything should work.

Some other things worth mentioning:

  • moveTo seems rather pointless because the way it’s currently written means doing a.moveTo(b) is going to give you the same result as just doing a = b.
  • Doing * 1.0 is a redundant operation. If the intent was to convert to float, you should use static_cast instead, e.g. static_cast<float>(from.x), though in this case it wouldn’t make a difference anyway because subtracting two integers will never generate a fractional part, only division will.
  • It’s strange for one to be called Vector2D and one to be called Point, I would have expected either Vector2D and Point2D or Vector and Point, or for them to be named based on what type their x and y coordinates are, e.g. VectorF and PointI8

Anyway, something like this ought to work:

#pragma once

namespace Benov
{
	struct Vector
	{
		float x;
		float y;

		Vector() = default;

		Vector(float x, float y) :
			x { x }, y { y }
		{
		}
	};
}
#pragma once

#include "Vector.h"

namespace Benov
{
	struct Point
	{
		int8_t x;
		int8_t y;

		Point() = default;

		Point(int8_t x, int8_t y) :
			x { x }, y { y }
		{
		}
	};

	inline Vector vectorBetween(const Point & from, const Point & to)
	{
		return { (to.x - from.x), (to.y - from.y) };
	}
}

There may actually be an easier way to do what you want to do than using vectors depending on what the actual end goal is.

For example, if your circles never change location you can precalculate everything beforehand.
E.g. by an arrangement like:

struct Circle
{
	int16_t x;
	int16_t y;
};

struct Links
{
	uint8_t left;
	uint8_t right;
	uint8_t up;
	uint8_t down;
};

struct CircleReference
{
	Circle circle;
	Links links;
};

CircleReference references[]
{
	// 0
	{
		{ 63, 31 },
		// Going up takes you to circle 1
		{ 0, 0, 1, 0 }
	}
	// 1
	{
		{ 63, 15 },
		// Going down takes you to circle 0
		{ 1, 1, 1, 0 }
	}
};

Or depending on how your circles are arranged, it may be enough to just search for the next largest/smallest x/y value.

(Or depending on what you really want to do, all this talk of circles could be an XY Problem.)

Thanks ! I understand the issue way better now.

By looking up on different documentations, I’ve found that circular referencing can be resolved by adding struct Point; above my struct Vector2D{ ... }; declaration.

What do you think about that ? Does a circular reference is bad, in any language ?

Actually, I personally find the solution I bring very ugly. I think you’re right, the issue is probably in conception. I will take the advice you gave me.

Thanks !

Sometimes that’s useful if you’re splitting your code into .h and .cpp files as well, but on its own it’s not enough.

For example, here’s an example of two hypothetical classes A and B that have a circular reference but will compile properly:

// A.h
#pragma once

class B;

class A
{
	int value;
	
	void useB(const B &);
};
// A.cpp
#include "A.h"
#include "B.h"

void A::useB(const B & object)
{
	std::cout << object.value << '\n';
}
// B.h
#pragma once

class A;

class B
{
	int value;
	
	void useA(const A &);
};
// B.cpp
#include "B.h"
#include "A.h"

void B::useA(const A & object)
{
	std::cout << object.value << '\n';
}

No, circular references are not inherantly bad.

Sometimes there might be a better alternative than introducing a circular reference,
but other times circular references are simply unavoidable.

More modern languages (e.g. C#) tend to use different compiling techniques (e.g. multi-pass compilation) that mean circular references aren’t as much of a problem,
but C++ was designed in a different era (where single-pass compilation was the norm) and is mostly stuck with its early choices,
so consequently any circular references need to be handled specially.

1 Like