Re: [glob2-devel] Nicowar changed to gradients, requesting tips on update algorithm

[Nuage]

Hello


*Bad things*

Watch your indentation, please. You still have the block indentation going wrong
when there are two nested loops or branches. Look at the beginning of "void
Gradient::update()". I have comments for these loops, but I'll say these later.

I don't know how std::queue is fast or not. But I think "squares.size()" is
order "O(n)", which is slow, compair to "!squares.empty()" which is "O(1)".


*other things*

Maybe using gradients that goes up instead of down may confuse coding newbies,
which I don't care. Same thing for the special values "0" and "1" which are
differents than the other gradient system. Note that using gradients which goes
down allows you to compute gradients with smaller range, it's only faster.

You'r only updating the gradient in 4 directions instead of 8. This is quite
faster. It's not useable in the pathfinding algorithm. But I think it's pretty
smart for buildings enplacement. Just beware that it can imply some sub-optimal
emplacements.

I don't really mind, but you may prefer to explicitely say the bit size and sign
of the variables. For instance "Uint16" instead of "unsigned short".

You don't take advantage of any bit-wise operations. Maybe you prefer it this
way, but you could save some cpu time.

The gradient is signed, but I don't see where you use the negative values.

You only make updates on a case which has never been updated. This will not be a
problem while the gradients values in the "squares" queue are ordered. But if
you want to applay various "bias to certain terrains", you'll face bugs. Then
you'll need to check an upper and a lower bound, in order to be able to update a
square which has already been updated.

oh oh I have to go

Nuage


> void Gradient::update()
> {
>       std::fill(gradient.begin(), gradient.end(), 0);
>       std::queue<unsigned int> squares;
>       for(unsigned x=0; x<width; ++x)
>               for(unsigned y=0; y<height; ++y)
>       {
>               if(isObstacle(x, y))
>               {
>                       gradient[y*width+x]=1;
>                       continue;
>               }
>               if(isSource(x, y))
>               {
>                       gradient[y*width+x]=2;
>                       squares.push(y*width+x);
>                       continue;
>               }
>       }
> 
>       while(squares.size())
>       {
>               unsigned int square=squares.front();
>               unsigned int x=square%width;
>               unsigned int y=square/width;
>               int x1=x-1, x2=x+1, y1=y-1, y2=y+1;
>               if(x1<0)
>                       x1+=width;
>               if(x2>=static_cast<int>(width))
>                       x2-=width;
>               if(y1<0)
>                       y1+=height;
>               if(y2>=static_cast<int>(height))
>                       y2-=height;
>               if(gradient[y1*width+x1]==0)
>               {
>                       squares.push(y1*width+x1);
>                       gradient[y1*width+x1]=gradient[y*width+x]+1;
>               }
>               if(gradient[y1*width+x2]==0)
>               {
>                       squares.push(y1*width+x2);
>                       gradient[y1*width+x2]=gradient[y*width+x]+1;
>               }
>               if(gradient[y2*width+x1]==0)
>               {
>                       squares.push(y2*width+x1);
>                       gradient[y2*width+x1]=gradient[y*width+x]+1;
>               }
>               if(gradient[y2*width+x2]==0)
>               {
>                       squares.push(y2*width+x2);
>                       gradient[y2*width+x2]=gradient[y*width+x]+1;
>               }
>               squares.pop();
>       }
> }