• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
cozzie

sorting floats with index

21 posts in this topic

Hi,

I'm struggling with something which sounds fairly simple... although..

 

- I have a int array containing incices of meshes, say Meshes[5] = { 3, 1, 4, 9, 2};

- these indices point to objects (meshes) with a member 'distance' (float)

- say the meshes with indices above have: 10, 30, 40, 50, 15 as distance

 

What I want to achieve is the new index (int array) sorted on the descending order of the member floats..

 

I got so far to be able to sort the int array without the floats, and I got that far to sort the floats as an array (distances).

Simply don't know how to complete this goal...

 

Here's the code that partially does this.

Can someone help me out?

 

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	float elements = sizeof(dists) / sizeof(dists[0]); 
	std::sort(dists, dists+mNrD3dMeshesBlended, std::greater<float>());

//	int elements = sizeof(mMeshIndexBlended) / sizeof(mMeshIndexBlended[0]); 
//	std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, std::greater<int>());

 

 

0

Share this post


Link to post
Share on other sites

I'd create a struct that holds the original index and the distance. Add an operator > which compares the distance members. Populate a std::vector with instances of the struct for each mesh index/distance combination you need. Then use std::sort on the vector, and voila :-)

1

Share this post


Link to post
Share on other sites

Thanks for the quick reactions, I guess I'll have to dig into pairs/vectors (till now not used that much :))

Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?

(looking at memory allocation for the pairs or structs)

0

Share this post


Link to post
Share on other sites
Keeping in mind that this function will run each frame I render, is this the most efficient way to do this?
(looking at memory allocation for the pairs or structs)

 

As long as you keep the std::vector around between frames, there shouldn't be much allocation going on (only when the vector's length grows significantly). Your struct (or std::pair, for that matter) should be a very thin wrapper class, and created on the stack - no real cost to those allocations, and copying them into the vector should be similarly cheap.

 

Ideally, the sort itself should dominate the performance cost here. I presume you are not sorting a huge number of items?

0

Share this post


Link to post
Share on other sites

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

[code]std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists[b];});[/code]

 

Or the pre-C++11 way:

[code]struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values[b]; }

    float *values;
}; ... std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));[/code]

1

Share this post


Link to post
Share on other sites
Wow, that looks easy (although I have do dig in and read/ study it to understand:))
But it compiles directly, thanks :)

The result is not exacly as expected, but nearly there.
It's sorting but not yet as I'd expect.

Array before sorting:

Render: 1 ,dist to cam: 163.554
Render: 3 ,dist to cam: 136.565
Render: 5 ,dist to cam: 111.131
Render: 7 ,dist to cam: 88.6002
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 13 ,dist to cam: 132.098
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 25 ,dist to cam: 152.151
Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37

After sort:

Render: 27 ,dist to cam: 46.3681
Render: 29 ,dist to cam: 39.37
Render: 25 ,dist to cam: 152.151
Render: 15 ,dist to cam: 105.594
Render: 17 ,dist to cam: 81.5475
Render: 19 ,dist to cam: 62.849
Render: 21 ,dist to cam: 154.11
Render: 23 ,dist to cam: 150.167
Render: 1 ,dist to cam: 163.554
Render: 5 ,dist to cam: 111.131
Render: 13 ,dist to cam: 132.098
Render: 3 ,dist to cam: 136.565
Render: 9 ,dist to cam: 71.7635
Render: 11 ,dist to cam: 159.844
Render: 7 ,dist to cam: 88.6002 Edited by cozzie
0

Share this post


Link to post
Share on other sites

From your initial set of indices, I get the impression now that your indices are not sequential. In that case, my method won't work. It assumes that index n has the distance value dists[n], while it seems like you have a set of index/distance pairs (n, dist) with arbitrary n and dist, and that has to be sorted by dist. If that's the case, then the structure approach suggested earlier will work.

0

Share this post


Link to post
Share on other sites

too bad, I'll have to get into that then.

Thanks for the help.

 

My gut feeling that there must be a easy way was not true then :)

