6 replies to this topic

[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]

Reedbeta said:

Post code?

#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]

Tufty said:

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

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]

baldurk said:

Tufty said:

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

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.

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]

Ed Mack said:

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

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.