map.cpp

/***************************************************************************
                           map.cpp
                           -------------------
    begin                : 2004-04-16
    copyright            : (C) 2004-2005 by Michael Menne
    email                : menne@users.sourceforge.net
 ***************************************************************************/

/***************************************************************************
 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; either version 2
 of the License, or (at your option) any later version.

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

#include "map.h"
#include <stdio.h>
#include <math.h>
#include <set>

#include "app.h"
#include "frame.h"
#include "glcanvas.h"
#include "profilemanager.h"
#include "parser.h"

extern ofstream logFile;

namespace WDS
{

DECLARE_APP(CApp)

// Direction Table for Paths
int g_DirTable[8][3] = {
// x   y  WDS-Keypad
{  0, -1, 8},       // oben
{  1,  0, 6},       // rechts
{  0,  1, 2},       // unten
{ -1,  0, 4},       // links
{  1, -1, 9},       // rechts-oben
{  1,  1, 3},       // rechts-unten
{ -1,  1, 1},       // links-unten
{ -1, -1, 7} };     // links-oben


/*----------------------------------------------------------------------------/
    Constructor / Destructor
-----------------------------------------------------------------------------*/

CMap::CMap()
{
    m_nMapWidth  = 0;
    m_nMapHeigth = 0;
    m_rcBounds = Rect(0, 0, 0, 0);

    m_pDlgPath = NULL;
}

CMap::~CMap()
{
    Clear( );

    // Pfad-Dialog löschen
    if( m_pDlgPath )
    {
        delete m_pDlgPath;
        m_pDlgPath = NULL;
    }
}

void CMap::Clear( )
{
    m_aTiles.clear();
    m_aTowns.clear();
    m_nMapWidth  = 0;
    m_nMapHeigth = 0;
    m_rcBounds = Rect( 0, 0, 0, 0);
}

/*----------------------------------------------------------------------------/
    Lade Funktionen
-----------------------------------------------------------------------------*/

bool CMap::Load( const wxString& strTerrain, const wxString& strTowns )
{
    // if CMap::Load is called, we can be sure that p != NULL
    CProfile* p = CProfileManager::GetCurrentProfile();
    wxBusyInfo waitInfo( "Bitte warten, lade Profil \"" + p->GetName()
        + "\".\nDies kann je nach PC ein paar Sekunden dauern.");

    // Alte Karte loeschen
    Clear( );

    // Terrain laden
    if( !LoadTerrain( strTerrain ) )
        return false;

    // Towns laden
    if( !LoadTowns( strTowns ) )
        return false;

    return true;
}

bool CMap::Update( const string strUpdate )
{
    CParser parser;
    parser.StartParseString( strUpdate.c_str() );

    // Solange parsen, bis nichts mehr da ist
    while( parser.NextToken( true ) )
    {
        // X-Koordinate
        int x = atoi( parser.Token() );

        // Y-Koordinate
        if( !parser.NextToken( false ) ) continue;
        int y = atoi( parser.Token() );

        m_aTiles[x][y].Reset(); // reset data for that tile
        m_aTowns.erase(x, y);   // and remove town if it exists

        // [BUILDING]
        if( !parser.NextToken( false ) ) continue;
        m_aTiles[x][y].SetBuilding( atoi(parser.Token()) );

        // [BORDERS]
        if( !parser.NextToken( false ) ) continue;
        m_aTiles[x][y].SetBorder( atoi(parser.Token()) );

        // [STREETS]
        if( !parser.NextToken( false ) ) continue;
        m_aTiles[x][y].SetStreet( atoi(parser.Token()) );

        // [UNITS]
        if( !parser.NextToken( false ) ) continue;

        // extract the units and set them
        int units = atoi(parser.Token());
        if (units & 0x1) m_aTiles[x][y].SetUnit( 1 );
        if (units & 0x2) m_aTiles[x][y].SetUnit( 2 );
        if (units & 0x4) m_aTiles[x][y].SetUnit( 3 );
        if (units & 0x8) m_aTiles[x][y].SetUnit( 4 );

        // [FOW] (fog of war)
        if( !parser.NextToken( false ) ) continue;
        m_aTiles[x][y].SetFogOfWar( atoi(parser.Token()) );

        // [SIGHT]
        if( !parser.NextToken( false ) ) continue;


        // ok, now we *know* that at x, y is a town, so add entry to town array
        // and create needed variables.
        wxString strName = "", strGuild = "", strOwner = "";
        m_aTowns.set( x, y, CTown() );
        CTown* pTown = m_aTowns.get( x, y ); // get pointer to the new town

        pTown->SetPos( x, y );
        pTown->SetSight( atoi(parser.Token()) );

        // [TOWN_NAME]
        if( parser.NextToken( false ) ) strName = parser.Token();

        // [PLAYER_NAME]
        if( parser.NextToken( false ) ) strOwner = parser.Token();

        // [GUILD]
        if( parser.NextToken( false ) ) strGuild = parser.Token();

        pTown->SetName( strName, strOwner, strGuild );


        parser.SkipLine( ); // Rest der Zeile überspringen
    }

    return true;
}