0

Share this post


Link to post
Share on other sites
Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.
0

Share this post


Link to post
Share on other sites
My gut feeling that there must be a easy way was not true then smile.png

It's really not that complicated...

std::vector< std::pair<float, int> > data;

data.push_back( std::make_pair(0.5, 12) );
data.push_back( std::make_pair(1.75, 14) );
data.push_back( std::make_pair(1.5, 4) );
data.push_back( std::make_pair(0.25, 7) );

std::sort(data.begin(), data.end());
0

Share this post


Link to post
Share on other sites
Stick the distances and indices in a std::map<float, int> then, with the float as the key. Then when you iterate through the map you will get the indices back in order of increasing float key.

 

This is dangerous if you might have identical distances, as one will stomp the others. You might prefer a std::multimap instead, but even then, the cost of building the tree, traversing it, and maintaining sorted order during inserts/removes is going to clobber your speed compared to just stuffing things into a vector and sorting once.

1

Share this post


Link to post
Share on other sites

Well, thinking about it a bit more, you can actually use my approach with some modifications: add an additional order-array and add an additional level of referencing to the comparison.

 

[code]int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended-1 ... std::sort(     order,     order+mNrD3dMeshesBlended,     [&](int a, int b) {         return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended[b]];     } );[/code]

The array order can, after sorting, be used to traverse the index arrays in sorted order based on distance.

0

Share this post


Link to post
Share on other sites

Great!

 

try a little modification

struct pred {
    pred(d3dMesh *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a].mDistToCam < values[b].mDistToCam; }
    d3dMesh *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(mD3dMeshes));

 

 

You can also use a custom predicate that sorts the indices by comparing the distance values at the corresponding indices.

 

The C++11 way:

 

std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, [&](int a, int b) {return dists[a]<dists[b];});

 

 

Or the pre-C++11 way:

 

struct pred {
    pred(float *values) : values(values)
    {}
    
    bool operator()(int a, int b)
    { return values[a] < values[b]; }
    float *values;
};
...
std::sort(mMeshIndexBlended, mMeshIndexBlended+mNrD3dMeshesBlended, pred(dists));

 

0

Share this post


Link to post
Share on other sites

I might have read it wrong and filled the int array with the non-sorted index, just filled it with just 0, 1, 2 etc. up to mNrD3dMeshesBlended.

Error is gone now, and here's the result up till now:

 

Before sort:

Order org: 1 ,dist to cam: 163.554
Order org: 3 ,dist to cam: 136.565
Order org: 5 ,dist to cam: 111.131
Order org: 7 ,dist to cam: 88.6002
Order org: 9 ,dist to cam: 71.7635
Order org: 11 ,dist to cam: 159.844
Order org: 13 ,dist to cam: 132.098
Order org: 15 ,dist to cam: 105.594
Order org: 17 ,dist to cam: 81.5475
Order org: 19 ,dist to cam: 62.849
Order org: 21 ,dist to cam: 154.11
Order org: 23 ,dist to cam: 150.167
Order org: 25 ,dist to cam: 152.151
Order org: 27 ,dist to cam: 46.3681
Order org: 29 ,dist to cam: 39.37
 

 

After sort:

Order: 12
Order: 13
Order: 14
Order: 7
Order: 8
Order: 9
Order: 10
Order: 11
Order: 6
Order: 4
Order: 1
Order: 3
Order: 0
Order: 5
Order: 2
 

Probably this is the order based on the new int array being 0 up to mNrD3dMeshesBlended.

Now probably have to link them all together.

0

Share this post


Link to post
Share on other sites

