Pathfinding

Discussion in 'JS Plugin Requests' started by Necrotus, Dec 16, 2018.

  1. Necrotus

    Necrotus Villager Member

    Messages:
    5
    Likes Received:
    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.
     
    #1
  2. Andar

    Andar Veteran Veteran

    Messages:
    28,002
    Likes Received:
    6,327
    Location:
    Germany
    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.
     
    #2
    Necrotus and Wavelength like this.
  3. Jonforum

    Jonforum Veteran Veteran

    Messages:
    1,568
    Likes Received:
    1,324
    Location:
    Canada / Québec
    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(globalPathConnextionsstartCaseIDendCaseID) || [];
            
    //const pattern = this.dfs(this.list_cases, 0, );

            
    const allowed $huds.displacement._stamina;
            const 
    greenFilter = new PIXI.filters.OutlineFilter (60x1c66001);
            const 
    redFilter = new PIXI.filters.OutlineFilter (80x6600001);
            for (
    let i pattern.lengthi--;) {
                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(predecessorsend) {
            const 
    nodes = [];
            
    let u end;
            while (
    !== void 0) {
                
    nodes.push(u);
                
    predecessors[u];
            };
            
    nodes.reverse();
            return 
    nodes;
        };

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

        
    findShortestPath(globalPathConnextionsstartCaseIDendCaseID) {
            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(globalPathConnextionsstartIDendID); //
                
    if (connectedIDList) {
                    
    shortest this.extractShortest(connectedIDListendID);
                    if (
    nodes.length) {
                        
    path.push.apply(pathshortest.slice(0, -1));
                    } else {
                        return 
    path.concat(shortest); // finish succeed
                    
    }
                } else { return 
    null }; // break
                
    startID endID;
            }
        }

        
    findPaths(globalPathConnextionsstartIDendID) {
            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.lengthdelete 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(totalCostvertexopen);
                        
    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 && || c2<c1 && || 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*
     
    #3
    Necrotus likes this.
  4. Necrotus

    Necrotus Villager Member

    Messages:
    5
    Likes Received:
    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.
     
    #4
  5. caethyril

    caethyril ^_^ Veteran

    Messages:
    947
    Likes Received:
    587
    Location:
    UK
    First Language:
    English
    Primarily Uses:
    RMMV
    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.
     
    #5
    Necrotus likes this.

Share This Page