bool CMap::LoadTerrain( const wxString& strFile )
{
    if( strFile.IsEmpty() )
        return false;

    wxStopWatch sw;
    logFile << "Loading terrrain..." << endl;

    // Input Datei oeffnen
    FILE *pFile = fopen( strFile.c_str(), "r" );    // FILE ist schneller als ifstream!
    if( pFile == NULL )
    {
        logFile << "Konnte Kartendatei '" << strFile.c_str() << "' nicht laden. Bitte 'mapfile' Eintrag in config.cfg überprüfen." << endl;
        return false;
    }

    // Größe der Datei abfragen
    fseek( pFile, 0L, SEEK_END );
    int nSize = ftell( pFile );
    rewind( pFile );

    // Speicher für die CSV-Daten reservieren
    BYTE *pFelder = new BYTE[nSize];
    memset( pFelder, 0, nSize );

    // CSV-Daten einlesen
    int mx, my  = 1;
    int nFields = 0;
    while( !feof( pFile ) )
    {
        char c = getc( pFile );

        if( c >= '0' && c <= '9' )  // Is c a number?
        {
            pFelder[nFields++] = (BYTE)(c-'0');
        }
        else if( c == '\n' )
        {
            my++;
        }
    }
    fclose( pFile );

    // Breite der Karte berechnen
    mx = nFields / my;

    // Speicher für die Karte reservieren
    m_nMapWidth  = mx;
    m_nMapHeigth = my;
    m_aTiles = MapArray( mx, vector<CTile>(my) );

    // Die genauen Bilder aus den CSV-Daten brechnen
    int nTiles = 0;
    int x, y;
    for (  y = 1; y < my-1; y++)
    {
        for ( x = 1; x < mx-1; x++ )
        {
            int nBorder = 0;
            int nID     = pFelder[x + y*mx];

            if ( pFelder[x   + (y-1) * mx] != nID ) nBorder = nBorder + 1;  // Oben
            if ( pFelder[x+1 +  y    * mx] != nID ) nBorder = nBorder + 2;  // Rechts
            if ( pFelder[x   + (y+1) * mx] != nID ) nBorder = nBorder + 4;  // Unten
            if ( pFelder[x-1 +  y    * mx] != nID ) nBorder = nBorder + 8;  // Links

            if (( nBorder & (1+8)) == 0)
                if ( pFelder[x-1 + (y-1)*mx] != nID ) nBorder += 16;

            if (( nBorder & (1+2)) == 0)
                if ( pFelder[x+1 + (y-1)*mx] != nID ) nBorder += 32;

            if (( nBorder & (2+4)) == 0)
                if ( pFelder[x+1 + (y+1)*mx] != nID ) nBorder += 64;

            if (( nBorder & (4+8)) == 0)
                if ( pFelder[x-1 + (y+1)*mx] != nID ) nBorder += 128;

            m_aTiles[x][y].SetTerrain( nID, nBorder );
            nTiles++;
        }
    }

    // CSV-Daten löschen
    delete [] pFelder;


    // Rahmen hinzufügen
    for( x = 1; x < mx-1; x++ ) // Obenere und untenere Leiste des Rahmens
    {
        m_aTiles[x][0].SetFrame( 3 );      // Oben
        m_aTiles[x][my-1].SetFrame( 6 ); // Unten
    }

    for( y=1; y<my-1; y++ )     // Linke und rechte Leiste des Rahmens
    {
        m_aTiles[0][y].SetFrame( 1 );    // Links
        m_aTiles[mx-1][y].SetFrame( 2 ); // Rechts
    }

    // Ecken des Rahmen
    m_aTiles[0][0].SetFrame( 4 );         // Oben links
    m_aTiles[mx-1][0].SetFrame( 5 );      // Oben rechts
    m_aTiles[mx-1][my-1].SetFrame( 8 ); // Unten rechts
    m_aTiles[0][my-1].SetFrame( 7 );    // Unten links

    // Umgebungs-Box berechnen
    int t = 70;
    int l = (0-(my-2)) * 63;
    int r = (mx-0) * 63;
    int b = (my+mx) * 35;
    m_rcBounds.x = l;
    m_rcBounds.y = t;
    m_rcBounds.w = r-l;
    m_rcBounds.h = b-t;
    m_rcBounds.Inflate( 100, 100 );

    logFile << "-> " << nFields << " terrain tiles loaded in " << sw.Time() << " ms." <<  endl;

    return true;
}

