A* algorithm. Server vs Client Pathfinding

shial

New Member
Joined
Mar 31, 2009
Messages
5
Reaction score
0
Location
Sydney, Australia
With Tibia server pathfinding is it done on the server side or via client side?
If so why? What are cons and pros?
Want to know your opinion on that topic.
 

Togu

Active Member
Joined
Jun 22, 2018
Messages
240
Reaction score
92
Location
Brazil
Found this on OTClient project:
Code:
std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> Map::findPath(const Position& startPos, const Position& goalPos, int maxComplexity, int flags)
{
    // pathfinding using A* search algorithm
    // as described in http://en.wikipedia.org/wiki/A*_search_algorithm

    struct Node {
        Node(const Position& pos) : cost(0), totalCost(0), pos(pos), prev(nullptr), dir(Otc::InvalidDirection) { }
        float cost;
        float totalCost;
        Position pos;
        Node *prev;
        Otc::Direction dir;
    };

    struct LessNode : std::binary_function<std::pair<Node*, float>, std::pair<Node*, float>, bool> {
        bool operator()(std::pair<Node*, float> a, std::pair<Node*, float> b) const {
            return b.second < a.second;
        }
    };

    std::tuple<std::vector<Otc::Direction>, Otc::PathFindResult> ret;
    std::vector<Otc::Direction>& dirs = std::get<0>(ret);
    Otc::PathFindResult& result = std::get<1>(ret);

    result = Otc::PathFindResultNoWay;

    if(startPos == goalPos) {
        result = Otc::PathFindResultSamePosition;
        return ret;
    }

    if(startPos.z != goalPos.z) {
        result = Otc::PathFindResultImpossible;
        return ret;
    }

    // check the goal pos is walkable
    if(g_map.isAwareOfPosition(goalPos)) {
        const TilePtr goalTile = getTile(goalPos);
        if(!goalTile || !goalTile->isWalkable()) {
            return ret;
        }
    }
    else {
        const MinimapTile& goalTile = g_minimap.getTile(goalPos);
        if(goalTile.hasFlag(MinimapTileNotWalkable)) {
            return ret;
        }
    }

    std::unordered_map<Position, Node*, PositionHasher> nodes;
    std::priority_queue<std::pair<Node*, float>, std::vector<std::pair<Node*, float>>, LessNode> searchList;

    Node *currentNode = new Node(startPos);
    currentNode->pos = startPos;
    nodes[startPos] = currentNode;
    Node *foundNode = nullptr;
    while(currentNode) {
        if((int)nodes.size() > maxComplexity) {
            result = Otc::PathFindResultTooFar;
            break;
        }

        // path found
        if(currentNode->pos == goalPos && (!foundNode || currentNode->cost < foundNode->cost))
            foundNode = currentNode;

        // cost too high
        if(foundNode && currentNode->totalCost >= foundNode->cost)
            break;

        for(int i=-1;i<=1;++i) {
            for(int j=-1;j<=1;++j) {
                if(i == 0 && j == 0)
                    continue;

                bool wasSeen = false;
                bool hasCreature = false;
                bool isNotWalkable = true;
                bool isNotPathable = true;
                int speed = 100;

                Position neighborPos = currentNode->pos.translated(i, j);
                if(g_map.isAwareOfPosition(neighborPos)) {
                    wasSeen = true;
                    if(const TilePtr& tile = getTile(neighborPos)) {
                        hasCreature = tile->hasCreature();
                        isNotWalkable = !tile->isWalkable();
                        isNotPathable = !tile->isPathable();
                        speed = tile->getGroundSpeed();
                    }
                } else {
                    const MinimapTile& mtile = g_minimap.getTile(neighborPos);
                    wasSeen = mtile.hasFlag(MinimapTileWasSeen);
                    isNotWalkable = mtile.hasFlag(MinimapTileNotWalkable);
                    isNotPathable = mtile.hasFlag(MinimapTileNotPathable);
                    if(isNotWalkable || isNotPathable)
                        wasSeen = true;
                    speed = mtile.getSpeed();
                }

                float walkFactor = 0;
                if(neighborPos != goalPos) {
                    if(!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)
                        continue;
                    if(wasSeen) {
                        if(!(flags & Otc::PathFindAllowCreatures) && hasCreature)
                            continue;
                        if(!(flags & Otc::PathFindAllowNonPathable) && isNotPathable)
                            continue;
                        if(!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)
                            continue;
                    }
                } else {
                    if(!(flags & Otc::PathFindAllowNotSeenTiles) && !wasSeen)
                        continue;
                    if(wasSeen) {
                        if(!(flags & Otc::PathFindAllowNonWalkable) && isNotWalkable)
                            continue;
                    }
                }

                Otc::Direction walkDir = currentNode->pos.getDirectionFromPosition(neighborPos);
                if(walkDir >= Otc::NorthEast)
                    walkFactor += 3.0f;
                else
                    walkFactor += 1.0f;

                float cost = currentNode->cost + (speed * walkFactor) / 100.0f;

                Node *neighborNode;
                if(nodes.find(neighborPos) == nodes.end()) {
                    neighborNode = new Node(neighborPos);
                    nodes[neighborPos] = neighborNode;
                } else {
                    neighborNode = nodes[neighborPos];
                    if(neighborNode->cost <= cost)
                        continue;
                }

                neighborNode->prev = currentNode;
                neighborNode->cost = cost;
                neighborNode->totalCost = neighborNode->cost + neighborPos.distance(goalPos);
                neighborNode->dir = walkDir;
                searchList.push(std::make_pair(neighborNode, neighborNode->totalCost));
            }
        }

        if(!searchList.empty()) {
            currentNode = searchList.top().first;
            searchList.pop();
        } else
            currentNode = nullptr;
    }

    if(foundNode) {
        currentNode = foundNode;
        while(currentNode) {
            dirs.push_back(currentNode->dir);
            currentNode = currentNode->prev;
        }
        dirs.pop_back();
        std::reverse(dirs.begin(), dirs.end());
        result = Otc::PathFindResultOk;
    }

    for(auto it : nodes)
        delete it.second;

    return ret;
}
And this on TFS 1.3 project:
Code:
void Creature::goToFollowCreature()
{
    if (followCreature) {
        FindPathParams fpp;
        getPathSearchParams(followCreature, fpp);

        Monster* monster = getMonster();
        if (monster && !monster->getMaster() && (monster->isFleeing() || fpp.maxTargetDist > 1)) {
            Direction dir = DIRECTION_NONE;

            if (monster->isFleeing()) {
                monster->getDistanceStep(followCreature->getPosition(), dir, true);
            } else { //maxTargetDist > 1
                if (!monster->getDistanceStep(followCreature->getPosition(), dir)) {
                    // if we can't get anything then let the A* calculate
                    listWalkDir.clear();
                    if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
                        hasFollowPath = true;
                        startAutoWalk(listWalkDir);
                    } else {
                        hasFollowPath = false;
                    }
                    return;
                }
            }

            if (dir != DIRECTION_NONE) {
                listWalkDir.clear();
                listWalkDir.push_front(dir);

                hasFollowPath = true;
                startAutoWalk(listWalkDir);
            }
        } else {
            listWalkDir.clear();
            if (getPathTo(followCreature->getPosition(), listWalkDir, fpp)) {
                hasFollowPath = true;
                startAutoWalk(listWalkDir);
            } else {
                hasFollowPath = false;
            }
        }
    }

    onFollowCreatureComplete(followCreature);
}
So I don't know
 
