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

[Bradley Arsenault]

On 1/14/06, Nuage <address@hidden> wrote:
> 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.
>
Well, the block indendation, although I probably could fix it, I use
an auto-formatting program which saves me allot of time. I'll see what
I can do about it.

> 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)".
>

Queue uses a deque as an underlieing default container, so its O(1) for size.

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

Well I read up on this wavefront algorithm (which is the one used for
gradients), and it says put 0 for un-calculated square, which has the
side effect that unreachable squares are also 0, and use 1 for
obstacles. Put 2 at the destination, count up to the source. This is
yeah, sort of the opposite of what my class says, so yeah it may be a
lil confusing at first.

> 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 think it matters though, since all numbers are relitive, I'll
probably just add a switch to make it go on diagnols if desired.

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

I heard boost had a thing where you could use templates to select an
integer type based on the properties you want it to have, which would
certainly be the *most* portable solution, since not all systems may
have a 16 bit integer in the first place, those typedefs are from SDL
right?

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

I'm bad with bitwise math...

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

Yeah thats a mistake. I told you there was gonna be a bug!

> 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.
>
Bias woud go in the form of having it count up by 2's on land, but 3's
on water, so the lower numbers go to land, but if water is *that* much
shorter a distance, it will have the lowest numbers. I haven't
entirely solved the bias system yet, but it shouldn't be hard to
change.
> 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)
> >       {
Bloady bcpp, I might have to stop using it, its been giving me so much
trouble converting to the projects indent standards.
> >               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();
> >       }
> > }
>
>
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel
>

    With valor, honor, and a chess game on the table, Bradley Arsenault