____                _       __
    / __ )____  _____   | |     / /___ ___________
   / __  / __ \/ ___/   | | /| / / __ `/ ___/ ___/
  / /_/ / /_/ (__  )    | |/ |/ / /_/ / /  (__  )
 /_____/\____/____/     |__/|__/\__,_/_/  /____/

       A futuristic real-time strategy game.
          This file is part of Bos Wars.

(C) Copyright 2001-2007 by the Bos Wars and Stratagus Project. Distributed under the "GNU General Public License"

---

ai_plan.cpp

Go to the documentation of this file.

//     ____                _       __               
//    / __ )____  _____   | |     / /___ ___________
//   / __  / __ \/ ___/   | | /| / / __ `/ ___/ ___/
//  / /_/ / /_/ (__  )    | |/ |/ / /_/ / /  (__  ) 
// /_____/\____/____/     |__/|__/\__,_/_/  /____/  
//                                              
//       A futuristic real-time strategy game.
//          This file is part of Bos Wars.
//
//
//      (c) Copyright 2002-2005 by Lutz Sammer and Jimmy Salmon
//
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of the GNU General Public License as published by
//      the Free Software Foundation; only version 2 of the License.
//
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.
//
//      You should have received a copy of the GNU General Public License
//      along with this program; if not, write to the Free Software
//      Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
//      02111-1307, USA.
//


/*----------------------------------------------------------------------------
--  Includes
----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#include "stratagus.h"
#include "missile.h"
#include "unittype.h"
#include "unit_cache.h"
#include "map.h"
#include "pathfinder.h"
#include "actions.h"
#include "ai_local.h"
#include "player.h"

/*----------------------------------------------------------------------------
--  Variables
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
--  Functions
----------------------------------------------------------------------------*/

static CUnit *EnemyOnMapTile(const CUnit *source, int tx, int ty)
{
    CUnit *table[UnitMax];
    CUnit *unit;
    CUnit *best;
    const CUnitType *type;
    int n;
    int i;

    n = UnitCache.Select(tx, ty, table, UnitMax);
    best = NoUnitP;
    for (i = 0; i < n; ++i) {
        unit = table[i];
        // unusable unit ?
        // if (unit->IsUnusable()) can't attack constructions
        // FIXME: did SelectUnitsOnTile already filter this?
        if (unit->Removed ||
                //(!UnitVisible(unit, source->Player)) ||
                unit->Orders[0]->Action == UnitActionDie) {
            continue;
        }
        type = unit->Type;
        if (tx < unit->X || tx >= unit->X + type->TileWidth ||
                ty < unit->Y || ty >= unit->Y + type->TileHeight) {
            continue;
        }
        if (!CanTarget(source->Type, unit->Type)) {
            continue;
        }
        if (!source->Player->IsEnemy(unit)) { // a friend or neutral
            continue;
        }
        //
        // Choose the best target.
        //
        if (!best || best->Type->Priority < unit->Type->Priority) {
            best = unit;
        }
    }
    return best;
}

static void AiMarkWaterTransporter(const CUnit *unit, unsigned char *matrix)
{
    static const int xoffset[] = { 0, -1, +1, 0, -1, +1, -1, +1 };
    static const int yoffset[] = { -1, 0, 0, +1, -1, -1, +1, +1 };
    struct p {
        unsigned short X;
        unsigned short Y;
    } *points;
    int size;
    int x;
    int y;
    int rx;
    int ry;
    int mask;
    int wp;
    int rp;
    int ep;
    int i;
    int w;
    unsigned char *m;

    x = unit->X;
    y = unit->Y;
    w = Map.Info.MapWidth + 2;
    matrix += w + w + 2;
    if (matrix[x + y * w]) { // already marked
        DebugPrint("Done\n");
        return;
    }

    size = Map.Info.MapWidth * Map.Info.MapHeight / 4;
    points = new p[size];

    //
    // Make movement matrix.
    //
    mask = unit->Type->MovementMask;
    // Ignore all possible mobile units.
    mask &= ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit);

    points[0].X = x;
    points[0].Y = y;
    rp = 0;
    matrix[x + y * w] = 66; // mark start point
    ep = wp = 1; // start with one point

    //
    // Pop a point from stack, push all neightbors which could be entered.
    //
    for (;;) {
        while (rp != ep) {
            rx = points[rp].X;
            ry = points[rp].Y;
            for (i = 0; i < 8; ++i) { // mark all neighbors
                x = rx + xoffset[i];
                y = ry + yoffset[i];
                m = matrix + x + y * w;
                if (*m) { // already checked
                    continue;
                }

                if (CanMoveToMask(x, y, mask)) { // reachable
                    *m = 66;
                    points[wp].X = x; // push the point
                    points[wp].Y = y;
                    if (++wp >= size) { // round about
                        wp = 0;
                    }
                    /* Must be checked multiple
                       } else { // unreachable
                       *m=99;
                     */
                }
            }

            if (++rp >= size) { // round about
                rp = 0;
            }
        }

        //
        // Continue with next frame.
        //
        if (rp == wp) { // unreachable, no more points available
            break;
        }
        ep = wp;
    }

    delete[] points;
}

