C/C++ Pathfinding C++

Gohu · 29 Janvier 2014

Hello tout le monde,

Je suis actuellement entrain de faire un pathfinding pour mon bot. Je me heurte a un petit problème que je ne comprends pas:
en effet, j'ai tout vérifié et mon code semble bon.
Lors de tests quand je tente d'aller depuis la cellule 297 à 452 voici le chemin que j'obtiens (voir image fleche rouge), tandis que d'apres mes tests voici ce que le client fait (fleche bleue)
J'ai tout vérifié et mon code semble correcte. Voici mes sources:

la classe "Cellule"

Code:

#include "Cells.h"

Cells::Cells(QList<int> const &closedList, int cell)
{
    m_closedList = closedList;

    m_cell = cell;
    m_parent = NULL;
    m_YCoords = NULL;
    m_XCoords = NULL;

    m_cellFWeight = NULL;
    m_cellHWeight = NULL;
    m_cellGWeight = NULL;
    m_adjacentCells;
}

Cells::Cells(int cell)
{
    m_cell = cell;
    m_YCoords = NULL;
    m_XCoords = NULL;
    m_parent = NULL;

    m_cellFWeight = NULL;
    m_cellHWeight = NULL;
    m_cellGWeight = NULL;
}

Cells::Cells(int cell, int parent)
{
    m_cell = cell;
    m_parent = parent;
    m_YCoords = NULL;
    m_XCoords = NULL;

    m_cellFWeight = NULL;
    m_cellHWeight = NULL;
    m_cellGWeight = NULL;
}

bool Cells::operator==(const Cells& cell2)
{
    if (m_cell == cell2.m_cell)
            return true;

    return false;
}

