GeoEngine and movement improvements

[Pandragon]

The inner team has done a lot of code cleanup/improvements during the last year and I am ready glad you did so. But I feel that at some point you should start focusing on improving the current GeoEngine and monster movement. In my opinion it may be the most important thing, that has big impact on player gameplay and also server resources usage.

There are already two threats with some quite promising improvements.
viewtopic.php?f=69&t=27000
viewtopic.php?f=69&t=24034

I just point what I see as a simple l2j user, with no idea on what your current plans are.

[Zoey76]

The inner team has done a lot of code cleanup/improvements during the last year and I am ready glad you did so. But I feel that at some point you should start focusing on improving the current GeoEngine and monster movement. In my opinion it may be the most important thing, that has big impact on player gameplay and also server resources usage.

There are already two threats with some quite promising improvements.
viewtopic.php?f=69&t=27000
viewtopic.php?f=69&t=24034

I just point what I see as a simple l2j user, with no idea on what your current plans are.

The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.
The movement fixes patch has many bugs and it's outdated, there are some nice videos in that thread but no code updates.

[Pandragon]

I was thinking that a core dev could start a new thread, like the old Hellbound contribution threat.
Get users that are interested to help with the development and use any good contributions for BETA branch.
You cound start with something simple, like geoengine rework and code cleanup etc

[jurchiks]

Thay're too busy for that, not going to happen.

[UnAfraid]

The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.

Which one is the best approach then?

[Zoey76]

The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.

Which one is the best approach then?

I don't know yet, but you can ask Forsaiken, since he is our L2J Geodata expert, he will probably tell you the same about this approach.

[jurchiks]

There's no point in telling just that something is not good, you have to say what is the better approach. Otherwise it's just mixing the air.

[UnAfraid]

The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.

Which one is the best approach then?

I don't know yet, but you can ask Forsaiken, sinc he is our L2J Geodata expert, he will probably tell you the same about this approach.

He did the same.
Actually FBIagent even made best possible way to keep memory usage low and fast operation of the engine.
I can't see any better way, keep in mind that this is called really often you must not slow down the procedures and you don't really have much options.

[Pandragon]

