main.qml

import QtQuick 2.4
import QtQuick.Window 2.2

Window {
    width: 400
    height: 400
    visible: true

    property var map: []

    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
    }

    //property var start: {"id":31,"x":3,"y":1,"G":0,"H":0,"Z":0,"parent":-1}
    //property var end:   {"id":45,"x":4,"y":5,"G":0,"H":0,"Z":0,"parent":-1}
    property var nodes: {"Zero":[]}
    property var openNodesId: []
    property var closedNodesId: []
    property var allNodeIds: []
    property var endNode: { "Zero":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       //(end.x-node.x < 0     ? -1*(end.x-node.x)     : end.x-node.x    )*10
        var modXPlus  = Math.abs(end.x-(node.x+1))*10   //(end.x-(node.x+1) < 0 ? -1*(end.x-(node.x+1)) : end.x-(node.x+1))*10
        var modXMinus = Math.abs(end.x-(node.x-1))*10   //(end.x-(node.x-1) < 0 ? -1*(end.x-(node.x-1)) : end.x-(node.x-1))*10
        var modYZero  = Math.abs(end.y-node.y)*10       //(end.y-node.y < 0     ? -1*(end.y-node.y)     : end.y-node.y    )*10
        var modYPlus  = Math.abs(end.y-(node.y+1))*10   //(end.y-(node.y+1) < 0 ? -1*(end.y-(node.y+1)) : end.y-(node.y+1))*10
        var modYMinus = Math.abs(end.y-(node.y-1))*10   //(end.y-(node.y-1) < 0 ? -1*(end.y-(node.y-1)) : end.y-(node.y-1))*10

        //((newNode.x*10) + newNode.y) < 10 ? "0" + ((newNode.x*10) + newNode.y) : ((newNode.x*10) + newNode.y)
        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 = getNodeId(node.x,node.y)
            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 = getNodeId(node.x,node.y)
            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 = getNodeId(node.x,node.y)
            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 = getNodeId(node.x,node.y)
            friends.push(newNode)
        }

        for (var i = 0; i < friends.length; i++) {
            map[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;
            //console.log("ordering node = ",openNodesId[i]," i=",i," j=",j)
            while(i >= 0 && nodes[openNodesId[i]].F > key.F){
                openNodesId[i + 1] = openNodesId[i];
                i = i - 1;
            }
            openNodesId[i + 1] = key.id;
        }
    }

    function printMap() {
        console.log("\n")
        for (var i = 0; i < map.length; i++) {
            var line = ""
            for (var j = 0; j < map[i].length; j++) {
                line += map[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":-1}
        var end   = {"id":getNodeId(endX+1,endY+1)    ,"x":endX+1  ,"y":endY+1  , "G":0, "H":0, "Z":0, "parent":-1}

        var it = 0;
        // First Round
        nodes[start.id] = start
        allNodeIds.push(start.id)
        //closedNodesId.push(start.id)
        openNodesId.push(start.id)
        //        var friends = getFriends(start,end)
        //        for (var i = 0; i < friends.length; i++) {
        //            console.log("Adding to base: ",friends[i].id)
        //            nodes[friends[i].id] = friends[i]
        //            allNodeIds.push(friends[i].id)
        //            openNodesId.push(friends[i].id)
        //        }
        //        orderByFFromNodes()
        //        console.log("Start Friends Ready\n")
        //        printMap()
        var found = false
        //var friends = []

        while (!found) {
            // Second Round
            it++
            var bestF = openNodesId.shift()
            //console.log("it = "+it," bestF = ",bestF)
            //console.log("Before allNodeIds = ",allNodeIds.toString())
            closedNodesId.push(bestF)
            var current = nodes[bestF]
            //console.log("current = F",bestF.F)
            var friends = getFriends(current,end)
            for (var ix = 0; ix < friends.length; ix++) {
                if (!(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
            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)
                }
            }

            // Add missing nodes to open
            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] = "X"
                        found = true
                    }
                }
            }
            if (!found) { orderByFFromNodes() }
        }
        printMap()
    }

    Component.onCompleted: {
        var theMap = [
                    [1,1,1,1,1,1,1],
                    [1,0,0,0,0,0,1],
                    [1,0,1,1,1,1,1],
                    [1,0,0,0,0,0,1],
                    [1,0,0,0,0,0,1],
                    [1,0,0,0,0,0,1],
                    [1,1,1,1,1,1,1]]
        setMap(theMap)
        printMap()
        search(3,1,4,5)
    }

}