void Cells::adjacentCells(Cells cell, QList<int> closedList)
{
    cell.coordsCalculations(cell);
    int _cell = cell.m_cell;

    cell.m_adjacentCells.clear();

    Cells adjacentCell1 = Cells(-1);
    Cells adjacentCell2 = Cells(-1);
    Cells adjacentCell3 = Cells(-1);
    Cells adjacentCell4 = Cells(-1);
    Cells adjacentCell5 = Cells(-1);
    Cells adjacentCell6 = Cells(-1);
    Cells adjacentCell7 = Cells(-1);
    Cells adjacentCell8 = Cells(-1);

    if ((cell.getYCoords(cell) % 2) == 0) {
        adjacentCell1.m_cell = (_cell - 1);
        adjacentCell2.m_cell = (_cell - 15);
        adjacentCell3.m_cell = (_cell - 28);
        adjacentCell4.m_cell = (_cell + 13);
        adjacentCell5.m_cell = (_cell - 14);
        adjacentCell6.m_cell = (_cell + 28);
        adjacentCell7.m_cell = (_cell + 14);
        adjacentCell8.m_cell = (_cell + 1);

        if (!closedList.contains(m_cell - 1))
            cell.m_adjacentCells.append(adjacentCell1.getCellId(adjacentCell1));
        if (!closedList.contains(m_cell - 15))
            cell.m_adjacentCells.append(adjacentCell2.getCellId(adjacentCell2));
        if (!closedList.contains(m_cell - 28))
            cell.m_adjacentCells.append(adjacentCell3.getCellId(adjacentCell3));
        if (!closedList.contains(m_cell + 13))
            cell.m_adjacentCells.append(adjacentCell4.getCellId(adjacentCell4));
        if (!closedList.contains(m_cell - 14))
            cell.m_adjacentCells.append(adjacentCell5.getCellId(adjacentCell5));
        if (!closedList.contains(m_cell + 28))
            cell.m_adjacentCells.append(adjacentCell6.getCellId(adjacentCell6));
        if (!closedList.contains(m_cell + 14))
            cell.m_adjacentCells.append(adjacentCell7.getCellId(adjacentCell7));
        if (!closedList.contains(m_cell + 1))
            cell.m_adjacentCells.append(adjacentCell8.getCellId(adjacentCell8));
    }

    if ((cell.getYCoords(cell) % 2) != 0) {
        adjacentCell1.m_cell = (_cell - 1);
        adjacentCell2.m_cell = (_cell - 14);
        adjacentCell3.m_cell = (_cell - 28);
        adjacentCell4.m_cell = (_cell + 14);
        adjacentCell5.m_cell = (_cell - 13);
        adjacentCell6.m_cell = (_cell + 28);
        adjacentCell7.m_cell = (_cell + 15);
        adjacentCell8.m_cell = (_cell + 1);

        if (!closedList.contains(m_cell - 1))
            cell.m_adjacentCells.append(adjacentCell1.getCellId(adjacentCell1));
        if (!closedList.contains(m_cell - 14))
            cell.m_adjacentCells.append(adjacentCell2.getCellId(adjacentCell2));
        if (!closedList.contains(m_cell - 28))
            cell.m_adjacentCells.append(adjacentCell3.getCellId(adjacentCell3));
        if (!closedList.contains(m_cell + 14))
            cell.m_adjacentCells.append(adjacentCell4.getCellId(adjacentCell4));
        if (!closedList.contains(m_cell - 13))
            cell.m_adjacentCells.append(adjacentCell5.getCellId(adjacentCell5));
        if (!closedList.contains(m_cell + 28))
            cell.m_adjacentCells.append(adjacentCell6.getCellId(adjacentCell6));
        if (!closedList.contains(m_cell + 15))
            cell.m_adjacentCells.append(adjacentCell7.getCellId(adjacentCell7));
        if (!closedList.contains(m_cell + 1))
            cell.m_adjacentCells.append(adjacentCell8.getCellId(adjacentCell8));
    }

        if ((cell.getXCoords(cell) == 1 || cell.getXCoords(cell) == 0) && (cell.getYCoords(cell) % 2 == 0)) {
            cell.m_adjacentCells.removeOne(adjacentCell1.getCellId(adjacentCell1));
            cell.m_adjacentCells.removeOne(adjacentCell2.getCellId(adjacentCell2));
            cell.m_adjacentCells.removeOne(adjacentCell4.getCellId(adjacentCell4));
        }

        if (cell.getYCoords(cell) == 0) {
            cell.m_adjacentCells.removeOne(adjacentCell2.getCellId(adjacentCell2));
            cell.m_adjacentCells.removeOne(adjacentCell3.getCellId(adjacentCell3));
            cell.m_adjacentCells.removeOne(adjacentCell5.getCellId(adjacentCell5));
        }

        if (cell.getYCoords(cell) == 1) {
            cell.m_adjacentCells.removeOne(adjacentCell3.getCellId(adjacentCell3));
        }

        if (cell.getXCoords(cell) == 27) {
            cell.m_adjacentCells.removeOne(adjacentCell5.getCellId(adjacentCell5));
            cell.m_adjacentCells.removeOne(adjacentCell7.getCellId(adjacentCell7));
            cell.m_adjacentCells.removeOne(adjacentCell8.getCellId(adjacentCell8));
        }

        if (cell.getYCoords(cell) == 39) {
            cell.m_adjacentCells.removeOne(adjacentCell4.getCellId(adjacentCell4));
            cell.m_adjacentCells.removeOne(adjacentCell6.getCellId(adjacentCell6));
            cell.m_adjacentCells.removeOne(adjacentCell7.getCellId(adjacentCell7));
        }

        if ((cell.getXCoords(cell) == 0 || cell.getXCoords(cell) == 1) && (cell.getYCoords(cell) % 2 != 0)) {
            cell.m_adjacentCells.removeOne(adjacentCell1.getCellId(adjacentCell1));
        }

        m_adjacentCells = cell.m_adjacentCells;
}

int Cells::processGWeight(Cells startCell, Cells endCell, int weight)
{
    startCell.coordsCalculations(startCell);
    endCell.coordsCalculations(endCell);
    int b = 0;

    if (endCell.getYCoords(endCell) % 2 == 0)
        if (startCell.getYCoords(startCell) % 2 != 0)
            b = 10;
        else
            b = 14;

    if (endCell.getYCoords(endCell) % 2 != 0)
        if (startCell.getYCoords(startCell) % 2 == 0)
            b = 10;
        else
            b = 14;

    b += weight;

    return b;

}

int Cells::processHWeight(Cells startCell, Cells endCell)
{
    startCell.coordsCalculations(startCell);
    endCell.coordsCalculations(endCell);
    int a;
    int b;
    int c;

    a = abs((endCell.getXCoords(endCell) - startCell.getXCoords(startCell)));
    b = abs((endCell.getYCoords(endCell) - startCell.getYCoords(startCell)));
    c = (10 * (a + b));
    return c;
}

