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

       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"

---

pathfinder.cpp

Go to the documentation of this file.

//     ____                _       __               
//    / __ )____  _____   | |     / /___ ___________
//   / __  / __ \/ ___/   | | /| / / __ `/ ___/ ___/
//  / /_/ / /_/ (__  )    | |/ |/ / /_/ / /  (__  ) 
// /_____/\____/____/     |__/|__/\__,_/_/  /____/  
//                                              
//       A futuristic real-time strategy game.
//          This file is part of Bos Wars.
//
//
//      I use breadth-first.
//
//      (c) Copyright 1998-2007 by Lutz Sammer, Russell Smith
//
//      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 "stratagus.h"
#include "map.h"
#include "unittype.h"
#include "unit.h"
#include "pathfinder.h"

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

static unsigned char Matrix[(MaxMapWidth + 2) * (MaxMapHeight + 3) + 2];  

static int STDCALL CostMoveTo(int x, int y, void *data);

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

void InitPathfinder()
{
    InitAStar(Map.Info.MapWidth, Map.Info.MapHeight, CostMoveTo);
}

void FreePathfinder()
{
    FreeAStar();
}

static void InitMatrix(unsigned char *matrix)
{
    unsigned i;
    unsigned w;
    unsigned h;
    unsigned e;

    w = Map.Info.MapWidth + 2;
    h = Map.Info.MapHeight;

    i = w + w + 1;
    memset(matrix, 98, i);          // +1 for ships!
    memset(matrix + i, 0, w * h);   // initialize matrix

    for (e = i + w * h; i < e;) {   // mark left and right border
        matrix[i] = 98;
        i += w;
        matrix[i - 1] = 98;
    }
    memset(matrix + i, 98, w + 1);  // +1 for ships!
}

unsigned char *CreateMatrix(void)
{
    InitMatrix(Matrix);
    return Matrix;
}

unsigned char *MakeMatrix(void)
{
    unsigned char *matrix;

    matrix = new unsigned char[(Map.Info.MapWidth + 2) * (Map.Info.MapHeight + 3) + 2];
    InitMatrix(matrix);

    return matrix;
}

/*----------------------------------------------------------------------------
--  PATH-FINDER USE
----------------------------------------------------------------------------*/

int PlaceReachable(const CUnit *src, int x, int y, int w, int h, int minrange, int range)
{
    int i = AStarFindPath(src->X, src->Y, x, y, w, h,
        src->Type->TileWidth, src->Type->TileHeight, minrange, range, NULL, 0, (void *)src);

    switch (i) {
        case PF_FAILED:
        case PF_UNREACHABLE:
        case PF_REACHED:
            i = 0;
            break;
        case PF_WAIT:
            Assert(0);
            i = 0;
            break;
        case PF_MOVE:
            break;
        default:
            break;
    }

    return i;
}

int UnitReachable(const CUnit *src, const CUnit *dst, int range)
{
    int depth;

    //
    //  Find a path to the goal.
    //
    depth = PlaceReachable(src, dst->X, dst->Y, dst->Type->TileWidth, dst->Type->TileHeight, 0, range);
    if (depth <= 0) {
        return 0;
    }

    return depth;
}

static int STDCALL CostMoveTo(int x, int y, void *data)
{
    int i;
    int j;
    int flag;
    int cost = 0;
    CUnit *goal;
    const CUnit *unit = (const CUnit *)data;
    int mask = unit->Type->MovementMask;

    cost = 0;

    // Doesn't cost anything to move to ourselves :)
    // Used when marking goals mainly.  Could cause speed problems
    if (unit->X == x && unit->Y == y) {
        return 0;
    }

    // verify each tile of the unit.
    for (i = x; i < x + unit->Type->TileWidth; ++i) {
        for (j = y; j < y + unit->Type->TileHeight; ++j) {
            flag = Map.Field(i, j)->Flags & mask;
            if (flag && (AStarKnowUnseenTerrain || Map.IsFieldExplored(unit->Player, i, j))) {
                if (flag & ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit)) {
                    // we can't cross fixed units and other unpassable things
                    return -1;
                }
                goal = UnitOnMapTile(i, j, unit->Type->UnitType);
                if (!goal) {
                    // Shouldn't happen, mask says there is something on this tile
                    Assert(0);
                    return -1;
                }
                if (goal->Moving)  {
                    // moving unit are crossable
                    cost += AStarMovingUnitCrossingCost;
                } else {
                    // for non moving unit Always Fail
                    // FIXME: Need support for moving a fixed unit to add cost
                    return -1;
                    //cost += AStarFixedUnitCrossingCost;
                }
            }
            // Add cost of crossing unknown tiles if required
            if (!AStarKnowUnseenTerrain && !Map.IsFieldExplored(unit->Player, i, j)) {
                // Tend against unknown tiles.
                cost += AStarUnknownTerrainCost;
            }
            // Add tile movement cost
            cost += Map.Field(i, j)->Cost;
        }
    }
    return cost;
}

