(Easy, i think) array sorting problem

[LakySimi1]

Hi everyone,
i'm making a raycasting renderign engine, i have to sort by distance the sprites, from further to nearest.

First of all i scroll (sorry for my bad english) the SpritesX array, which contain all x coordinates of all the sprites, in no particular order; then calculate the distance player-sprite for each of them storing the result in DistanceSprites array.

Then, the ordering: i scroll the DistanceSprites array and save in OrderedDraw the index of the sprite which is furthest (the larger number) but less further of the OrderedDistance[index-1], which i use for this purpose, track the elements sorted.

In this way i obtain the array OrderedDraw, scrolling which tell me the index of the SpritesX and SpritesY to use to render the sprite, so i can render them from further to nearest (painters algorithm).
OrderedDraw contain the ID of sprites sorted by distance.

The code works initially but when the player move of 1 space i get some strange values, for example:
DistanceSprites = 6,12,35;
give me
OrderedDistance = 36, 35.996, 35.978;




I also need to render the sprites that eventually has the same distance, which this code doesn't do, and i can't figure it out how to do.

CALCULATE DISTANCES

    int i = 0;
    int j = 0;

    ///CALCULATING DISTANCES PLAYER-SPRITE
    for(i = 0; i < worldSize*worldSize; i++)
    {
        if (SpritesX[i] == 0)     //if 0 means i have scroll all present sprites
            {
                break;
            }


        spriteX = SpritesX[i];
        spriteY = SpritesY[i];
        deltaX = (xPlayer - spriteX);
        deltaY = (yPlayer - spriteY);
        distancePlayerSpriteUncorrected = deltaX*deltaX + deltaY*deltaY;

        DistanceSprites[j] = distancePlayerSpriteUncorrected;
        VisibleSprites[j] = i;

        j++;     //j is for future plan of render only the visible sprites, for i consider all them visible by player
    }

SORTING

    ///ORDERING
    j=0;
    i = 0;
    int k = 0;
    for(j = 0; j < worldSize*worldSize; j++)
    {
        if (DistanceSprites [j] == 0)
            break;

        float ActualMaxDist = OrderedDistance [j];
        for(i = 0; i < worldSize*worldSize; i++)
        {
            if (DistanceSprites [i] == 0)    //if 0 means i have scroll all present sprites
                    break;

            if (j == 0)   //sorting first element = searching the larger value
            {

                if (DistanceSprites[i] > ActualMaxDist)
                {
                    ActualMaxDist = DistanceSprites[i];
                    OrderedDraw [j] = i;
                    OrderedDistance[j] = ActualMaxDist;
                }
            }
            else if (j > 0)   
            //sorting non first element =  it has to be larger then ActualMaxDist (which is 
            //always the first element of DistanceSprites, and smaller than the last 
            //OrderedDistance, saved in the previous cicle.
            {
                if (DistanceSprites[i] > ActualMaxDist && DistanceSprites[i] < OrderedDistance [j-1])
                {
                    ActualMaxDist = DistanceSprites[i];
                    OrderedDraw [j] = i;
                    OrderedDistance[j] = ActualMaxDist;
                }
            }
        }
    }

SHOWING RESULTS

    for (i = 0; i < worldSize*worldSize; i++)
    {
        if (DistanceSprites [i] == 0)
            //if (VisibleSprites [i+1] == 0)
                break;
        cout << "Sprite x= "<< SpritesX [i] << "   ; Sprite y= " << SpritesY[i] << " ; Sprite ID= " << VisibleSprites[i];
        cout << " - Distance^2= " << DistanceSprites[i] << "   ; Ordered dist=" << OrderedDistance[i] << "   ; Draw order= " << OrderedDraw[i] << endl;
        cout << endl;
    }

Look the last 3 rows..
RESULT OF NORMAL WORKING, the player move just a little, 1 block maybe
https://i.imgur.com/KlWbRVB.png

RESULT OF ANORMAL WORKING, the player move simply longer, the output doesn't depend on the player position:
https://i.imgur.com/qquvsa8.png



PS
If needed i can make a working full code :)

[jonnin]

ok, one thing at a time.
what did you expect when you put 6,12,35 in? Is the player at zero, did you expect 5,11,34 or something like that??

[LakySimi1]

No, i don't put the DistanceSprite, i obtain the values calcalculating the distance from player and single sprite, Player is in (32,32) initially, the sprite location is:

SpritesX [0] = 30;
SpritesX [1] = 28;
SpritesX [2] = 26;

SpritesY [0] = 32;
SpritesY [1] = 32;
SpritesY [2] = 32;

I've updated the open post with slightly cleaned code and image of normal and anormal working results.

Note that the distances are squared because it's faster than doing also the sqare root and i don't need since sort sprites for distance or distance^2 give same output.

[jonnin]

Ok. The distance part seems to be correct.

can you write it to use std::sort to see if that does the same thing? If it works, the bug is in your sort, and I can dig into that, but if it does the same thing, the bug is elsewhere, and your sort may be fine. It looks fine, but I didn't really go into it as I am tired right now.

you may want to just use std::sort anyway. There are only 2 ways I have been able to outperform it, ever. One is by multi-threading/merge back and the other is counting sort on a reasonable range of data, and even for those 2, it takes a large amount of data to register the tweak.

Its doing something odd: is the sort nonstandard, or just trying to skip unnecessary work?

[keskiverto]

std::sort anyway, example:

std::vector<int> spritesX;
std::vector<int> spritesY;
// fill in co-ordinates
assert( spritesX.size() == spritesY.size() );

std::vector<long> distances( spritesX.size() );
for ( size_t i=0; i < distances.size(); ++i ) {
  distances[i] = ...
}

std::vector<size_t> byDistance( distances.size() );
std::iota( byDistance.begin(), byDistance.end(), 0 );
std::sort( byDistance.begin(), byDistance.end(), [&distances](size_t lhs, size_t rhs)
 { return distances[rhs] < distances[lhs]; } );

for ( auto j : byDistance ) {
  // draw spritesX[j] spritesY[j]
}

[LakySimi1]

Thank you all for responding!
I didn't know about std::sort(), by the way googling around i found a very simple sorting code wich i modify to track the index also, this time it's not needed to use OrderedDistance and OrderedDraw since i sort the Distance and Visible array, here's the code:

for(i=0;i<n;i++)      //n is the index of last non-zero value od DistanceSprites
{
    for(j=i+1;j<n;j++)
    {
        if(DistanceSprites[i]<DistanceSprites[j])
        {
            temp = DistanceSprites[i];
            DistanceSprites[i]=DistanceSprites[j];
            DistanceSprites[j]=temp;

            temp = VisibleSprites [i];
            VisibleSprites[i]=VisibleSprites[j];
            VisibleSprites[j]=temp;
        }
    }
}