bool CMap::LoadTowns( const wxString& strFile )
{
    if( strFile.IsEmpty() )
        return false;

    // Input Datei öffnen
    ifstream infile( strFile.c_str() );
    if ( infile.fail() )
    {
        logFile << "Konnte Datendatei '" << strFile.c_str() << "' nicht laden. Bitte 'datfile' Eintrag in config.cfg überprüfen." << endl;
        return false;
    }

    char   c;
    string strToken;
    while( !infile.eof() )
    {
        infile >> c;
        if( c == '[' )
        {
            infile >> strToken;

            if( strToken.find( "buildings" ) != string::npos )
                LoadBuildings( infile );

            else if( strToken.find( "border" ) != string::npos )
                LoadBorders( infile );

            else if( strToken.find( "units" ) != string::npos )
                LoadUnits( infile );

            else if( strToken.find( "streets" ) != string::npos )
                LoadStreets( infile );

            else if( strToken.find( "towns" ) != string::npos )
                LoadTowns( infile );
        }

    }

    infile.close();

    return true;
}

bool CMap::LoadBuildings( ifstream &infile )
{
    wxStopWatch sw;
    logFile << "Loading buildings..." << endl;

    int x, y, n;
    int nBuildings = 0;
    while( 1 )
    {
        eatwhite( infile );
        if( infile.eof() || infile.peek() == '[')
            break;

        infile >> x >> y >> n;

        m_aTiles[x][y].SetBuilding( n );
        nBuildings++;
    }

    logFile << "-> " << nBuildings << " buildings loaded in " << sw.Time() << " ms." << endl;

    return true;
}

bool CMap::LoadBorders( ifstream &infile )
{
    wxStopWatch sw;
    logFile << "Loading borders..." << endl;

    int x, y, n;
    int nBorders = 0;
    while( 1 )
    {
        eatwhite( infile );
        if( infile.eof() || infile.peek() == '[')
            break;

        infile >> x >> y >> n;
        m_aTiles[x][y].SetBorder( n );
        nBorders++;
    }

    logFile << "-> " << nBorders << " borders loaded in " << sw.Time() << " ms." << endl;

    return true;
}

bool CMap::LoadUnits( ifstream &infile )
{
    wxStopWatch sw;
    logFile << "Loading units..." << endl;

    int x, y, n;
    int nUnits = 0;
    while( 1 )
    {
        eatwhite( infile );
        if( infile.eof() || infile.peek() == '[')
            break;

        infile >> x >> y >> n;
        m_aTiles[x][y].SetUnit( n );
        nUnits++;
    }

    logFile << "-> " << nUnits << " units loaded in " << sw.Time() << " ms." << endl;

    return true;
}

