1
0
mirror of https://github.com/blupi-games/planetblupi synced 2024-12-30 10:15:36 +01:00
planetblupi/chemin.cpp
2017-01-21 17:51:48 +01:00

370 lines
8.4 KiB
C++

// chemin.cpp
// (c) 1997, Denis Dumoulin
#include "DECOR.H"
#include "FIFO.H"
#include "ACTION.H"
// Mémorise toutes les positions des blupi.
void CDecor::CheminMemPos(int exRank)
{
int rank, index;
m_cheminNbPos = 0;
index = 0;
for ( rank=0 ; rank<MAXBLUPI ; rank++ )
{
if ( m_blupi[rank].bExist &&
m_blupi[rank].perso != 6 && // pas le détonnateur de mine
rank != exRank )
{
m_cheminPos[index] = m_blupi[rank].cel;
m_cheminRank[index] = rank;
m_cheminNbPos ++;
index ++;
if ( m_blupi[rank].destCel.x != m_blupi[rank].cel.x ||
m_blupi[rank].destCel.y != m_blupi[rank].cel.y )
{
m_cheminPos[index] = m_blupi[rank].destCel;
m_cheminRank[index] = rank;
m_cheminNbPos ++;
index ++;
}
}
}
}
// Teste si une positiion est occupée par un blupi.
BOOL CDecor::CheminTestPos(POINT pos, int &rank)
{
int i;
for ( i=0 ; i<m_cheminNbPos ; i++ )
{
if ( pos.x == m_cheminPos[i].x &&
pos.y == m_cheminPos[i].y )
{
rank = m_cheminRank[i];
return TRUE;
}
}
return FALSE;
}
// une fois le but trouvé, reprend en arrière
// à la recherche du chemin le plus court
// retourne la direction à prendre
int CDecor::CheminARebours(int rank)
{
int pos, rebours, last, dir, set;
POINT v;
pos = m_blupi[rank].goalCel.y*MAXCELX + m_blupi[rank].goalCel.x;
rebours = m_cheminWork[pos];
if ( rebours == 0 ) return -1;
while ( TRUE )
{
bis:
for ( set=0 ; set<2 ; set++ )
{
for ( dir=set ; dir<8 ; dir+=2 )
{
v = GetVector(dir*16);
last = pos + v.y*MAXCELX+v.x;
if ( m_cheminWork[last] > 0 &&
m_cheminWork[last] < rebours )
{
pos = last;
rebours = m_cheminWork[pos];
if (rebours==1) return (dir>=4) ? dir-4 : dir+4;
goto bis; // interrompt le for...
}
}
}
// ne devrait jamais arriver !
return -1;
}
}
// troisième méthode de recherche
// semblable à la précédente,
// mais les points à explorer sont classés selon leur distance à la cible
void CDecor::CheminFillTerrain(int rank)
{
long pos, last, dest, dist;
int step, dir, cout, action, max, next, ampli;
int dx, dy;
int but = 1000;
if ( m_blupi[rank].cel.x == m_blupi[rank].goalCel.x &&
m_blupi[rank].cel.y == m_blupi[rank].goalCel.y ) return;
pos = m_blupi[rank].cel.y*MAXCELX + m_blupi[rank].cel.x;
dest = m_blupi[rank].goalCel.y*MAXCELX + m_blupi[rank].goalCel.x;
CPileTriee fifo(2*MAXCELX+2*MAXCELY); // les variantes possibles
fifo.put(pos, 0); // position de départ
m_cheminWork[pos] = 1; // première position
// répète jusqu'à trouvé ou plus de possibilités
max = 500;
while ( max-- > 0 )
{
// reprend une variante de chemin
pos = fifo.get();
if ( pos < 0 ) break;
step = m_cheminWork[pos];
// on est arrivé au but ?
//? if ( pos == dest ) return;
if ( pos == dest )
{
but = step; // hélas trop lent !
max = 50;
}
// est-ce vraiment trop loin ?
if ( step > 200 ) return;
// marque les cases autour du point
if ( step < but ) for ( dir=0 ; dir<8 ; dir++ )
{
if ( CheminTestDirection(rank, pos, dir, next, ampli, cout, action) )
{
last = pos + ampli*next;
if ( last<0 || last>=MAXCELX*MAXCELY ) continue;
if ( m_cheminWork[last] == 0 ||
m_cheminWork[last] > step+cout )
{
// marque les cases sautées
for (int i=1; i<ampli;i++)
{
m_cheminWork[pos+i*next] = step+cout-ampli+i;
}
m_cheminWork[last] = step+cout;
//? char buffer[50];
//? sprintf(buffer, "word = %d;%d %d\n", last%200, last/200, step+cout);
//? OutputDebug(buffer);
dx = m_blupi[rank].goalCel.x - last%MAXCELX;
dy = m_blupi[rank].goalCel.y - last/MAXCELX;
//? dist = dy*dy + dx*dx;
dist = (long)(dy*dy) + (long)(dx*dx);
fifo.put(last, dist);
}
}
}
}
}
// routine déterninant si une direction est possible
// retourne l'incrément pour passer à la nouvelle case
// et le "prix à payer" pour aller dans cette direction
// coût doit être déterminé en sortie
BOOL CDecor::CheminTestDirection(int rank, int pos, int dir,
int &next, int &ampli,
int &cout, int &action)
{
POINT cel, vector, newCel;
BOOL bFree;
int tryDirect, workBlupi, rankHere;
cel.x = pos%MAXCELX;
cel.y = pos/MAXCELX;
tryDirect = dir*16;
vector = GetVector(tryDirect);
// Peut-on glisser dans cette direction ?
bFree = IsFreeGlisse(cel, tryDirect, rank, action);
cout = 5; // coût élevé
if ( !bFree )
{
// Peut-on marcher normalement ?
bFree = IsFreeDirect(cel, tryDirect, rank);
action = ACTION_MARCHE;
cout = 1; // coût minimal
}
if ( !bFree )
{
// Peut-on sauter ?
bFree = IsFreeJump(cel, tryDirect, rank, action);
cout = 3; // coût élevé
}
ampli = GetAmplitude(action); // a <- amplitude (1..5)
cout *= ampli; // coût plus élevé si grande amplitude
// Blupi peut aller sur le lieu de la construction.
if ( !bFree && m_blupi[rank].passCel.x != -1 )
{
newCel = m_blupi[rank].passCel;
workBlupi = m_decor[newCel.x/2][newCel.y/2].workBlupi;
if ( m_blupi[rank].passCel.x/2 == (cel.x+vector.x*ampli)/2 &&
m_blupi[rank].passCel.y/2 == (cel.y+vector.y*ampli)/2 &&
(workBlupi < 0 || workBlupi == rank) )
{
bFree = TRUE;
cout = 1;
}
}
if ( bFree ) // chemin libre (sans tenir compte des perso) ?
{
newCel.x = cel.x + vector.x*ampli;
newCel.y = cel.y + vector.y*ampli; // newCel <- arrivée suposée
if ( m_blupi[rank].perso == 3 ) // tracks ?
{
// Le tracks peut aller sur les blupi
// pour les écraser !
if ( IsTracksHere(newCel, FALSE) ) // autre perso ici ?
{
return FALSE;
}
}
else
{
//? if ( IsBlupiHere(newCel, FALSE) ) // autre perso ici ?
if ( CheminTestPos(newCel, rankHere) ) // autre perso ici ?
{
// Si blupi immobile, comme si obstacle qq.
//? if ( m_blupi[m_blupiHere].goalCel.x == -1 ) return FALSE;
if ( m_blupi[rankHere].goalCel.x == -1 ) return FALSE;
// Si blupi mobile, possible mais coût élevé.
cout = 20;
}
}
next = vector.y*MAXCELX + vector.x;
return TRUE;
}
return FALSE;
}
// Retourne TRUE si on a assigné une nouvelle direction à blupi.
BOOL CDecor::CheminCherche(int rank, int &action)
{
int cout; // prix pour aller dans une direction
int pos, dir, next, ampli;
// Déjà à destination ?
if ( m_blupi[rank].cel.x == m_blupi[rank].goalCel.x &&
m_blupi[rank].cel.y == m_blupi[rank].goalCel.y )
{
return FALSE;
}
// Destination occupée ?
if ( IsBlupiHereEx(m_blupi[rank].goalCel, rank, FALSE) )
{
return FALSE;
}
memset(m_cheminWork, 0, (BYTE)MAXCELX*(BYTE)MAXCELY);
CheminMemPos(rank);
// fait un remplissage du map de travail
// autour du point de départ
CheminFillTerrain(rank);
// cherche le chemin à partir de la destination
dir = CheminARebours(rank);
if ( dir < 0 ) return FALSE;
pos = m_blupi[rank].cel.y*MAXCELX + m_blupi[rank].cel.x;
if ( CheminTestDirection(rank, pos, dir, next, ampli, cout, action) &&
cout < 20 )
{
m_blupi[rank].sDirect = 16*dir;
return TRUE;
}
// ne devrait jamais arriver !
return FALSE;
}
// Teste s'il est possible de se rendre à un endroit donné.
BOOL CDecor::IsCheminFree(int rank, POINT dest, int button)
{
int action, sDirect;
POINT goalCel, passCel, limit;
BOOL bOK;
if ( button == BUTTON_STOP ) return TRUE;
goalCel = m_blupi[rank].goalCel;
passCel = m_blupi[rank].passCel;
sDirect = m_blupi[rank].sDirect;
if ( IsFreeCelEmbarque(dest, rank, action, limit) )
{
dest = limit;
}
if ( IsFreeCelDebarque(dest, rank, action, limit) )
{
dest = limit;
}
if ( button == BUTTON_GO &&
m_decor[dest.x/2][dest.y/2].objectChannel == CHOBJECT &&
(m_decor[dest.x/2][dest.y/2].objectIcon == 118 || // jeep ?
m_decor[dest.x/2][dest.y/2].objectIcon == 16 ) && // armure ?
dest.x%2 == 1 && dest.y%2 == 1 )
{
dest.y --; // va à côté jeep/armure
}
if ( button == BUTTON_GO &&
m_decor[dest.x/2][dest.y/2].objectChannel == CHOBJECT &&
m_decor[dest.x/2][dest.y/2].objectIcon == 113 ) // maison ?
{
dest.x = (dest.x/2)*2+1;
dest.y = (dest.y/2)*2+1; // sous la porte
}
if ( m_blupi[rank].cel.x == dest.x &&
m_blupi[rank].cel.y == dest.y ) return TRUE;
m_blupi[rank].goalCel = dest;
if ( m_decor[dest.x/2][dest.y/2].objectChannel == CHOBJECT &&
button != BUTTON_GO )
{
m_blupi[rank].passCel = dest; // si arbres/fleurs/bateau/etc.
}
bOK = CheminCherche(rank, action);
m_blupi[rank].goalCel = goalCel;
m_blupi[rank].passCel = passCel;
m_blupi[rank].sDirect = sDirect;
return bOK;
}