void Cells::cellWeight(Cells startCell, Cells currentCell, Cells endCell, int weight)
{
    currentCell.m_cellFWeight = 0;
    currentCell.m_cellHWeight = 0;
    currentCell.m_cellGWeight = 0;

    currentCell.m_cellHWeight = processHWeight(endCell, currentCell);
    currentCell.m_cellGWeight = processGWeight(currentCell, startCell, weight);
    currentCell.m_cellFWeight = currentCell.m_cellGWeight + currentCell.m_cellHWeight;

    m_cellFWeight = currentCell.m_cellFWeight;
    m_cellGWeight = currentCell.m_cellGWeight;
    m_cellHWeight = currentCell.m_cellHWeight;
}

void Cells::coordsCalculations(Cells &cell)
{
    cell.m_YCoords = floor((cell.m_cell / 14));

    if (cell.m_YCoords < 0)
        cell.m_YCoords = 0;

    if (cell.m_YCoords && 1)
        cell.m_XCoords = (cell.m_cell - cell.m_YCoords * 14) * 2 +1;
    else
        cell.m_XCoords = (cell.m_cell - cell.m_YCoords * 14) * 2;

    m_XCoords = cell.m_XCoords;
    m_YCoords = cell.m_YCoords;
}

QList<int> Cells::cellsToInt(QList<Cells> cellList)
{
    QList<int> intList;
    for (int i = 0; i < cellList.size(); i++)
        intList.append(cellList[i].m_cell);

    return intList;
}

int Cells::getXCoords(Cells cell) const
{
    return cell.m_XCoords;
}

int Cells::getYCoords(Cells cell) const
{
    return cell.m_YCoords;
}

int Cells::getCellId(Cells cell) const
{
    return cell.m_cell;
}

QList<int> Cells::getAdjacentCells(Cells cell) const
{
    return cell.m_adjacentCells;
}

float Cells::getCellFWeight(Cells cell) const
{
    return cell.m_cellFWeight;
}

float Cells::getCellHWeight(Cells cell) const
{
    return cell.m_cellHWeight;
}

float Cells::getCellGWeight(Cells cell) const
{
    return cell.m_cellGWeight;
}

int Cells::getParent(Cells cell) const
{
    return cell.m_parent;
}

void Cells::setOpenList(Cells cell, QList<int> openList)
{
    cell.m_openList = openList;
}

void Cells::setParent(int parentCell)
{
    m_parent = parentCell;
}

void Cells::setCellId(int cellId)
{
    m_cell = cellId;
}

void Cells::setFWeight(int weight)
{
    m_cellFWeight = weight;
}

void Cells::setHWeight(int weight)
{
    m_cellHWeight = weight;
}

void Cells::setGWeight(int weight)
{
    m_cellGWeight = weight;
}

void Cells::setCloseList(QList<int> list)
{
    m_closedList = list;
}

La classe Pathfinder:

Code:

#include "Pathfinding.h"

Pathfinding::Pathfinding()
{
}