bool CMap::LoadStreets( ifstream &infile )
{
    wxStopWatch sw;
    logFile << "Loading streets..." << endl;

    int x, y, n;
    int nStreets = 0;
    while( 1 )
    {
        eatwhite( infile );
        if( infile.eof() || infile.peek() == '[')
            break;

        infile >> x >> y >> n;
        m_aTiles[x][y].SetStreet( n );
        nStreets++;
    }

    logFile << "-> " << nStreets << " streets loaded in " << sw.Time() << " ms." << endl;

    return true;
}

/*
 *  LoadTowns( )
 *  Bsp.: 344 372 "Coronet" "Smir" "[BDS]"
 */
bool CMap::LoadTowns( ifstream &infile )
{
    wxStopWatch sw;
    logFile << "Loading towns..." << endl;

    int x, y;
    char buf[64], c;
    wxString strName, strOwner, strGuild;
    int nTowns = 0;
    CTown town;
    while( 1 )
    {
        eatwhite( infile );
        if( infile.eof() || infile.peek() == '[')
            break;

        infile >> x >> y;

        infile >> c;            // c ist "
        infile.getline(buf, 63, '"' );
        strName = buf;

        infile >> c;
        infile.getline(buf, 63, '"' );
        strOwner = buf;

        infile >> c;
        infile.getline(buf, 63, '"' );
        strGuild = buf;

        town.SetName( strName, strOwner, strGuild );
        town.SetPos( x, y );
        m_aTowns.set( x, y, town );
        nTowns++;
    }

    logFile << "-> " << nTowns << " towns loaded in " << sw.Time() << " ms." << endl;

    return true;
}


/*----------------------------------------------------------------------------/
    Zeichen Funktionen
-----------------------------------------------------------------------------*/

void CMap::Draw()
{
    int x, y;
    CGLCanvas *pCanvas = GetGLCanvas();
    CProfile *pProfile = CProfileManager::GetCurrentProfile( );
    bool bFOW = pProfile->GetFogOfWar( );
    Rect rcScreen = pCanvas->GetVisibleRect();
    Rect rcTile( 0, 0, 126, 105 );

    int sx = GetFieldAtPoint( rcScreen.x, rcScreen.y ).x;                                   // Top-Left
    int mx = GetFieldAtPoint( rcScreen.x + rcScreen.w + 128, rcScreen.y + rcScreen.h ).x;   // Botton-Right

    int sy = GetFieldAtPoint( rcScreen.x + rcScreen.w, rcScreen.y ).y;          // Top-Right
    int my = GetFieldAtPoint( rcScreen.x, rcScreen.y + rcScreen.h + 128 ).y;    // Bottom-Left

    // Draw visible region
    for ( y=sy; y<my; y++ )
    {
        for ( x=sx; x<mx; x++ )
        {
            rcTile.x = (x-y) * 63;
            rcTile.y = (y+x) * 35;

            if( rcScreen.RectIntersect( &rcTile ) )
            {
                m_aTiles[x][y].Draw( rcTile, bFOW );
            }
        }
    }

    // Draw overlays
    for ( y=sy; y<my; y++ )
    {
        for ( x=sx; x<mx; x++ )
        {
            rcTile.x = (x-y) * 63;
            rcTile.y = (y+x) * 35;

            if( rcScreen.RectIntersect( &rcTile ) )
            {
                m_aTiles[x][y].DrawOverlay( rcTile );
            }
        }
    }

    // Werte für das zeichnen der Städtenamen aus der Configdatei auslesen
    bool   bShowTownNames;
    double fHideTownNames;
    wxConfigBase::Get()->SetPath( "/General" );
    wxConfigBase::Get()->Read( "show_town_names", &bShowTownNames, true );  // ???
    wxConfigBase::Get()->Read( "hide_town_names", &fHideTownNames, 0.2 );   // TODO: Bloeder Name.

    // Städtenamen zeichnen.
    if( bShowTownNames && pCanvas->GetZoom() > fHideTownNames ) // Keine Namen wenn zu weit weggezoomt!
    {
        CTown* pTown = m_aTowns.firstSibling();

        while ( pTown != 0L ) {
            // Jeder Stadtname wird gegen den sichtbaren Bereich getestet.
            // Dies ist nicht schnell, geht aber bei den wenigen Städten die wir haben.
            pTown->Draw( &rcScreen );

            pTown = m_aTowns.nextSibling();
        }
    }
}

