Sort objects vector according to player position

[Geckoo]

Hello everyone. I would like to sort an vector with objects which I know their position. I have my inline function to compute distance, but I don't understand how I should use sort in order to get closer objects as last displaying objects. Do you have an idea ? Thank you ++

for (int y = 0; y < size; y++)
  for (int x = 0; x < size; x++)
    if (mapAsSprite->GetPixel(gck::vi2d(x, y)) == mushroomColour)
      billboards.push_back(Billboard(gck::vf2d(x + .5f, y + .5f), mushroomTexture));
// ... playerPos = ...
// in the update section according to the player position.
// compute distance between two points (header file)
inline float xGameEngine::computeDistance(const gck::vi2d& p1, const gck::vi2d& p2)
{
  float diffY = p1.y - p2.y;
  float diffX = p1.x - p2.x;
  return sqrt((diffY * diffY) + (diffX * diffX));
}
// pseudo code
sort(begin(billboards), end(billboards), computeDistance(object in billboards vector pos, playerPos)); // ??? 

I tried many variants, but I have always an error during compilation. I miss something somewhere :/
I don't understand the right semantic...

sort(begin(billboards), end(billboards), computeDistance(gck::vi2d(billboard.pos.x, billboard.pos.y), gck::vi2d(playerPosition.x, playerPosition.y)));
sort(billboards.begin(), billboards.end(), std::greater<int>());

Erreur	C2664	'bool std::greater<int>::operator ()(const _Ty &,const _Ty &) const' : 
impossible de convertir l'argument 1 de 'Billboard' en 'const _Ty &'	

[keskiverto]

The third parameter to std::sort, the comp, is:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.

That is, something like:

bool billcomp( const Billboard& lhs, const Billboard& rhs ) {
  auto dl = computeDistance( dl, playerPos );
  auto dr = computeDistance( dr, playerPos );
  return dl > dr;
}

That, obviously, has unknown 'playerPos'. In old C++ we would define a class that has playerPos as member and operator() to allow it act like a function (functor).

Modern C++ has lambda closures. https://en.cppreference.com/w/cpp/language/lambda

sort( begin(billboards), end(billboards),
  [playerPos]( const auto& lhs, const auto& rhs ) {
    auto dl = computeDistance( lhs, playerPos );
    auto dr = computeDistance( rhs, playerPos );
    return dl > dr; }
);

[zapshe]

Some issues:

return sqrt((diffY * diffY) + (diffX * diffX));
This return value is not a true or false, which is what it wants to determine how to sort.

For example:

bool sort(int &one, int &two)
{
	return one < two;
}

That would be a proper function, as it compares values and returns a true or false. To use this kind of function in sort(), you want to use a lambda function like this:

int main()
{
	vector<int> a = { 1, 61, 913, 12 };

	sort(a.begin(), a.end(), [](int &one, int &two)
		{
			return one < two;
		});


	//output the vector to check it's sorted:
	for (auto i : a)
	{
		cout << i << '\n';
	}
}

You can use that to create custom comparisons for things:

int main()
{
	vector<pair<int, int>> a = { {1, 5}, {61, 2}, {913, 7}, {12, 6} };

        //used auto, could have put pair<int, int> instead
	sort(a.begin(), a.end(), [](auto& one, auto& two)
		{
			return one.second < two.second;
		});


	//output the vector to check it's sorted:
	for (auto i : a)
	{
		cout << i.second << '\n';
	}
}

[Geckoo]

Thank you everyone for your clever explanations. I understand better now.
It is less complicated than I figured before :)
Each object has its structure. So I can add a distance integer as a parameter. Thank you ++

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  std::vector<int> dist = { 10, 78, 22, 45, 32 };
  std::sort(dist.begin(), dist.end(), [](int& a, int& b){ return a < b; });

  for (auto i : dist)
    std::cout << i << '\n';
}

[seeplus]

Each object has its structure. So I can add a distance integer as a parameter.

If you do this and use C++20, then with ranges you can do things like:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Data {
	int a {}, b {};
	int dist {};

	Data(int a_, int b_) : dist(std::abs(a_ - b_)), a(a_), b(b_) {}
};

int main() {
	std::vector<Data> mydata { { 1, 2 }, { 2, 4 }, { 3, 6 }, { 4, 5 }};

	std::ranges::sort(mydata, {}, &Data::dist );

	for (const auto& [a, b, d] : mydata)
		std::cout << '(' << a << ' ' << b << ") ";

	std::cout << '\n';
}

(1 2) (4 5) (2 4) (3 6)

[Geckoo]

Done.

struct Billboard
{
public:
  gck::vf2d pos;
  gck::Sprite *sprite;
  float dist = 0.0f; // new parameter

  Billboard(gck::vf2d p, gck::Sprite* spr) 
  { 
    pos = p; 
    sprite = spr; 
  }
};

for (auto& billboard : billboards)
   billboard.dist = computeDistance(gck::vf2d(playerPosition.x, playerPosition.y), gck::vi2d(billboard.pos.x, billboard.pos.y));
// sort structure according value distance
std::sort(billboards.begin(),billboards.end(), [](Billboard& a, Billboard& b) { return a.dist > b.dist; });

This way sprites which are far to my player will be displayed under those which are closer.
It works as expected. More or less like layers...
Thank you everyone for your help and clever explanations ++

[JLBorges]

> std::sort(billboards.begin(),billboards.end(), [](Billboard& a, Billboard& b) { return a.dist > b.dist; });

This (comparison function accepting reference to non-const objects) may result in compile-time errors.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy.
https://en.cppreference.com/w/cpp/algorithm/sort

Make it

std::sort(billboards.begin(),billboards.end(), 
          []( const Billboard& a, const Billboard& b ) { return a.dist > b.dist; });

[Geckoo]

Right. Thank you for the tips :)

[lastchance]

For efficiency, sort on distance-squared, not distance. You will get the same ordering, but avoid the necessity of repeated calls to a square-root function.