QList<int> Pathfinding::findPath(int _startCell, int _endCell, QList<int> _closedList)
{
    Cells startCell = Cells(_startCell);
    Cells endCell = Cells(_endCell);
    Cells currentCell = Cells(_closedList, _startCell);
    currentCell.setGWeight(0);

    QList<int> temp1;
    QList<Cells> temp2;
    QList<Cells> openList;
    QList<Cells> closeList;

    for (int i = 0; i < _closedList.size(); i++)    {
        Cells _cell = Cells(_closedList[i]);
        closeList.append(_cell);    }

    for (int i = 0; i < closeList.size(); i++)
        openList.removeOne(closeList[i]);

    closeList.append(startCell);
    currentCell.setCellId(_startCell);
    currentCell.setGWeight(0);

    while ((openList.size() != (560 - closeList.size())) && (!closeList.contains(endCell)))     {

        currentCell.adjacentCells(currentCell, Cells::cellsToInt(closeList));
        temp1 = currentCell.getAdjacentCells(currentCell);

        for (int i = 0; i < temp1.size(); i++)  {
            Cells _cell = Cells(temp1[i]);
            temp2.append(_cell);

            if (!closeList.contains(temp2.last()))  {
                temp2.last().cellWeight(currentCell, temp2.last(), endCell, currentCell.getCellGWeight(currentCell));
                temp2.last().setParent(currentCell.getCellId(currentCell));
            }
            else
                temp2.removeLast();
        }

        for (int i = 0; i < temp2.size(); i++)  {
            if (openList.contains(temp2[i]))    {
                if (openList[i].getCellGWeight(currentCell) > openList[i].processGWeight(currentCell, openList[i], currentCell.getCellGWeight(currentCell)))    {
                    openList[i].setParent(currentCell.getCellId(currentCell));
                    openList[i].setFWeight(openList[i].getCellHWeight(openList[i]) + openList[i].processGWeight(currentCell, openList[i], currentCell.getCellGWeight(currentCell)));
                    openList[i].setGWeight(openList[i].processGWeight(currentCell, openList[i], currentCell.getCellGWeight(currentCell)));
                }
            }

            if (!openList.contains(temp2[i]))   {
                openList.append(temp2[i]);
                openList.last().cellWeight(currentCell,  openList.last(), endCell, currentCell.getCellGWeight(currentCell));
                openList.last().setParent(currentCell.getCellId(currentCell));
            }
        }

        int minFWeight = 99999;
        int minGWeight = 99999;
        int optimisedCell = -1;
        int optimisedParent = -1;
        for (int i = 0; i < openList.size(); i++)   {
            if (openList[i].getCellFWeight(openList[i]) < minFWeight)   {
                qDebug()<<"Cell:"<<openList[i].getCellId(openList[i])<<"F:"<<openList[i].getCellFWeight(openList[i])<<"H:"<<openList[i].getCellHWeight(openList[i])<<"G:"<<openList[i].getCellGWeight(openList[i]);
                minFWeight = openList[i].getCellFWeight(openList[i]);
                minGWeight = openList[i].getCellGWeight(openList[i]);
                optimisedCell = openList[i].getCellId(openList[i]);
                optimisedParent = openList[i].getParent(openList[i]);
            }

            if ((openList[i].getCellFWeight(openList[i]) == minFWeight) && (openList[i].getCellGWeight(openList[i]) < minGWeight))  {
                qDebug()<<"Cell:"<<openList[i].getCellId(openList[i])<<"F:"<<openList[i].getCellFWeight(openList[i])<<"H:"<<openList[i].getCellHWeight(openList[i])<<"G:"<<openList[i].getCellGWeight(openList[i]);
                minFWeight = openList[i].getCellFWeight(openList[i]);
                minGWeight = openList[i].getCellGWeight(openList[i]);
                optimisedCell = openList[i].getCellId(openList[i]);
                optimisedParent = openList[i].getParent(openList[i]);
            }
        }

        qDebug()<<"Chose Cell"<<optimisedCell;
        Cells activeCell = Cells(optimisedCell, optimisedParent);
        closeList.append(activeCell);
        openList.removeOne(activeCell);

        currentCell.setCellId(optimisedCell);
        currentCell.setParent(optimisedParent);
        currentCell.setGWeight(minGWeight);

        temp1.clear();
        temp2.clear();
    }

    int _cell = closeList.last().getCellId(closeList.last());
        while (_cell != startCell.getCellId(startCell))   {
            m_path.prepend(_cell);
            _cell = traceBack(closeList.indexOf(_cell), closeList);
        }

        m_path.insert(0, startCell.getCellId(startCell));
        return m_path;
}

int Pathfinding::traceBack(int pos, QList<Cells> closeList)
{
    return closeList[pos].getParent(closeList[pos]);
}

FastFrench · 29 Janvier 2014

A mon avis cela n'a aucune importance. Si ton algo n'est pas rigoureusement identique à celui de D@fus, c'est normal que tu n'empruntes pas exactement le même chemin. Cela peut être simplement une question d'arrondis sur les calculs faits dans flash vs C++. Assures-toi juste que ton implémentation ne te fait jamais passer sur des obstacles ou autres cases interdites.

Je ne me suis jamais soucié d'avoir exactement les mêmes chemins que D@fus, et je recherchais même cette différence en introduisant un choix aléatoire entre les différents chemins équiprobables, afin que tous les persos gérés par le bot ne prennent pas tous le même chemin.

Et cela n'a jamais posé le moindre problème, même après par mal de mois de fonctionnement non-stop sur 8 comptes.

Gohu · 29 Janvier 2014

Donc tu dis que la différence du PATH entre le miens et celui de dof
n'est pas lié avec le fait que je fasse kik quand j'envoie le paquet de
mouvement ?

BlueDream · 29 Janvier 2014

Essaye d'inverser la veleur G Diagonale 14 avec G 10 horizontal/vertical.

Edit:

Après il faut que tu étudie le Path de dofus, pour les conditions que ankama a ajouté.

Gohu · 29 Janvier 2014

Bah d'apres FastFrench ya meme pas besoin de modifier

ToOnS · 29 Janvier 2014

