Pathfinding

[Necrotus]

Greetings,

I am using Altimits pixel movement( https://forums.rpgmakerweb.com/index.php?threads/altimit-pixel-movement-0-50β.85408/ ) which is the best pixel movement plugin for my project. However all of the pathfinding plugins(tried all plugins which are in master plugin list and they had either first or second problem listed below) have some
problem when Altimits plugin is on. For example when using Yanflys move route core( http://yanfly.moe/2017/01/21/yep-124-move-route-core-rpg-maker-mv/ ) game starts lagging when pathfinding command is used. Or when using oranges move character to( https://forums.rpgmakerweb.com/index.php?threads/orange-move-character-to.46735/ ) character sprite is
not changing directions but kinda glitching between 2 of them (for example if command is given to move to upper left corner of map then sprite is glitching between back and left one). So I would be grateful for pathfinding script that would work properly with Altimits pixel movement.

If it makes creating the plugin easier then pathfinding doesnt need to use diagonal movement.
Also I should note that I dont use any special sprite when moving diagonally. Just standart 4sided sprites.

I am using RMMV 1.6.1

Thanks for reading.

 

[Andar]

pathfinding is one of the more complex mathematics, especially for more complex maps.
Adding pixel movement to pathfinding is something extremely problematical.

Just think about it: pathfinding works by checking all positions of a map to decide where to move to (no, not exactly all as there are improved path mathematics, but that doesn't matter here).
In default, you have one position per tile. Adding pixel movement with the tilesize of 48x48 means that each tile now has 48x48 = 2304 positions to be tested.
That is what causes the lag - that the pathfinding now has to check tens of thousands of positions instead of a few dozen tiles for moving.

And the only chance to reduce that is to find a pathfinding plugin that was specifically written to go with your pixel movement script, because that can skip a few steps in data handling.
So you basically have to ask the plugin writer of the pixel movement plugin about what he suggests to use.

 

[Jonforum]

it not math the hard part, math for pathfinding are easy and simple to understand.
The hard part it the computing and customisation of your pathfinding algo to your projet in js.

On my side , i build my own dfs pathfinding algo, as you can see, you no need a lot of math, but understanding the concept and how to build it in javascript.

 // calcule le chemin vers un target
    computePathTo(target) {
        const playerCase = $player.inCase;
        // map all path connextion , only if allowed by conditionInteractive of the case
        const globalPathConnextions = this.list_cases.map((c) => {
            if(!c.conditionInteractive || c.conditionInteractive()){return c.pathConnexion};
        }); // nodeConnextions
        const startCaseID = $player.inCase.dataCase.lID;
        const endCaseID = target.dataCase.lID;
        const pattern = this.findShortestPath(globalPathConnextions, startCaseID, endCaseID) || [];
        //const pattern = this.dfs(this.list_cases, 0, );

        const allowed = $huds.displacement._stamina;
        const greenFilter = new PIXI.filters.OutlineFilter (6, 0x1c6600, 1);
        const redFilter = new PIXI.filters.OutlineFilter (8, 0x660000, 1);
        for (let i = pattern.length; i--;) {
            const id = pattern[i];
            if(i>allowed){
                //this.list_cases[id].d.tint = 0xa03d21;
                this.list_cases[id].d._filters = [redFilter]

            }else{
                //this.list_cases[id].d.tint = 0x42f465;
                this.list_cases[id].d._filters = [greenFilter]
            }
        };
        this.pathBuffer = pattern || null;
    };


    // parcour chemin invers a partir du IDcase end et trouver connext vers ID start
    extractShortest(predecessors, end) {
        const nodes = [];
        let u = end;
        while (u !== void 0) {
            nodes.push(u);
            u = predecessors[u];
        };
        nodes.reverse();
        return nodes;
    };

    addToOpen(cost, vertex, open) {
        const key = "" + cost;
        if (!open[key]) open[key] = [];
        open[key].push(+vertex);
    }

    findShortestPath(globalPathConnextions, startCaseID, endCaseID) {
        const nodes = [startCaseID,endCaseID];
        let startID      = nodes.shift();
        let path         = []           ;
        let endID        = null         ;
        let connectedIDList = null         ;
        let shortest     = null         ;
        while (nodes.length) { // force one pass
            endID = nodes.shift();
            connectedIDList = this.findPaths(globalPathConnextions, startID, endID); //
            if (connectedIDList) {
                shortest = this.extractShortest(connectedIDList, endID);
                if (nodes.length) {
                    path.push.apply(path, shortest.slice(0, -1));
                } else {
                    return path.concat(shortest); // finish succeed
                }
            } else { return null }; // break
            startID = endID;
        }
    }

    findPaths(globalPathConnextions, startID, endID) {
        const costs = {};
        const connectedIDList = {};
        let open = {'0': [startID]}; // id:start
        let keys = null;
        costs[startID] = 0;
        while (open) {
            if(!(keys = Object.keys(open)).length) break;
            keys.sort((a,b)=>{return parseFloat (a) - parseFloat (b)});
            let key = keys[0];
            let bucket = open[key];
            let node = bucket.shift();
            let currentCost = parseFloat(key);
            let adjacentNodes = globalPathConnextions[node] || {};
            if (!bucket.length) delete open[key];
            for (const vertex in adjacentNodes) {
                let cost = adjacentNodes[vertex],
                    totalCost = cost + currentCost,
                    vertexCost = costs[vertex];
                if ((vertexCost === void 0) || (vertexCost > totalCost)) {
                    costs[vertex] = totalCost;
                    this.addToOpen(totalCost, vertex, open);
                    connectedIDList[vertex] = node;
                };
            };
        };
        if (costs[endID] === void 0) { return null; }
        else { return connectedIDList; };
    };
   

    getDirXFromId (id1,id2) {
        if (Number.isFinite(id1) && Number.isFinite(id2) ){
            const c1 = this.list_cases[id1].x;
            const c2 = this.list_cases[id2].x;
            return c1<c2 && 6 || c2<c1 && 4 || false;
        };
        return false;
    };

you can take a look here, you will can see all modern pathfinding algo for js.
https://qiao.github.io/PathFinding.js/visual/
The hard part it to customise the algo for your custom projet, you need know javascript in deep, but no need good math.
You have somme good tutorial on the web that will help you.
For pixel pathfinding the best algo are A*

 

[Necrotus]

Thanks a lot for explanation. It seems like I need to dig into js more then I expected.

 

[caethyril]

Just throwing this out there: you may want to look up a pre-processing algorithm like jump-point search. Like Andar says, the major obstacle here is the node count.