/*----------------------------------------------------------------------------
--  REAL PATH-FINDER
----------------------------------------------------------------------------*/

int NewPath(CUnit *unit)
{
    int i;
    int gw;
    int gh;
    int gx;
    int gy;
    int minrange;
    int maxrange;
    char *path;

    if (unit->Orders[0]->Goal) {
        gw = unit->Orders[0]->Goal->Type->TileWidth;
        gh = unit->Orders[0]->Goal->Type->TileHeight;
        gx = unit->Orders[0]->Goal->X;
        gy = unit->Orders[0]->Goal->Y;
        maxrange = unit->Orders[0]->Range;
        minrange = unit->Orders[0]->MinRange;
    } else {
        // Take care of non square goals :)
        // If goal is non square, range states a non-existant goal rather
        // than a tile.
        gw = unit->Orders[0]->Width;
        gh = unit->Orders[0]->Height;
        maxrange = unit->Orders[0]->Range;
        minrange = unit->Orders[0]->MinRange;
        // Large units may have a goal that goes outside the map, fix it here
        if (unit->Orders[0]->X + unit->Type->TileWidth - 1 >= Map.Info.MapWidth) {
            unit->Orders[0]->X = Map.Info.MapWidth - unit->Type->TileWidth;
        }
        if (unit->Orders[0]->Y + unit->Type->TileHeight - 1 >= Map.Info.MapHeight) {
            unit->Orders[0]->Y = Map.Info.MapHeight - unit->Type->TileHeight;
        }
        gx = unit->Orders[0]->X;
        gy = unit->Orders[0]->Y;
    }
    path = unit->Data.Move.Path;
    i = AStarFindPath(unit->X, unit->Y, gx, gy, gw, gh,
        unit->Type->TileWidth, unit->Type->TileHeight, minrange, maxrange, path, MAX_PATH_LENGTH, unit);
    if (i == PF_FAILED) {
        i = PF_UNREACHABLE;
    }

    // Update path if it was requested. Otherwise we may only want
    // to know if there exists a path.

    if (path != NULL) {
        if (i >= MAX_PATH_LENGTH) {
            unit->Data.Move.Length = MAX_PATH_LENGTH;
        } else {
            unit->Data.Move.Length = i;
        }
        if (unit->Data.Move.Length == 0) {
            ++unit->Data.Move.Length;
        }
    }
    return i;
}

int NextPathElement(CUnit *unit, int *pxd, int *pyd)
{
    int result;

    // Attempt to use path cache
    // FIXME: If there is a goal, it may have moved, ruining the cache
    *pxd = 0;
    *pyd = 0;

    // Goal has moved, need to recalculate path or no cached path
    if (unit->Data.Move.Length <= 0 ||
        (unit->Orders[0]->Goal && (unit->Orders[0]->Goal->X != unit->Orders[0]->X ||
            unit->Orders[0]->Goal->Y != unit->Orders[0]->Y))) {
        result = NewPath(unit);

        if (result == PF_UNREACHABLE) {
            unit->Data.Move.Length = 0;
            return result;
        }
        if (result == PF_REACHED) {
            return result;
        }
        if (unit->Goal) {
            // Update Orders
            unit->Orders[0]->X = unit->Goal->X;
            unit->Orders[0]->Y = unit->Goal->Y;
        }
    }

    *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
    *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
    result = unit->Data.Move.Length;
    unit->Data.Move.Length--;
    if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) {
        // If obstructing unit is moving, wait for a bit.
        if (unit->Data.Move.Fast) {
            unit->Data.Move.Fast--;
            AstarDebugPrint("WAIT at %d\n" _C_ unit->Data.Move.Fast);
            result = PF_WAIT;
        } else {
            unit->Data.Move.Fast = 10;
            AstarDebugPrint("SET WAIT to 10\n");
            result = PF_WAIT;
        }
        if (unit->Data.Move.Fast == 0 && result != 0) {
            AstarDebugPrint("WAIT expired\n");
            result = NewPath(unit);
            if (result > 0) {
                *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
                *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
                if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) {
                    // There may be unit in the way, Astar may allow you to walk onto it.
                    result = PF_UNREACHABLE;
                    *pxd = 0;
                    *pyd = 0;
                } else {
                    result = unit->Data.Move.Length;
                    unit->Data.Move.Length--;
                }
            }
        }
    }
    if (result != PF_WAIT) {
        unit->Data.Move.Fast = 0;
    }
    return result;
}

---