static int AiFindTarget(const CUnit *unit, unsigned char *matrix, int *dx, int *dy,
    int *ds)
{
    static const int xoffset[] = { 0, -1, +1, 0, -1, +1, -1, +1 };
    static const int yoffset[] = { -1, 0, 0, +1, -1, -1, +1, +1 };
    struct p {
        unsigned short X;
        unsigned short Y;
        unsigned char State;
    } *points;
    int size;
    int x;
    int y;
    int rx;
    int ry;
    int mask;
    int wp;
    int rp;
    int ep;
    int i;
    int w;
    enum {
        OnWater,
        OnLand,
        OnIsle
    };
    unsigned char state;
    unsigned char *m;

    size = Map.Info.MapWidth * Map.Info.MapHeight / 4;
    points = new p[size];

    x = unit->X;
    y = unit->Y;

    w = Map.Info.MapWidth + 2;
    mask = unit->Type->MovementMask;
    // Ignore all possible mobile units.
    mask &= ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit);

    points[0].X = x;
    points[0].Y = y;
    points[0].State = OnLand;
    matrix += w + w + 2;
    rp = 0;
    matrix[x + y * w] = 1; // mark start point
    ep = wp = 1; // start with one point

    //
    // Pop a point from stack, push all neightbors which could be entered.
    //
    for (;;) {
        while (rp != ep) {
            rx = points[rp].X;
            ry = points[rp].Y;
            state = points[rp].State;
            for (i = 0; i < 8; ++i) { // mark all neighbors
                x = rx + xoffset[i];
                y = ry + yoffset[i];
                m = matrix + x + y * w;

                if (state != OnWater) {
                    if (*m) { // already checked
                        if (state == OnLand && *m == 66) { // tansporter?
                            DebugPrint("->Water\n");
                            *m = 6;
                            points[wp].X = x; // push the point
                            points[wp].Y = y;
                            points[wp].State = OnWater;
                            if (++wp >= size) { // round about
                                wp = 0;
                            }
                        }
                        continue;
                    }
                    // Check targets on tile?
                    // FIXME: the move code didn't likes a shore building as
                    //  target
                    if (EnemyOnMapTile(unit, x, y)) {
                        DebugPrint("Target found %d,%d-%d\n" _C_ x _C_ y _C_ state);
                        *dx = x;
                        *dy = y;
                        *ds = state;
                        delete[] points;
                        return 1;
                    }

                    if (CanMoveToMask(x, y, mask)) { // reachable

                        *m = 1;
                        points[wp].X = x; // push the point
                        points[wp].Y = y;
                        points[wp].State = state;
                        if (++wp >= size) { // round about
                            wp = 0;
                        }
                    } else { // unreachable
                        *m = 99;
                    }
                } else { // On water
                    if (*m) { // already checked
                        if (*m == 66) { // tansporter?
                            *m = 6;
                            points[wp].X = x; // push the point
                            points[wp].Y = y;
                            points[wp].State = OnWater;
                            if (++wp >= size) { // round about
                                wp = 0;
                            }
                        }
                        continue;
                    }
                    if (CanMoveToMask(x, y, mask)) { // reachable
                        DebugPrint("->Land\n");
                        *m = 1;
                        points[wp].X = x; // push the point
                        points[wp].Y = y;
                        points[wp].State = OnIsle;
                        if (++wp >= size) { // round about
                            wp = 0;
                        }
                    } else { // unreachable
                        *m = 99;
                    }
                }
            }

            if (++rp >= size) { // round about
                rp = 0;
            }
        }

        //
        // Continue with next frame.
        //
        if (rp == wp) { // unreachable, no more points available
            break;
        }
        ep = wp;
    }
    delete[] points;
    return 0;
}

