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

[Bradley Arsenault]

I've just made a moderately major change to Nicowars construction
system, it has completely effected its play. I've switched it from a
system that polls the grid for the "best" section to a system that
uses gradients like castor does.

The gradient system overlays several gradients and a space
availability map, then examines every point of the map for the "best"
point. The gradients grow outwards from various sources, such as wood,
wheat, or other buildings, from 2 upwards, (1 is for obstacles, 0 is
for empty or unreachable). It then examines every point to see if its
a candidate best point, by getting its scores on the various gradients
and applying weights, summing them and then comparing it to the
current best score, if its score is lower, that means it has a better
average distance to all the things it needs, and thus that is a better
position for the building. If it is infact the current "best"
position, it then checks if a building is even able to be constructed
their, (I could have done this test first, but I figured the other
test would be lighter, and thus it should be done first). If a
building is able to be put in this spot, then it this spot is pushed
into a queue for random selection later.

Currently the system is quite buggy, and I won't be making a commit
soon. I would just like to come upon the knowledge of gradients of
nuage and nct for help on my update algorithm, and for any other tips.
My gradients use 16 bit integers, so I can apply basic bias to certain
terrains. I find castor chooses where it places its buildings very
well, so I decided to drop the grid polling system in favor of a
gradients system, which offers more flexibility in the features of the
map, and the ability to precompute easily. I've got my current
algorithms at the bottom of this email, its fairly trivial, and may
still contain a bug or two. It seems to work at a fairly fast speed,
unnoticable when I first started using it, all the real time is spent
examing the gradients through getHeight and finding out where to place
a building.

And as a side note, once I'm done all the actual coding of Nicowar,
I'm going to want to have someone, preferably not me, fine tune
nicowar, the extensive variability in nicowars constants can change
its behaviour and performance dramatically. This is probably about a
half a month away, anyone want to volunteer themselves 2 weeks in
advance?



Simple gradient system:


        ///This class serves as an adaptable full map gradient.
        class Gradient
        {
                public:
                        ///This enum holds anything that can be a source in the 
gradient
                        enum Sources
                        {
                                VillageCenter=1<<0,
                                Wheat=1<<1,
                                Wood=1<<2,
                                Stone=1<<3,
                                TeamBuildings=1<<4,
                        };

                        ///This enum holds anything that can be an obstacle in 
the gradient
                        enum Obstacles
                        {
                                None=0,
                                Resource=1<<0,
                                Building=1<<1,
                        };


                        ///Constructs an invalid gradient
                        Gradient() {}
                        ///Constructs a new gredient
                        Gradient(Team* team, unsigned sources, unsigned 
obstacles);
                        ///Modifyies an existing gradient with new parameters
                        void reset(Team* team, unsigned sources, unsigned 
obstacles);
                        ///Updates the gradient from the given starting point 
outwards.
                        ///Resources count as obstacles
                        void update();
                        ///Gets the height of point x,y
                        unsigned getHeight(unsigned x, unsigned y);
                private:
                        bool isSource(unsigned x, unsigned y);
                        bool isObstacle(unsigned x, unsigned y);
                        unsigned width;
                        unsigned height;
                        unsigned sources;
                        unsigned obstacles;
                        Team* team;
                        Map* map;
                        std::vector<short int> gradient;
        };



Gradient::Gradient(Team* team, unsigned sources, unsigned obstacles) :
width(map->getW()), height(map->getH()), sources(sources),
obstacles(obstacles), team(team), map(team->map),
gradient(width*height)
{

}




void Gradient::reset(Team* aTeam, unsigned aSources, unsigned aObstacles)
{
        team=aTeam;
        map=team->map;
        sources=aSources;
        obstacles=aObstacles;
        width=map->getW();
        height=map->getH();
        gradient.resize(width*height);
}




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




unsigned Gradient::getHeight(unsigned x, unsigned y)
{
        return gradient[y*width+x]-1;
}




bool Gradient::isSource(unsigned x, unsigned y)
{
        if(sources&VillageCenter && static_cast<int>(x)==team->startPosX &&
static_cast<int>(y)==team->startPosY)
                return true;
        if(sources&Wheat && map->isRessourceTakeable(x, y, CORN))
                return true;
        if(sources&Wood && map->isRessourceTakeable(x, y, WOOD))
                return true;
        if(sources&Stone && map->isRessourceTakeable(x, y, STONE))
                return true;
        if(sources&TeamBuildings && map->getBuilding(x, y)!=NOGBID)
        {
                if(getBuildingFromGid(team->game, map->getBuilding(x, 
y))->owner==team)
                        return true;
        }
        return false;
}




bool Gradient::isObstacle(unsigned x, unsigned y)
{
        if(obstacles&Resource && map->isRessource(x, y))
                return true;
        if(obstacles&Building && map->getBuilding(x, y)!=NOGBID)
                return true;
        return false;
}