How about improved pathfinding? so that monsters will not get stuck on obstacles
(as shown on Szponiasty's videos).

[Aristo]

To calculate the path, you can use a new algorithm for "Jump Point Search". It is much faster and more efficiently than A*.
Here you can compare the performance of algorithms: http://qiao.github.io/PathFinding.js/visual/
Detailed description: http://harablog.wordpress.com/2011/09/0 ... nt-search/

The implementation for the JS and two coordinate system:

Code: Select all

/** * @author aniero / https://github.com/aniero */var Heap       = require('../core/Heap');var Util       = require('../core/Util');var Heuristic  = require('../core/Heuristic'); /** * Path finder using the Jump Point Search algorithm * @param {object} opt * @param {function} opt.heuristic Heuristic function to estimate the distance *     (defaults to manhattan). */function JumpPointFinder(opt) {    opt = opt || {};    this.heuristic = opt.heuristic || Heuristic.manhattan;} /** * Find and return the path. * @return {Array.<[number, number]>} The path, including both start and *     end positions. */JumpPointFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {    var openList = this.openList = new Heap(function(nodeA, nodeB) {            return nodeA.f - nodeB.f;        }),        startNode = this.startNode = grid.getNodeAt(startX, startY),        endNode = this.endNode = grid.getNodeAt(endX, endY), node;     this.grid = grid;      // set the `g` and `f` value of the start node to be 0    startNode.g = 0;    startNode.f = 0;     // push the start node into the open list    openList.push(startNode);    startNode.opened = true;     // while the open list is not empty    while (!openList.empty()) {        // pop the position of node which has the minimum `f` value.        node = openList.pop();        node.closed = true;         if (node === endNode) {            return Util.backtrace(endNode);        }         this._identifySuccessors(node);    }     // fail to find the path    return [];}; /** * Identify successors for the given node. Runs a jump point search in the * direction of each available neighbor, adding any points found to the open * list. * @protected */JumpPointFinder.prototype._identifySuccessors = function(node) {    var grid = this.grid,        heuristic = this.heuristic,        openList = this.openList,        endX = this.endNode.x,        endY = this.endNode.y,        neighbors, neighbor,        jumpPoint, i, l,        x = node.x, y = node.y,        jx, jy, dx, dy, d, ng, jumpNode,        abs = Math.abs, max = Math.max;     neighbors = this._findNeighbors(node);    for(i = 0, l = neighbors.length; i < l; ++i) {        neighbor = neighbors[i];        jumpPoint = this._jump(neighbor[0], neighbor[1], x, y);        if (jumpPoint) {             jx = jumpPoint[0];            jy = jumpPoint[1];            jumpNode = grid.getNodeAt(jx, jy);             if (jumpNode.closed) {                continue;            }             // include distance, as parent may not be immediately adjacent:            d = Heuristic.euclidean(abs(jx - x), abs(jy - y));            ng = node.g + d; // next `g` value             if (!jumpNode.opened || ng < jumpNode.g) {                jumpNode.g = ng;                jumpNode.h = jumpNode.h || heuristic(abs(jx - endX), abs(jy - endY));                jumpNode.f = jumpNode.g + jumpNode.h;                jumpNode.parent = node;                 if (!jumpNode.opened) {                    openList.push(jumpNode);                    jumpNode.opened = true;                } else {                    openList.updateItem(jumpNode);                }            }        }    }}; /** Search recursively in the direction (parent -> child), stopping only when a * jump point is found. * @protected * @return {Array.<[number, number]>} The x, y coordinate of the jump point *     found, or null if not found */JumpPointFinder.prototype._jump = function(x, y, px, py) {    var grid = this.grid,        dx = x - px, dy = y - py, jx, jy;     if (!grid.isWalkableAt(x, y)) {        return null;    }    else if (grid.getNodeAt(x, y) === this.endNode) {        return [x, y];    }     // check for forced neighbors    // along the diagonal    if (dx !== 0 && dy !== 0) {        if ((grid.isWalkableAt(x - dx, y + dy) && !grid.isWalkableAt(x - dx, y)) ||            (grid.isWalkableAt(x + dx, y - dy) && !grid.isWalkableAt(x, y - dy))) {            return [x, y];        }    }    // horizontally/vertically    else {        if( dx !== 0 ) { // moving along x            if((grid.isWalkableAt(x + dx, y + 1) && !grid.isWalkableAt(x, y + 1)) ||               (grid.isWalkableAt(x + dx, y - 1) && !grid.isWalkableAt(x, y - 1))) {                return [x, y];            }        }        else {            if((grid.isWalkableAt(x + 1, y + dy) && !grid.isWalkableAt(x + 1, y)) ||               (grid.isWalkableAt(x - 1, y + dy) && !grid.isWalkableAt(x - 1, y))) {                return [x, y];            }        }    }     // when moving diagonally, must check for vertical/horizontal jump points    if (dx !== 0 && dy !== 0) {        jx = this._jump(x + dx, y, x, y);        jy = this._jump(x, y + dy, x, y);        if (jx || jy) {            return [x, y];        }    }     // moving diagonally, must make sure one of the vertical/horizontal    // neighbors is open to allow the path    if (grid.isWalkableAt(x + dx, y) || grid.isWalkableAt(x, y + dy)) {        return this._jump(x + dx, y + dy, x, y);    } else {        return null;    }}; /** * Find the neighbors for the given node. If the node has a parent, * prune the neighbors based on the jump point search algorithm, otherwise * return all available neighbors. * @return {Array.<[number, number]>} The neighbors found. */JumpPointFinder.prototype._findNeighbors = function(node) {    var parent = node.parent,        x = node.x, y = node.y,        grid = this.grid,        px, py, nx, ny, dx, dy,        neighbors = [], neighborNodes, neighborNode, i, l;     // directed pruning: can ignore most neighbors, unless forced.    if (parent) {        px = parent.x;        py = parent.y;        // get the normalized direction of travel        dx = (x - px) / Math.max(Math.abs(x - px), 1);        dy = (y - py) / Math.max(Math.abs(y - py), 1);         // search diagonally        if (dx !== 0 && dy !== 0) {            if (grid.isWalkableAt(x, y + dy)) {                neighbors.push([x, y + dy]);            }            if (grid.isWalkableAt(x + dx, y)) {                neighbors.push([x + dx, y]);            }            if (grid.isWalkableAt(x, y + dy) || grid.isWalkableAt(x + dx, y)) {                neighbors.push([x + dx, y + dy]);            }            if (!grid.isWalkableAt(x - dx, y) && grid.isWalkableAt(x, y + dy)) {                neighbors.push([x - dx, y + dy]);            }            if (!grid.isWalkableAt(x, y - dy) && grid.isWalkableAt(x + dx, y)) {                neighbors.push([x + dx, y - dy]);            }        }        // search horizontally/vertically        else {            if(dx === 0) {                if (grid.isWalkableAt(x, y + dy)) {                    if (grid.isWalkableAt(x, y + dy)) {                        neighbors.push([x, y + dy]);                    }                    if (!grid.isWalkableAt(x + 1, y)) {                        neighbors.push([x + 1, y + dy]);                    }                    if (!grid.isWalkableAt(x - 1, y)) {                        neighbors.push([x - 1, y + dy]);                    }                }            }            else {                if (grid.isWalkableAt(x + dx, y)) {                    if (grid.isWalkableAt(x + dx, y)) {                        neighbors.push([x + dx, y]);                    }                    if (!grid.isWalkableAt(x, y + 1)) {                        neighbors.push([x + dx, y + 1]);                    }                    if (!grid.isWalkableAt(x, y - 1)) {                        neighbors.push([x + dx, y - 1]);                    }                }            }        }    }    // return all neighbors    else {        neighborNodes = grid.getNeighbors(node, true);        for (i = 0, l = neighborNodes.length; i < l; ++i) {            neighborNode = neighborNodes[i];            neighbors.push([neighborNode.x, neighborNode.y]);        }    }        return neighbors;}; module.exports = JumpPointFinder;

[UnAfraid]

To calculate the path, you can use a new algorithm for "Jump Point Search". It is much faster and more efficiently than A*.
Here you can compare the performance of algorithms: http://qiao.github.io/PathFinding.js/visual/
Detailed description: http://harablog.wordpress.com/2011/09/0 ... nt-search/

Looks really good!

[Pandragon]

Can this be used to make pathfinding better?
Amazed... still... did not understand anything

[Aristo]

Theoretically, this would greatly reduce the load on the CPU with a large number of characters.
Also, it will find a route to any visible distances without severe performance degradation.

[Szponiasty]

Theoretically, this would greatly reduce the load on the CPU with a large number of characters.
Also, it will find a route to any visible distances without severe performance degradation.

I've already started writing JPS pathfinding engine. Have some experimental version done, based on some JPS code found on goole (currently it's without z support thou, so 2d pathfinding only). Looks very promising so far (It's very quick).

Anyway I have problem with moving very fat characters, for example around an obstacle. My current vectorengine path processing solves this, but only to certain max. collision radius :/ I was looking for some transformation algorithms, that I could use, but not found nothing interesting. So my idea is to process path this way:
Mby someone has better idea to solve this?

[Pandragon]

CellPathFinding -> JumpPointPathfinding?