/*----------------------------------------------------------------------------/
    Pfadfinde Funktionen
-----------------------------------------------------------------------------*/

/*
 *  FindPath
 *  Bei Erfolg wird die Länge des Pfades zurückgegeben, sonst -1
 */
bool CMap::FindPath( int sx, int sy, int ex, int ey )
{
    wxBusyCursor bc;

    // Testen ob Start und Endpunkte erreichbar sind
    if( !IsValidField( sx, sy ) ||
        !IsValidField( ex, ey ) )
    {
        wxMessageBox( "Start oder Ziel ist nicht erreichbar!", "Fehler" );
        return false;
    }

    // Tilearray zurücksetzen
    for(int y=0; y<m_nMapHeigth; y++ )
    {
        for(int x=0; x<m_nMapWidth; x++ )
        {
            m_aTiles[x][y].m_Parent = -1;
            m_aTiles[x][y].m_CostF  = 0;
            m_aTiles[x][y].m_CostG  = 0;
            m_aTiles[x][y].m_State  = PATH_NONE;
        }
    }

    wxStopWatch sw;
    bool bRet = AStar( sx, sy, ex, ey );
    sw.Pause();

    if( bRet )
    {
        wxString strPath;

        // Den Weg vom Ziel zum Start zurückverfolgen und markieren
        CTile *pTile;
        float  fCost = 0.0f;
        int    x = ex;
        int    y = ey;
        int    nParent;

        while( 1 )
        {
            pTile = &m_aTiles[x][y];
            pTile->m_State = PATH_ACTIVE;   // Liegt auf dem Weg
            nParent = pTile->m_Parent;

            // Abbrechen wenn wir am Startknoten angekommen sind
            if( nParent == -1 )
                break;

            x -= g_DirTable[nParent][0];
            y -= g_DirTable[nParent][1];
            fCost += pTile->GetWeigth();

            // Pfadstring zusammensetzen
            strPath = ((char)(g_DirTable[nParent][2]+'0')) + strPath;
        }

        GetGLCanvas()->Refresh( );

        // Path Dialog anzeigen
        if( !m_pDlgPath )
        {
            m_pDlgPath = new CDlgPath( sx, sy, ex, ey, sw.Time(), fCost, strPath, wxGetApp().GetFrame() );
            m_pDlgPath->Center();
        }
        else
        {
            m_pDlgPath->UpdateValues( sx, sy, ex, ey, sw.Time(), fCost, strPath );
        }

        m_pDlgPath->Show();
    }
    else
    {
        wxMessageBox( wxString::Format( "Kein Pfad von %d:%d nach %d:%d gefunden!",
            sx, sy, ex, ey), "Fehler" );
    }

    return bRet;
}