int AiPlanAttack(AiForce *force)
{
    unsigned char *watermatrix;
    const CUnit *aiunit = NULL;
    int x;
    int y;
    int i;
    int state;
    CUnit *transporter;

    DebugPrint("Planning for force #%lu of player #%d\n" _C_
        static_cast<long unsigned int> (force - AiPlayer->Force) _C_ AiPlayer->Player->Index);

    watermatrix = CreateMatrix();

    //
    // Transporter must be already assigned to the force.
    // NOTE: finding free transportes was too much work for me.
    //
    state = 1;
    for (i = 0; i < (int)force->Units.size(); ++i) {
        aiunit = force->Units[i];
        if (aiunit->Type->CanTransport) {
            DebugPrint("Transporter #%d\n" _C_ UnitNumber(aiunit));
            AiMarkWaterTransporter(aiunit, watermatrix);
            state = 0;
        }
    }

    //
    // No transport that belongs to the force.
    //
    transporter = NULL;
    if (state) {
        for (i = 0; i < AiPlayer->Player->TotalNumUnits; ++i) {
            CUnit *unit;

            unit = AiPlayer->Player->Units[i];
            if (unit->Type->CanTransport && unit->IsIdle()) {
                DebugPrint("Assign any transporter\n");
                AiMarkWaterTransporter(unit, watermatrix);
                // FIXME: can be the wrong transporter.
                transporter = unit;
                state = 0;
            }
        }
    }

    if (state) { // Absolute no transporter
        DebugPrint("No transporter available\n");
        // FIXME: should tell the resource manager we need a transporter!
        return 0;
    }
    //
    // Find a land unit of the force.
    // FIXME: if force is split over different places -> broken
    //
    for (i = 0; i < (int)force->Units.size(); ++i) {
        aiunit = force->Units[i];
        if (aiunit->Type->UnitType == UnitTypeLand) {
            DebugPrint("Land unit %d\n" _C_ UnitNumber(aiunit));
            break;
        }
    }
    if (i == (int)force->Units.size()) {
        DebugPrint("No land unit in force\n");
        return 0;
    }

    if (AiFindTarget(aiunit, watermatrix, &x, &y, &state)) {
        if (transporter) {
            force->Units.insert(force->Units.begin(), transporter);
            transporter->RefsIncrease();
        }

        DebugPrint("Can attack\n");
        force->GoalX = x;
        force->GoalY = y;
        force->MustTransport = state == 2;

        force->State = 1;
        return 1;
    }
    return 0;
}

void AiSendExplorers(void)
{
    AiExplorationRequest *request;
    int requestcount;
    int requestid;
    int centerx;
    int centery;
    int x;
    int y;
    int i;
    int targetok;
    int ray;
    int trycount;
    int outtrycount;

    CUnit **unit;
    CUnitType *type;
    CUnit *bestunit;
    int distance;
    int bestdistance;
    int flyeronly;

    // Count requests...
    requestcount = AiPlayer->FirstExplorationRequest.size();

    // Nothing => abort
    if (!requestcount) {
        return;
    }

    outtrycount = 0;
    do {
        bestunit = 0;
        ++outtrycount;

        // Choose a request
        requestid = SyncRand() % requestcount;
        request = &AiPlayer->FirstExplorationRequest[requestid];

        // Choose a target, "near"
        centerx = request->X;
        centery = request->Y;
        ray = 3;
        trycount = 0;

        do {
            targetok = 0;

            x = centerx + SyncRand() % (2 * ray + 1) - ray;
            y = centery + SyncRand() % (2 * ray + 1) - ray;

            if (x >= 0 && y >= 0 && x < Map.Info.MapWidth && y < Map.Info.MapHeight) {
                targetok = !Map.IsFieldExplored(AiPlayer->Player, x, y);
            }

            ray = 3 * ray / 2;
            ++trycount;
        } while (trycount < 8 && !targetok);

        if (!targetok) {
            continue;
        }

        // We have an unexplored tile in sight (x,y)

        // Find an idle unit, responding to the mask
        flyeronly = 0;
        bestdistance = -1;

        unit = AiPlayer->Player->Units;
        for (i = AiPlayer->Player->TotalNumUnits; i > 0; ++unit) {
            --i;

            if (!(*unit)->IsIdle()) {
                continue;
            }

            if ((*unit)->X == -1 || (*unit)->Y == -1) {
                continue;
            }

            type = (*unit)->Type;

            if (!CanMove(*unit)) {
                continue;
            }

            if (type->UnitType != UnitTypeFly) {
                if (flyeronly) {
                    continue;
                }
                if ((request->Mask & MapFieldLandUnit) && type->UnitType != UnitTypeLand) {
                    continue;
                }
                if ((request->Mask & MapFieldSeaUnit) && type->UnitType != UnitTypeNaval) {
                    continue;
                }
            } else {
                flyeronly = 1;
            }

            distance = ((*unit)->X - x) * ((*unit)->X - x) + ((*unit)->Y - y) * ((*unit)->Y - y);
            if (bestdistance == -1 || distance <= bestdistance ||
                    (bestunit->Type->UnitType != UnitTypeFly && type->UnitType == UnitTypeFly)) {
                bestdistance = distance;
                bestunit = (*unit);
            }
        }
    } while (outtrycount <= 4 && !bestunit);

    if (bestunit) {
        CommandMove(bestunit, x, y, FlushCommands);
        AiPlayer->LastExplorationGameCycle = GameCycle;
    }

    // Remove all requests
    AiPlayer->FirstExplorationRequest.clear();
}

---