Necrotus

Villager
Member
Joined
Jul 23, 2018
Messages
5
Reaction score
0
First Language
Slovak
Primarily Uses
RMMV
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

Veteran
Veteran
Joined
Mar 5, 2013
Messages
34,271
Reaction score
8,724
First Language
German
Primarily Uses
RMMV
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

Veteran
Veteran
Joined
Mar 28, 2016
Messages
1,634
Reaction score
1,457
First Language
French
Primarily Uses
RMMV
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.
PHP:
 // 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

Villager
Member
Joined
Jul 23, 2018
Messages
5
Reaction score
0
First Language
Slovak
Primarily Uses
RMMV
Thanks a lot for explanation. It seems like I need to dig into js more then I expected.
 

caethyril

^_^
Global Mod
Joined
Feb 21, 2018
Messages
2,957
Reaction score
2,292
First Language
EN
Primarily Uses
RMMZ
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.
 

Latest Threads

Latest Posts

Latest Profile Posts


AABS laser beams features:
1,Shoot penetrating laser beams for player's normal attack
2,Beam's width/damage/comsumes/loot can be controlled by events/variables with great flexibility
3,Beam can rebound to walls or certain regionID
4,Can play SE when shooting beams
5,Beam's images can be solid images or animated ones.
Surprising nobody, it turns out "next Friday" for the next Jump into Javascript has become "possibly Sunday if you're lucky" XD
Folks, if anyone sends you a message inviting you to add their API to your game, please report them. We don't want people spamming our members asking them to add stuff to their games for their own (or others') benefit. We've updated the forum rules to confirm this.
I'm listening to iiluminaughtii talking about the secrets behind shady businesses and scams. Meanwhile I'm writing a fanfic about Sephiroth from FF7, one specifically for my stepmom. I'll get to give it to her, too, because my boss said I could take the holidays off! Dec. 22-27 I will be in Orlando, and maybe Fort Myers too, visiting my dad and stepmom!
Of course, I bought a handful of games on the Steam Black Friday sale. Will I try them? Will I complete any? Who knows...

Forum statistics

Threads
117,015
Messages
1,103,835
Members
152,911
Latest member
WakeNBake
Top