• There is NO official Otland's Discord server and NO official Otland's server list. The Otland's Staff does not manage any Discord server or server list. Moderators or administrator of any Discord server or server lists have NO connection to the Otland's Staff. Do not get scammed!

A* algorithm. Server vs Client Pathfinding

shial

New Member
Joined
Mar 31, 2009
Messages
11
Reaction score
3
Location
Sydney, Australia
GitHub
shial4
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.
 
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
 
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:
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
 
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.
 
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.
 
When you map click its the client which does the path finding and then send the list of directions to the server

Would it be possible to override this somehow? I'm trying to disable diagonal pathfinding, so that one has to drag the character to move diagonally.
 
Back
Top