bool CMap::AStar( int sx, int sy, int ex, int ey )
{
    // Multiset sowie ein Iterator
    multiset<PathField> queue;
    multiset<PathField>::iterator itr;

    // 1.Add starting square
    CTile *pTile = &m_aTiles[sx][sy];
    pTile->m_CostG = 0;
    pTile->m_CostF = Heuristic( sx, sy, ex, ey );
    pTile->m_State = PATH_OPEN;
    queue.insert( PathField(sx, sy, pTile) );

    // Schleife
    while( !queue.empty() )
    {
        // Knoten mit den niedrigsten Kosten aus der Liste holen
        PathField f = *queue.begin();
        queue.erase( queue.begin() );

        f.pTile->m_State = PATH_CLOSE;  // Jetzt geschlossen
        int x = f.x, y = f.y;

        // Wenn Ziel sind wir fertig
        if( x == ex && y == ey )
            return true;

        // Alle angrenzenden Felder bearbeiten
        for( int i=0; i<8; i++ )
        {
            // Nachbarzelle
            int ax = x + g_DirTable[i][0];
            int ay = y + g_DirTable[i][1];

            // Testen ob neue x/y-Position gültig ist ( Rand ist ausgenommen )
            if( !IsValidField( ax, ay ) )
                continue;

            pTile = &m_aTiles[ax][ay];

            // Kosten um zu diesem Feld zu gelangen:
            float G = f.pTile->m_CostG + pTile->GetWeigth();    // Vorherige + aktuelle Kosten vom Start

            // Ignorieren wenn Knoten geschlossen ist und bessere Kosten hat
            if( pTile->m_State == PATH_CLOSE  && pTile->m_CostG < G )
                continue;

            // Tile ist bereits in der Queue, nur ersetzen wenn Kosten besser
            if( pTile->m_State == PATH_OPEN )
            {
                if( pTile->m_CostG < G )
                    continue;

                // Alten Eintrag aus der Queue entfernen
                itr = queue.find( PathField( ax, ay, pTile ) );
                if( itr != queue.end() )
                {
                    // Es können mehrere Einträge mit den gleichen Kosten vorhanden sein
                    // wir müssen den richtigen suchen
                    while( (*itr).pTile != pTile )
                        itr++;

                    queue.erase( itr );
                }
            }

            // Knoten berechnen
            pTile->m_CostG  = G;
            pTile->m_CostF  = G + Heuristic( ax, ay, ex, ey );      // Kosten vom Start + Kosten zum Ziel
            pTile->m_Parent = i;

            // Zu OPEN hinzufügen
            pTile->m_State = PATH_OPEN;
            queue.insert( PathField(ax, ay, pTile) );
        }
    }

    // Keinen Pfad gefunden
    return false;
}

float CMap::Heuristic( int sx, int sy, int ex, int ey )
{
    int dx = abs( sx - ex );
    int dy = abs( sy - ey );

    // Je größer die Konstante je schneller die Pfadplanung, je kleiner je optimaler der Weg
    return ( 1 * max(dx, dy));
}

/*----------------------------------------------------------------------------/
    Sonstige Funktionen
-----------------------------------------------------------------------------*/

/*
 *  IsValidField
 *  Wenn das Feld x/y exestiert, wird true zurückgegeben, sonst false
 */
bool CMap::IsValidField( int x, int y )
{
    if( x <= 0 || y <= 0 || x >= (m_nMapWidth-1) || y >= (m_nMapHeigth-1) )
        return false;

    return true;
}

/*
 *  GetFieldAtPoint
 *  Liefert die x/y Koordinate des Feldes unter dem Pixel an der Koordinate (x,y)
 */
wxPoint CMap::GetFieldAtPoint( int x, int y )
{
    wxPoint pt;
    pt.x = int((double(x) / 126.0 + double(y) /  70.0) - 1.0);
    pt.y = int( double(y) / 70.0  - double(x) / 126.0);

    // Clamp to valid map dimensions
    if( pt.x < 0 ) pt.x = 0; else if( pt.x > m_nMapWidth  ) pt.x = m_nMapWidth;
    if( pt.y < 0 ) pt.y = 0; else if( pt.y > m_nMapHeigth ) pt.y = m_nMapHeigth;
    return pt;
}

/*
 *  GetPosFromField
 *  Gibt die x/y Koordinate des Feldes (Mittepunkt) in Pixeln zurück
 */
wxPoint CMap::GetPosFromField( int x, int y )
{
    wxPoint pt;
    pt.x = (x-y) * 63 + 60;
    pt.y = (y+x) * 35 + 70;
    return pt;
}

CTown* CMap::GetTownAt( int x, int y )
{
    if ( !IsValidField( x, y ) )
        return NULL;

    return m_aTowns.get( x, y );
}

CGLCanvas* CMap::GetGLCanvas()
{
    CGLCanvas *pCanvas = wxGetApp().GetFrame()->GetGLCanvas();
    return pCanvas;
}

}
// kate: space-indent off; tab-width 4; replace-tabs off;

---