I can't find the relation yet between the output and the corresponding index of the original index/ array. The code now looks like this (please don't mind al the local variables, will pick this up later when I get the aimed output)

 

	std::ofstream before("blaorg.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		before << "Unsorted: " << mMeshIndexBlended[j] << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	before.close();

	float *dists = new float[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	int *order = new int[mNrD3dMeshesBlended]; // fill this one with values from 0 and up to mNrD3dMeshesBlended
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; //mMeshIndexBlended[oc];

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return dists[mMeshIndexBlended[a]]<dists[mMeshIndexBlended[b]]; });

	std::ofstream after("bla.txt");
	for(int j=0;j<mNrD3dMeshesBlended;++j)
		after << "Sorted: " << order[j] << std::endl; // << " ,dist to cam: " << mD3dMeshes[mMeshIndexBlended[j]].mDistToCam << std::endl;
	after.close();

 

The output of this in the reply above, before and after sorting.


When I look at it, it's probably bad that the indices in the "order" int array don't match up with the distances in the float array.

Shouldn't I fill the "order" int array with the unsorted index? (although giving an access violation at the moment)

 

0

Share this post


Link to post
Share on other sites

I apologize for my previous attempts at trying to get this right. I have partly read your question too quick, and partly been evaluating it with the wrong set of values and not seen the obvious errors. However, third times a charm; is this what you want? This time I'm even using your exact values and not some made-up test bench.

[code]int main()
{
    int order[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    int indices[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29};
    int values[] = {163.554, 136.565, 111.131, 88.6002, 71.7635, 159.844, 132.098, 105.594, 81.5475, 62.849, 154.11, 150.167, 152.151, 46.3681, 39.37};
   
    std::sort(
        order,
        order+15,
        [&](int a, int b){
            return values[a]<values[b];
        }
    );
    
    for(int i : order) {
        std::cout << "(" << indices[i] << ", " << values[i] << ")" << std::endl;
    }
}[/code]

The idea is to forget about the index-values of the vector you want to sort, and just do an index-sort on the vector values directly. As long as the contents of values is unchanged, the vector indices maintains its correspondence to the vector values.

0

Share this post


Link to post
Share on other sites

Thanks Bob, I really appreciate your help.

I tried it out right away and it looks like it's working, last steps to get the right data on the right place will definitely work out.

 

Here's the code I have now and the output.

I'll go work on getting the arrays in my class, to prevent all the memory allocation for each rendered frame.

 

Thanks again.

 

	int *order = new int[mNrD3dMeshesBlended]; 
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; 

	int *indices = new int[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) indices[oc] = mMeshIndexBlended[oc];

	int *dists = new int[mNrD3dMeshesBlended];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) dists[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return dists[a]<dists[b]; });

Unsorted output:

 0 Unsorted: 1 ,dist to cam: 95.6556
1 Unsorted: 3 ,dist to cam: 105.594
2 Unsorted: 5 ,dist to cam: 152.151
3 Unsorted: 7 ,dist to cam: 46.3681
4 Unsorted: 9 ,dist to cam: 39.37
 

Sorted:

Sorted: 4  39
Sorted: 3  46
Sorted: 0  95
Sorted: 1  105
Sorted: 2  152

0

Share this post


Link to post
Share on other sites

Yeeeehaaa, all done.

Here's the result:

 

void CD3dscene::SortBlendedMeshes(D3DXVECTOR3 pCamPosition)
{
	for(oc=0;oc<mNrD3dMeshesBlended;++oc)
	{
		mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam = CoordToCoordDist(pCamPosition, mD3dMeshes[mMeshIndexBlended[oc]].mWorldPos);
	}

	int *order = new int[mNrD3dMeshesBlended]; 
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) order[oc] = oc; 

	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshIndexTemp[oc] = mMeshIndexBlended[oc];
	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshDistToCam[oc] = mD3dMeshes[mMeshIndexBlended[oc]].mDistToCam;

	std::sort(order, order+mNrD3dMeshesBlended, [&](int a, int b) { return mMeshDistToCam[a]>mMeshDistToCam[b]; });

	for(oc=0;oc<mNrD3dMeshesBlended;++oc) mMeshIndexBlended[oc] = mMeshIndexTemp[order[oc]];

	SafeDelete(order);
}

 

The only thing I doubt is if I also should make the order int array a class member, since it's created (and released/deleted to) each frame.

What do you think?

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0