AStarQuick.qml

/*
//    PatherQuick: AStarQuick.qml
//    by gabriel.ufrj@gmail.com
//    more info at:
//                   http://gaf.impa.br   or    http://www.gabrieldesign.com.br
//
//    This file is part of PatherQuick.
//
//    PatherQuick is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    PatherQuick is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
*/

import QtQuick 2.4

Item {

    property var map: []
    property var thinkMap: []
    property var pathMap: []
    property var nodes: {"Zero":[]}
    property var openNodesId: []
    property var closedNodesId: []
    property var allNodeIds: []
    property var endNode: { "Zero":0 } // This object holds the last search result.

    function setMap(newMap) {
        var w = newMap[0].length + 2
        var h = newMap.length + 2
        var outMap = []
        for (var i = 0; i < h; i++) {
            var outH = []
            for (var j = 0; j < w; j++) {
                if (i == 0 || j == 0 || i == h-1 || j == w-1 ) {
                    outH.push(1)
                } else {
                    outH.push(newMap[i-1][j-1])
                }
            }
            outMap.push(outH)
        }
        map = outMap
        cloneMaps()
    }

    function cloneMaps() {
        pathMap = []
        thinkMap = []
        for (var i = 0; i < map.length; i++) {
            thinkMap.push(map[i].slice(0)); pathMap.push(map[i].slice(0))
        }
    }

    function getNodeId(nodeX,nodeY) {
        var firstComponent = nodeX < 10 ? "0" + nodeX : "" + nodeX
        var secondComponent = nodeY < 10 ? "0" + nodeY : "" + nodeY
        return firstComponent + secondComponent
    }

    function getFriends(node,end) {
        var friends = []
        var modXZero  = Math.abs(end.x-node.x)*10
        var modXPlus  = Math.abs(end.x-(node.x+1))*10
        var modXMinus = Math.abs(end.x-(node.x-1))*10
        var modYZero  = Math.abs(end.y-node.y)*10
        var modYPlus  = Math.abs(end.y-(node.y+1))*10
        var modYMinus = Math.abs(end.y-(node.y-1))*10

        var newNode;
        if (map[node.y][node.x + 1] != 1) {
            newNode = {"x":node.x+1,"y":node.y,"G":node.G+10,"H":modXPlus,"F":node.G+10+modXPlus+modYZero,"Z":3}
            newNode.id = getNodeId(newNode.x,newNode.y)
            newNode.parent = node.id
            friends.push(newNode)
        }
        if (map[node.y][node.x - 1] != 1) {
            newNode = {"x":node.x-1,"y":node.y,"G":node.G+10,"H":modXMinus,"F":node.G+10+modXMinus+modYZero,"Z":4}
            newNode.id = getNodeId(newNode.x,newNode.y)
            newNode.parent = node.id
            friends.push(newNode)
        }

        if (map[node.y + 1][node.x] != 1) {
            newNode = {"x":node.x,"y":node.y+1,"G":node.G+10,"H":modYPlus,"F":node.G+10+modYPlus+modXZero,"Z":7}
            newNode.id = getNodeId(newNode.x,newNode.y)
            newNode.parent = node.id
            friends.push(newNode)
        }
        if (map[node.y - 1][node.x] != 1) {
            newNode = {"x":node.x,"y":node.y-1,"G":node.G+10,"H":modYMinus,"F":node.G+10+modYMinus+modXZero,"Z":8}
            newNode.id = getNodeId(newNode.x,newNode.y)
            newNode.parent = node.id
            friends.push(newNode)
        }

        for (var i = 0; i < friends.length; i++) {
            thinkMap[friends[i].y][friends[i].x] = 3
        }

        return friends
    }

    function orderByFFromNodes() {
        var j,i,key;
        for(j = 1; j < openNodesId.length; j++){
            key = nodes[openNodesId[j]];
            i = j - 1;
            while(i >= 0 && nodes[openNodesId[i]].F > key.F){
                openNodesId[i + 1] = openNodesId[i];
                i = i - 1;
            }
            openNodesId[i + 1] = key.id;
        }
    }

    function printMap(pMap) {
        console.log("\n")
        for (var i = 0; i < pMap.length; i++) {
            var line = ""
            for (var j = 0; j < pMap[i].length; j++) {
                line += pMap[i][j] + " "
            }
            console.log(line)
        }
        console.log("\n")
    }

    function search(startX,startY,endX,endY) {

        var start = {"id":getNodeId(startX+1,startY+1),"x":startX+1,"y":startY+1, "G":0, "H":0, "Z":0, "parent":"XXXX"}
        var end   = {"id":getNodeId(endX+1,endY+1)    ,"x":endX+1  ,"y":endY+1  , "G":0, "H":0, "Z":0, "parent":"XXXX"}
        var found = false

        // Add the first node... (start)
        nodes[start.id] = start
        allNodeIds.push(start.id)
        openNodesId.push(start.id)

        while (!found) {
            var bestF = openNodesId.shift()
            if (!(closedNodesId.indexOf(bestF) >= 0)) {
                closedNodesId.push(bestF)
            }
            console.log("** Analyze node = "+nodes[bestF].id)
            var current = nodes[bestF]
            var friends = getFriends(current,end)
            console.log("Node has = "+friends.length+" friends!")

            console.log("closed nodes:",closedNodesId.toString())
            console.log("open nodes:",openNodesId.toString())

            // Add unknown nodes to the main node array
            for (var ix = 0; ix < friends.length; ix++) {
                if (!nodes.hasOwnProperty(friends[ix].id)) { //!(openNodesId.indexOf(friends[ix].id) >= 0) && !(closedNodesId.indexOf(friends[ix].id) >=0)) {
                    console.log("add friend to nodes = "+friends[ix].id)
                    nodes[friends[ix].id] = (friends[ix])
                    allNodeIds.push(friends[ix].id)
                }
            }
            console.log("After allNodeIds = ",allNodeIds.toString())

            // Remove closed nodes which are already closed
            var newFriendList = []
            for (ix = 0; ix < friends.length; ix++) {
                if (!(closedNodesId.indexOf(friends[ix].id) >= 0)) {
                    console.log("remove closed friends = "+friends[ix].id)
                    //friends.splice(ix,1)
                    newFriendList.push(friends[ix])
                }
            }
            friends = newFriendList
            console.log("After close Node has = "+friends.length+" friends!")

            // Add new nodes to open (which aren't already closed or already present)
            for (ix = 0; ix < friends.length; ix++) {
                if (!(openNodesId.indexOf(friends[ix].id) >= 0)) {
                    if (friends[ix].id != end.id) {
                        console.log("add new open friends = "+friends[ix].id)
                        openNodesId.push(friends[ix].id)
                    } else {
                        console.log("Search and Found!")
                        end = friends[ix]
                        endNode = end
                        map[start.y][start.x] = "S"
                        map[end.y][end.x] = "E"
                        thinkMap[start.y][start.x] = "S"
                        thinkMap[end.y][end.x] = "E"
                        found = true
                    }
                }
            }
            if (openNodesId.length == 0) {
                console.log("No possible path....   :(")
                found = true
                endNode = start
            }

            if (!found) { orderByFFromNodes() }
        }
    }

    function pathArray() {
        var tempNode = endNode
        var route = []
        while (tempNode.parent != "XXXX") {
            route.unshift([tempNode.x-1,tempNode.y-1]) // for object style {"x":tempNode.x-1,"y":tempNode.y-1})
            pathMap[tempNode.y][tempNode.x] = "X"
            tempNode = nodes[tempNode.parent]
        }
        pathMap[tempNode.y][tempNode.x] = "S"
        pathMap[endNode.y][endNode.x]   = "E"
        if (tempNode.x == endNode.x && tempNode.y == endNode.y) { pathMap[tempNode.y][tempNode.x] = "!" }
        route.unshift([tempNode.x-1,tempNode.y-1]) // Start position
        return route
    }

}