OP
shial

shial

New Member
Joined
Mar 31, 2009
Messages
5
Reaction score
0
Location
Sydney, Australia
I am more likely interested in terms of a map click. Can you send me the link to client GitHub page?
NVM: edubart/otclient (https://github.com/edubart/otclient/blob/master/src/client/map.cpp)
got it myself.
My question is still valid.
So far got this
 
Last edited:

masteuszx

OtsList.eu
Joined
Aug 3, 2008
Messages
742
Reaction score
37
I am more likely interested in terms of a map click. Can you send me the link to client GitHub page?
NVM: edubart/otclient (https://github.com/edubart/otclient/blob/master/src/client/map.cpp)
got it myself.
My question is still valid.
So far got this
pure clientside, hope i helped :p
 

Yamaken

Pro OpenTibia Developer
Premium User
Joined
Jul 27, 2013
Messages
456
Reaction score
324
Both. When you map click its the client which does the path finding and then send the list of directions to the server, when you use an item and the server walks your character towards the item its the server path finding which is also used by NPCs and specially by monsters.
 
OP
shial

shial

New Member
Joined
Mar 31, 2009
Messages
5
Reaction score
0
Location
Sydney, Australia
Both. When you map click its the client which does the path finding and then send the list of directions to the server, when you use an item and the server walks your character towards the item its the server path finding which is also used by NPCs and specially by monsters.
That's the solution I went with.
 

Syntax

Developer
Joined
Oct 10, 2007
Messages
2,819
Reaction score
166
Location
Texas
The best solution is a server side service separate of the game server that can scale independently.


The client and server can offload pathfinding to it.
 
Top