GeoEngine and movement improvements
Forum rules
READ NOW: L2j Forums Rules of Conduct
READ NOW: L2j Forums Rules of Conduct
- Pandragon
- Posts: 704
- Joined: Tue Jul 26, 2005 7:38 pm
GeoEngine and movement improvements
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.
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
- L2j Inner Circle
- Posts: 7005
- Joined: Tue Aug 11, 2009 3:36 am
Re: GeoEngine and movement improvements
The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.pandragon wrote: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 movement fixes patch has many bugs and it's outdated, there are some nice videos in that thread but no code updates.
Powered by Eclipse 4.30 | Eclipse Temurin 21 | MariaDB 11.3.2 | L2J Server 2.6.3.0 - High Five
Join our Discord!
Join our Discord!
- Pandragon
- Posts: 704
- Joined: Tue Jul 26, 2005 7:38 pm
Re: GeoEngine and movement improvements
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
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
Last edited by Pandragon on Fri Jun 07, 2013 10:59 am, edited 1 time in total.
- jurchiks
- Posts: 6769
- Joined: Sat Sep 19, 2009 4:16 pm
- Location: Eastern Europe
Re: GeoEngine and movement improvements
Thay're too busy for that, not going to happen.
If you have problems, FIRST TRY SOLVING THEM YOURSELF, and if you get errors, TRY TO ANALYZE THEM, and ONLY if you can't help it, THEN ask here.
Otherwise you will never learn anything if all you do is copy-paste!
Discussion breeds innovation.
Otherwise you will never learn anything if all you do is copy-paste!
Discussion breeds innovation.
- UnAfraid
- L2j Veteran
- Posts: 4199
- Joined: Mon Jul 23, 2007 4:25 pm
- Location: Bulgaria
- Contact:
Re: GeoEngine and movement improvements
Which one is the best approach then?Zoey76 wrote:The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.
- Zoey76
- L2j Inner Circle
- Posts: 7005
- Joined: Tue Aug 11, 2009 3:36 am
Re: GeoEngine and movement improvements
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.UnAfraid wrote:Which one is the best approach then?Zoey76 wrote:The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.
Powered by Eclipse 4.30 | Eclipse Temurin 21 | MariaDB 11.3.2 | L2J Server 2.6.3.0 - High Five
Join our Discord!
Join our Discord!
- jurchiks
- Posts: 6769
- Joined: Sat Sep 19, 2009 4:16 pm
- Location: Eastern Europe
Re: GeoEngine and movement improvements
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.
If you have problems, FIRST TRY SOLVING THEM YOURSELF, and if you get errors, TRY TO ANALYZE THEM, and ONLY if you can't help it, THEN ask here.
Otherwise you will never learn anything if all you do is copy-paste!
Discussion breeds innovation.
Otherwise you will never learn anything if all you do is copy-paste!
Discussion breeds innovation.
- UnAfraid
- L2j Veteran
- Posts: 4199
- Joined: Mon Jul 23, 2007 4:25 pm
- Location: Bulgaria
- Contact:
Re: GeoEngine and movement improvements
He did the same.Zoey76 wrote: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.UnAfraid wrote:Which one is the best approach then?Zoey76 wrote:The geoengine is too complex and creates too many objects in memory, I don't think it's the best approach.
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
- Posts: 704
- Joined: Tue Jul 26, 2005 7:38 pm
Re: GeoEngine and movement improvements
How about improved pathfinding? so that monsters will not get stuck on obstacles
(as shown on Szponiasty's videos).
(as shown on Szponiasty's videos).
-
- Posts: 6
- Joined: Fri May 27, 2011 6:22 am
Re: GeoEngine and movement improvements
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:
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
- L2j Veteran
- Posts: 4199
- Joined: Mon Jul 23, 2007 4:25 pm
- Location: Bulgaria
- Contact:
Re: GeoEngine and movement improvements
Looks really good!Aristo wrote: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/
- Pandragon
- Posts: 704
- Joined: Tue Jul 26, 2005 7:38 pm
Re: GeoEngine and movement improvements
Can this be used to make pathfinding better?
Amazed... still... did not understand anything
Amazed... still... did not understand anything
-
- Posts: 6
- Joined: Fri May 27, 2011 6:22 am
Re: GeoEngine and movement improvements
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.
Also, it will find a route to any visible distances without severe performance degradation.
- Szponiasty
- Advanced User
- Posts: 557
- Joined: Mon Apr 21, 2008 1:31 pm
- Location: Eastern Poland
Re: GeoEngine and movement improvements
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).Aristo wrote: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.
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?
And in the next chronicle they went into space, fighting the evil empire... In a galaxy far, far away xD
- Pandragon
- Posts: 704
- Joined: Tue Jul 26, 2005 7:38 pm
Re: GeoEngine and movement improvements
CellPathFinding -> JumpPointPathfinding?