C++ Divides

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Jul 16, 2005 at 21:45

Hi.

I’m making a 2D terrain generator for my game project, using a midpoint displacement algorithm. I’m storing the heights of the terrain in a std::list as floats. I start by setting the start and end values, then averaging those to find the middle point.

Inserting the middle point into the list works fine - no problems there. But I’m having a problem calculating the average. I get the two points, add them together, then divide the result by 2. This should in theory (and going by the maths I did in school) give me the correct average.

Instead of that though, I get the value of the second point minus 0.5. This is driving me mad, and I can’t work out what the problem is with my code - unless it’s something to do with the way the values are stored in the list. It’s confusing the hell out of me, and I can’t figure out how to fix the problem.

Anyone got any ideas?

6 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 16, 2005 at 22:46

Post code?

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Jul 17, 2005 at 07:29

@Reedbeta

Post code? [snapback]19034[/snapback]

#include <list>
#include <iostream>
#include <time.h>

using std::list;
using std::cout;

void MakeTerrain( int );
void ShowTerrain();

list<float>   terrain;

#define ITERATIONS 1

int main()
{
    srand( (unsigned)time( NULL ) );

    MakeTerrain( ITERATIONS );
    ShowTerrain();
    

    getchar();

    return 0;
};

void MakeTerrain( int iterations )
{
    // both of these will be random later
    terrain.push_back( (float)(rand() % 255 - 128 ));   // start point
    terrain.push_back( (float)(rand() % 255 - 128 )); // end point

    int insertions = 1;

    for( int a = 0; a < iterations; a++ )
    {
 // Outer loop - do this as many times as specified by iterations
 int index = 1;

 list<float>::iterator    vIndex = terrain.begin();
 vIndex++;

 for( int b = 0; b < insertions; b++ )
 {
    float pointA = *vIndex-1;
    float pointC = *vIndex;

    // calculate new point, inserted at vIndex
    terrain.insert( vIndex, (pointA + pointC) / 2 );
 };

 insertions *= 2;
    };
};

void ShowTerrain( void )
{
    cout << "Overall number of points: " << terrain.size() << std::endl;
    for( list<float>::iterator index = terrain.begin(); index != terrain.end(); index++ )
    {
 cout << *index << " ";
    };
};
0684f9d33f52fa189aad7ac9e8c87510
0
baldurk 101 Jul 17, 2005 at 07:39

@Tufty

 for( int b = 0; b < insertions; b++ )
 {
    float pointA = *vIndex-1;
    float pointC = *vIndex;

    // calculate new point, inserted at vIndex
    terrain.insert( vIndex, (pointA + pointC) / 2 );
 };

[snapback]19040[/snapback]

Your pointer manipulation here is wrong. Unary * has a much higher precedence than -. This means that it gets the location pointed at first, then subtracts 1. So PointA = PointC-1, basically. That’s why when you add them and divide by two, you’ll get PointC-0.5.

What you want to do is replace *vIndex-1 with *(vIndex-1) so that the subtract is performed first.

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Jul 17, 2005 at 08:08

@baldurk

@Tufty

 for( int b = 0; b < insertions; b++ )
 {
    float pointA = *vIndex-1;
    float pointC = *vIndex;

    // calculate new point, inserted at vIndex
    terrain.insert( vIndex, (pointA + pointC) / 2 );
 };

[snapback]19040[/snapback]

Your pointer manipulation here is wrong. Unary * has a much higher precedence than -. This means that it gets the location pointed at first, then subtracts 1. So PointA = PointC-1, basically. That’s why when you add them and divide by two, you’ll get PointC-0.5.

What you want to do is replace *vIndex-1 with *(vIndex-1) so that the subtract is performed first.

[snapback]19042[/snapback]

Thanks, that explains that part. But now I’m getting complaints:

d:\Development\test\Main.cpp(42): error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const 
std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt> &)' : could not deduce template argument
 for 'const std::reverse_iterator<_RanIt> &' from 'std::list<_Ty>::iterator'
    with
    [
      _Ty=float
    ]

It seems that my list doesn’t like me using pointers in that way. Vectors would be fine with it, but I can’t use them because of the iterator being invalidated when you make an insertion - for the first loop it’s not a problem because I only need to insert once, but for the later loops I will be inserting multiple values.

I suppose I could get around this by doing multiple increments and decrements of the iterator to get it to the positions I want, but that comes across as a bit of a kludge and I’d rather avoid hacking my code around in that way.

065f0635a4c94d685583c20132a4559d
0
Ed_Mack 101 Jul 17, 2005 at 09:42
 list<float>::iterator    vIndex = terrain.begin();
 //vIndex++; // Remove this

 for( int b = 0; b < insertions; b++ )
 {
    float pointA = *vIndex;
    vIndex++;
    float pointC = *vIndex;

    // calculate new point, inserted at vIndex
    terrain.insert( vIndex, (pointA + pointC) / 2 );
 };

How about that? (BTW, before it stayed on the same point the whole time did it not?)

75c2c31bcca10ef21a86d5f5f49279d2
0
Tufty 101 Jul 17, 2005 at 09:46

@Ed Mack

 list<float>::iterator    vIndex = terrain.begin();
 //vIndex++; // Remove this

 for( int b = 0; b < insertions; b++ )
 {
    float pointA = *vIndex;
    vIndex++;
    float pointC = *vIndex;

    // calculate new point, inserted at vIndex
    terrain.insert( vIndex, (pointA + pointC) / 2 );
 };

How about that? (BTW, before it stayed on the same point the whole time did it not?)

[snapback]19050[/snapback]

Ed, you are great! Thanks, that’s fixed it. As usual I was looking too far past the problem and missing the easy answer. Just have to test it with a few more iterations now and fix any bugs that arise from that.