Bonjour , non pas besoin de modifier du moment qu'il va ou tu veux (sans traverser une montagne ou un arbre , enfin une case non marchables que tu recuperes dans les d2p de memoire , sinon c'est dans les d2o ou d2jesaisplusquoi , parceque la je vois nul par(t?) ou tu interdits de marcher sur certaines case) meme si c'est pas le chemin officiel (d'ailleur le chemin officiel des fois est nul) pour le kick ca vien d'autre chose comme par exemple pas assez de temps entre plusieurs deplacements , faut bien attendre que le serveur te reponde que c'est ok , je me souvien plus du message , ou pas faire bouger 2 persos en meme temps avec le meme chemin (un follow trop rapide c'est un ban 2h)

FastFrench · 30 Janvier 2014

Ca peut aussi être ton message de mouvement qui est mal formé. Par exemple très longtemps D@fus acceptait des chemins non compressés alors que le client les compressait. Ce n'est peut-être plus le cas aujourd'hui. Ou encore les directions qui seraient incorrectes.

Bref, pour les mouvement faut bien comprendre et reproduire comment sont construits les paquets.

Gohu · 30 Janvier 2014

Oula tu parles de compression de path et de directions ?
Je suis perdu

BlueDream · 30 Janvier 2014

En gros.

Avant si on était a la cellule 45 et qu'on voulait allez a la cellule 50.
on envoyais 45/46/47/48/49/50.

Maintenant 45/50.
Faut donner la cellule a chaque changement de direction.
Envois-tu la confirmation du déplacement au serveur avec un timer et tout ?

Gohu · 30 Janvier 2014

Merde non j'envoie juste mon actor id et la liste des cells
sans timer ni orientations (qui a ce que j'ai vu n'apparaissent pas dans le paquet 951)

BlueDream · 30 Janvier 2014

Alors je t'explique, tu as juste a parser ton chemin.
Pas d'orientation a envoyer au serveur.

Par exemple,

Je suis cellule 1, je veux aller a la 30.
Je vais jusuq'a la cellule 15, je tourne car obstacle et je vais toujours tout droit vers la 30.

Cela donne sa: 1 / 2 / 3 / 4 / 18 / 19 / (je tourne) 27 / 28 / 29 / 30 / 30
Chemin un peu au pif.

Donc sa c'est un chemin non parsé que pourrait générer ton path.

Un path parsé supprime toute les cellules des lignes droites.
C'est a dire, tant que l'on ne change pas d'orientation (on ne tourne pas, on va toujours tout droit) on supprime les celulle.

Cela donne sa : 1 / 4 / 27 / 30

Ensuite au niveau du timer, chaque cellule parcourue prend un certaine temps a etre parcourue.
300 ms en marchant et 150 en courant a procimativement.

Donc tu dois attendre que tu es fini de te déplacer, en calculant le temps par cellule.
Et envoyer le paquet GameMapMovementConfirmMessage, ID: 952.

tifoux · 6 Février 2014

Moi je pense que les bannissements vient tous simplement a cause des obstacles (joueur, monstres etc...) j'avais eux le même soucis avec mon pathfinding j'ai juste rajouter les "montres, joueur etc..." puis aucun bannissements.
Ps : Si sa pourrait t'aider regarde du côter du pathfinding a FF qui se trouve dans les sources de bim.

RedBust · 18 Février 2014

Sur D. les joueurs\monstres sont considérés comme des obstacles ?
Ca fait pas mal de temps que je n'ai pas joué mais il me semble bien qu'hors combat on peut être à plusieurs sur une case (ce qui rend les maps hyperchargées et absolument illisibles d'ailleurs).

asyade · 20 Février 2014

On peut étre a plusieur sur une cellule mais quant il sagit de pathfinding il contourne les monstes ,joueurs quant c'est possible (car des fois ce n'est evidament pas le cas) pour faire un peut plus "réaliste"

NicoMasterChief · 23 Février 2014

Sujet très intéressant, merci à tous pour ces précieuses explications.

C/C++ Pathfinding C++

Gohu

Membre Actif

FastFrench

Membre Actif

Gohu

Membre Actif

BlueDream

Administrateur

Gohu

Membre Actif

ToOnS

Membre Actif

FastFrench

Membre Actif

Gohu

Membre Actif

BlueDream

Administrateur

Gohu

Membre Actif

BlueDream

Administrateur

tifoux

Membre

RedBust

Membre Actif

asyade

Membre Actif

NicoMasterChief

Membre