C++ Divides

[Tufty]

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?

[Reedbeta]

Post code?

[Tufty]

Post code?
19034


#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 << " ";
};
};

[baldurk]

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 );
};
19040


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.

[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 );
};
19040


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.
19042


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.

[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?)

[Tufty]

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?)
19050


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.