OSBot's (First?) Web Walker

[Pandemic]

Hello everyone!

 

This web walker ONLY contains the path finding algorithm and currently has LIMITED nodes (check out my AIO Walker for what I currently have), and it also has NO obstacle handling (at the moment).

 

A little info on the path finder:

 

My path finding now uses an algorithm similar to A* and it works extremely well for its purpose.

 

I plan on finding/collecting/adding more surface nodes to it whenever I get a chance.

 

ALSO (for developers):

 

You should add the nodes path by path (do not mix the path positions as that will take longer), they don't have to be connecting or anything (my path finder will connect your nodes by itself).

 

This web walker essentials takes your starting position (player's position for instance) and your end position (wherever you want to go), and generates the shortest path.

 

Anyways, here are the two Java files you'll need to use it:

 

You're about to see 400 positions, this will be simplified then compressed and parsed at a later stage of development.

 

WebWalker.java:

import org.osbot.script.rs2.map.Position;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * Webwalker.java
 * <p/>
 * Created by Pandemic on 1/22/14.
 */
public class WebWalker {

    private final ArrayList<WalkNode> walkNodes = new ArrayList<WalkNode>();

    private final Position[] positions = { new Position(3222, 3218, 0), new Position(3230, 3218, 0), new Position(3238, 3225, 0), new Position(3248, 3226, 0), new Position(3258, 3226, 0), new Position(3261, 3236, 0), new Position(3256, 3245, 0), new Position(3252, 3255, 0), new Position(3250, 3265, 0), new Position(3244, 3273, 0), new Position(3239, 3283, 0), new Position(3240, 3293, 0), new Position(3239, 3303, 0), new Position(3231, 3309, 0), new Position(3223, 3315, 0), new Position(3218, 3324, 0), new Position(3212, 3332, 0), new Position(3205, 3342, 0), new Position(3201, 3352, 0), new Position(3207, 3360, 0), new Position(3210, 3370, 0), new Position(3211, 3380, 0), new Position(3211, 3390, 0), new Position(3211, 3400, 0), new Position(3212, 3410, 0), new Position(3212, 3416, 0), new Position(3212, 3426, 0), new Position(3209, 3426, 0), new Position(3199, 3427, 0), new Position(3189, 3428, 0), new Position(3179, 3428, 0), new Position(3169, 3428, 0), new Position(3161, 3421, 0), new Position(3153, 3415, 0), new Position(3144, 3415, 0), new Position(3134, 3416, 0), new Position(3124, 3414, 0), new Position(3115, 3419, 0), new Position(3105, 3420, 0), new Position(3095, 3419, 0), new Position(3085, 3418, 0), new Position(3078, 3418, 0), new Position(3068, 3417, 0), new Position(3059, 3412, 0), new Position(3049, 3410, 0), new Position(3041, 3417, 0), new Position(3034, 3425, 0), new Position(3024, 3423, 0), new Position(3015, 3428, 0), new Position(3004, 3431, 0), new Position(2994, 3429, 0), new Position(2984, 3427, 0), new Position(2977, 3419, 0), new Position(2969, 3413, 0), new Position(2966, 3403, 0), new Position(2965, 3393, 0), new Position(2965, 3383, 0), new Position(2965, 3373, 0), new Position(3099, 3419, 0), new Position(3093, 3427, 0), new Position(3092, 3437, 0), new Position(3092, 3447, 0), new Position(3091, 3457, 0), new Position(3087, 3464, 0), new Position(3080, 3472, 0), new Position(3080, 3482, 0), new Position(3086, 3490, 0), new Position(3087, 3494, 0), new Position(2968, 3413, 0), new Position(2958, 3417, 0), new Position(2950, 3424, 0), new Position(2948, 3434, 0), new Position(2947, 3444, 0), new Position(2939, 3451, 0), new Position(2929, 3450, 0), new Position(2920, 3455, 0), new Position(2910, 3456, 0), new Position(2905, 3457, 0), new Position(2896, 3452, 0), new Position(2890, 3444, 0), new Position(2888, 3434, 0), new Position(2887, 3427, 0), new Position(2880, 3427, 0), new Position(2872, 3433, 0), new Position(2872, 3443, 0), new Position(2875, 3453, 0), new Position(2873, 3463, 0), new Position(2870, 3468, 0), new Position(2868, 3478, 0), new Position(2868, 3488, 0), new Position(2873, 3497, 0), new Position(2877, 3507, 0), new Position(2875, 3517, 0), new Position(2869, 3525, 0), new Position(2859, 3525, 0), new Position(2849, 3526, 0), new Position(2839, 3527, 0), new Position(2833, 3527, 0), new Position(2823, 3524, 0), new Position(2813, 3521, 0), new Position(2803, 3517, 0), new Position(2796, 3509, 0), new Position(2797, 3499, 0), new Position(2807, 3496, 0), new Position(2816, 3501, 0), new Position(2826, 3498, 0), new Position(2832, 3490, 0), new Position(2835, 3480, 0), new Position(2839, 3470, 0), new Position(2845, 3462, 0), new Position(2848, 3452, 0), new Position(2853, 3447, 0), new Position(2857, 3437, 0), new Position(2849, 3431, 0), new Position(2840, 3434, 0), new Position(2830, 3435, 0), new Position(2820, 3437, 0), new Position(2810, 3436, 0), new Position(2809, 3434, 0), new Position(2799, 3431, 0), new Position(2790, 3436, 0), new Position(2782, 3443, 0), new Position(2777, 3452, 0), new Position(2769, 3459, 0), new Position(2763, 3467, 0), new Position(2757, 3475, 0), new Position(2751, 3478, 0), new Position(2741, 3480, 0), new Position(2731, 3485, 0), new Position(2721, 3485, 0), new Position(2712, 3484, 0), new Position(2702, 3484, 0), new Position(2692, 3485, 0), new Position(2683, 3480, 0), new Position(2680, 3470, 0), new Position(2672, 3464, 0), new Position(2670, 3454, 0), new Position(2662, 3448, 0), new Position(2655, 3440, 0), new Position(2649, 3432, 0), new Position(2646, 3422, 0), new Position(2646, 3412, 0), new Position(2646, 3402, 0), new Position(2646, 3394, 0), new Position(2646, 3384, 0), new Position(2644, 3374, 0), new Position(2637, 3373, 0), new Position(2637, 3363, 0), new Position(2636, 3353, 0), new Position(2636, 3343, 0), new Position(2636, 3336, 0), new Position(2645, 3331, 0), new Position(2650, 3322, 0), new Position(2654, 3312, 0), new Position(2646, 3305, 0), new Position(2640, 3303, 0), new Position(2636, 3300, 0), new Position(2632, 3297, 0), new Position(2622, 3297, 0), new Position(2612, 3298, 0), new Position(2606, 3290, 0), new Position(2605, 3284, 0), new Position(2609, 3279, 0), new Position(2605, 3275, 0), new Position(2599, 3271, 0), new Position(2601, 3261, 0), new Position(2593, 3254, 0), new Position(2599, 3246, 0), new Position(2604, 3237, 0), new Position(2612, 3231, 0), new Position(2620, 3225, 0), new Position(2624, 3215, 0), new Position(2626, 3205, 0), new Position(2625, 3195, 0), new Position(2620, 3185, 0), new Position(2619, 3175, 0), new Position(2622, 3165, 0), new Position(2623, 3155, 0), new Position(2623, 3145, 0), new Position(2621, 3135, 0), new Position(2618, 3125, 0), new Position(2618, 3115, 0), new Position(2616, 3105, 0), new Position(2608, 3099, 0), new Position(2605, 3093, 0), new Position(2643, 3409, 0), new Position(2635, 3402, 0), new Position(2629, 3394, 0), new Position(2619, 3390, 0), new Position(2609, 3388, 0), new Position(2599, 3387, 0), new Position(2589, 3389, 0), new Position(2580, 3394, 0), new Position(2570, 3396, 0), new Position(2560, 3399, 0), new Position(2550, 3399, 0), new Position(2540, 3400, 0), new Position(2534, 3401, 0), new Position(2524, 3399, 0), new Position(2514, 3395, 0), new Position(2506, 3389, 0), new Position(2496, 3385, 0), new Position(2490, 3388, 0), new Position(2482, 3388, 0), new Position(2473, 3387, 0), new Position(2464, 3382, 0), new Position(2461, 3381, 0), new Position(2461, 3389, 0), new Position(2461, 3399, 0), new Position(2460, 3409, 0), new Position(2458, 3419, 0), new Position(2457, 3426, 0), new Position(2732, 3483, 0), new Position(2737, 3492, 0), new Position(2742, 3501, 0), new Position(2741, 3511, 0), new Position(2742, 3521, 0), new Position(2741, 3527, 0), new Position(2739, 3537, 0), new Position(2729, 3540, 0), new Position(2723, 3542, 0), new Position(2713, 3543, 0), new Position(2703, 3543, 0), new Position(2693, 3543, 0), new Position(2683, 3546, 0), new Position(2675, 3552, 0), new Position(2666, 3557, 0), new Position(2660, 3560, 0), new Position(2659, 3570, 0), new Position(2653, 3578, 0), new Position(2653, 3588, 0), new Position(2654, 3596, 0), new Position(2655, 3606, 0), new Position(2661, 3614, 0), new Position(2662, 3624, 0), new Position(2666, 3634, 0), new Position(2663, 3644, 0), new Position(2661, 3654, 0), new Position(2658, 3659, 0), new Position(2966, 3378, 0), new Position(2976, 3378, 0), new Position(2986, 3374, 0), new Position(2994, 3368, 0), new Position(3003, 3363, 0), new Position(3006, 3353, 0), new Position(3008, 3343, 0), new Position(3006, 3333, 0), new Position(3007, 3323, 0), new Position(3008, 3313, 0), new Position(3007, 3306, 0), new Position(3007, 3296, 0), new Position(3007, 3286, 0), new Position(3002, 3277, 0), new Position(2992, 3277, 0), new Position(2984, 3269, 0), new Position(2974, 3266, 0), new Position(2971, 3256, 0), new Position(2963, 3250, 0), new Position(2957, 3242, 0), new Position(2955, 3232, 0), new Position(2958, 3222, 0), new Position(3010, 3280, 0), new Position(3019, 3275, 0), new Position(3024, 3268, 0), new Position(3020, 3261, 0), new Position(3020, 3251, 0), new Position(3021, 3243, 0), new Position(3026, 3276, 0), new Position(3036, 3277, 0), new Position(3046, 3276, 0), new Position(3056, 3276, 0), new Position(3066, 3278, 0), new Position(3076, 3279, 0), new Position(3081, 3270, 0), new Position(3081, 3260, 0), new Position(3084, 3251, 0), new Position(3090, 3247, 0), new Position(3095, 3247, 0), new Position(3096, 3248, 0), new Position(3101, 3239, 0), new Position(3107, 3231, 0), new Position(3117, 3228, 0), new Position(3127, 3227, 0), new Position(3137, 3231, 0), new Position(3146, 3236, 0), new Position(3156, 3237, 0), new Position(3166, 3240, 0), new Position(3176, 3242, 0), new Position(3186, 3244, 0), new Position(3195, 3240, 0), new Position(3205, 3240, 0), new Position(3215, 3240, 0), new Position(3225, 3237, 0), new Position(3231, 3229, 0), new Position(3075, 3280, 0), new Position(3083, 3286, 0), new Position(3091, 3292, 0), new Position(3101, 3293, 0), new Position(3110, 3298, 0), new Position(3115, 3307, 0), new Position(3121, 3315, 0), new Position(3129, 3322, 0), new Position(3134, 3331, 0), new Position(3134, 3341, 0), new Position(3135, 3351, 0), new Position(3136, 3361, 0), new Position(3133, 3371, 0), new Position(3130, 3375, 0), new Position(3124, 3383, 0), new Position(3114, 3388, 0), new Position(3106, 3394, 0), new Position(3102, 3404, 0), new Position(3100, 3414, 0), new Position(3099, 3420, 0), new Position(3236, 3224, 0), new Position(3246, 3226, 0), new Position(3256, 3226, 0), new Position(3266, 3228, 0), new Position(3276, 3227, 0), new Position(3282, 3219, 0), new Position(3292, 3216, 0), new Position(3300, 3210, 0), new Position(3301, 3200, 0), new Position(3294, 3192, 0), new Position(3292, 3182, 0), new Position(3222, 3429, 0), new Position(3232, 3429, 0), new Position(3242, 3430, 0), new Position(3252, 3430, 0), new Position(3262, 3429, 0), new Position(3272, 3428, 0), new Position(3282, 3428, 0), new Position(3287, 3419, 0), new Position(3291, 3409, 0), new Position(3292, 3399, 0), new Position(3293, 3389, 0), new Position(3296, 3379, 0), new Position(3299, 3369, 0), new Position(3298, 3359, 0), new Position(3302, 3349, 0), new Position(3299, 3339, 0), new Position(3290, 3334, 0), new Position(3280, 3333, 0), new Position(3283, 3322, 0), new Position(3283, 3312, 0), new Position(3286, 3302, 0), new Position(3286, 3292, 0), new Position(3285, 3282, 0), new Position(3289, 3272, 0), new Position(3292, 3262, 0), new Position(3297, 3252, 0), new Position(3300, 3242, 0), new Position(3306, 3234, 0), new Position(3309, 3224, 0), new Position(3304, 3216, 0), new Position(3303, 3206, 0), new Position(3297, 3198, 0), new Position(3295, 3188, 0), new Position(2450, 3089, 0), new Position(2455, 3080, 0), new Position(2461, 3072, 0), new Position(2471, 3071, 0), new Position(2481, 3071, 0), new Position(2491, 3072, 0), new Position(2498, 3080, 0), new Position(2501, 3090, 0), new Position(2509, 3096, 0), new Position(2517, 3102, 0), new Position(2525, 3102, 0), new Position(2529, 3092, 0), new Position(2539, 3092, 0), new Position(2549, 3092, 0), new Position(2559, 3091, 0), new Position(2569, 3091, 0), new Position(2575, 3092, 0), new Position(2585, 3096, 0), new Position(2595, 3097, 0), new Position(2604, 3096, 0), new Position(2791, 3434, 0), new Position(2781, 3432, 0), new Position(2771, 3428, 0), new Position(2761, 3423, 0), new Position(2753, 3417, 0), new Position(2748, 3407, 0), new Position(2746, 3397, 0), new Position(2744, 3387, 0), new Position(2741, 3377, 0), new Position(2742, 3367, 0), new Position(2737, 3358, 0), new Position(2732, 3349, 0), new Position(2726, 3341, 0), new Position(2721, 3331, 0), new Position(2714, 3323, 0), new Position(2705, 3318, 0), new Position(2698, 3310, 0), new Position(2690, 3304, 0), new Position(2680, 3303, 0), new Position(2673, 3304, 0), new Position(2663, 3305, 0), new Position(2655, 3307, 0) };

    public ArrayList<WalkNode> getAllNodes() {
        return walkNodes;
    }

    public WebWalker() {
        fillWalkNodes();
        connectWalkNodes();
    }

    private void connectWalkNodes() {
        int walkNodesSize = walkNodes.size();
        for (int i = 1; i < walkNodesSize; i++) {
            WalkNode node = walkNodes.get(i);
            WalkNode prev = walkNodes.get(i - 1);
            if (node.getPosition().distance(prev.getPosition()) <= 13 && i != walkNodes.size() - 1) {
                node.addNeighbor(prev);
            }
        }
        ArrayList<WalkNode> removeList = new ArrayList<WalkNode>();
        for (int i = 0; i < walkNodesSize; i++) {
            for (WalkNode n : walkNodes) {
                if (!n.equals(walkNodes.get(i)) && n.getPosition().distance(walkNodes.get(i).getPosition()) < 5) {
                    if (!removeList.contains(n)) {
                        removeList.add(n);
                        removeList.add(walkNodes.get(i));
                    }
                }
                if (!n.equals(walkNodes.get(i)) && !n.getNeighbors().contains(walkNodes.get(i)) && n.getPosition().distance(walkNodes.get(i).getPosition()) < 10) {
                    n.addNeighbor(walkNodes.get(i));
                }
            }
        }
        for (int i = 0; i < removeList.size(); i += 2) {
            ArrayList<WalkNode> neighbors = walkNodes.get(walkNodes.indexOf(removeList.get(i))).getNeighbors();
            walkNodes.remove(removeList.get(i));
            walkNodes.get(walkNodes.indexOf(removeList.get(i + 1))).addNeighbors(neighbors);
        }
    }

    private WalkNode getConnectingNode(WalkNode node, int excludeIndex) {
        Position nodePosition = node.getPosition();
        int walkNodesSize = walkNodes.size();
        int distance = 1000;
        int index = -1;
        for (int i = 0; i < walkNodesSize; i++) {
            if (i == excludeIndex || walkNodes.get(i).getNeighbors().contains(node))
                continue;
            int nodeDistance = nodePosition.distance(walkNodes.get(i).getPosition());
            if (nodeDistance < distance) {
                distance = nodeDistance;
                index = i;
            }
        }
        return walkNodes.get(index);
    }

    private void fillWalkNodes() {
        for (int i = 0; i < positions.length; i++) {
            walkNodes.add(new WalkNode(positions[i]));
        }
    }

    public Position[] getPath(WalkNode startNode, WalkNode endNode) {
        generateAllPaths(startNode, endNode);
        ArrayList<Position> path = new ArrayList<Position>();
        for (WalkNode node = endNode; node != null; node = node.getPreviousNode())
            path.add(node.getPosition());
        Collections.reverse(path);
        return path.toArray(new Position[0]);
    }

    private void generateAllPaths(WalkNode startNode, WalkNode endNode) {
        startNode.setMinimumDistance(0.0);
        PriorityQueue<WalkNode> walkNodeQueue = new PriorityQueue<WalkNode>();
        walkNodeQueue.add(startNode);
        while (!walkNodeQueue.isEmpty()) {
            WalkNode currentNode = walkNodeQueue.poll();
            for (WalkNode node : currentNode.getNeighbors()) {
                double minDistance = node.getApproximateDistance(endNode) + currentNode.getPosition().distance(node.getPosition()) + currentNode.getMinimumDistance();
                if (node.getMinimumDistance() > minDistance) {
                    walkNodeQueue.remove(node);
                    node.setMinimumDistance(minDistance);
                    node.setPreviousNode(currentNode);
                    walkNodeQueue.add(node);
                }
            }
        }
    }

    public WalkNode getClosestNode(Position position) {
        int walkNodesSize = walkNodes.size();
        int distance = 1000;
        int index = -1;
        for (int i = 0; i < walkNodesSize; i++) {
            int nodeDistance = position.distance(walkNodes.get(i).getPosition());
            if (nodeDistance < distance) {
                distance = nodeDistance;
                index = i;
            }
        }
        return walkNodes.get(index);
    }

}

and

 

WalkNode.java:

import org.osbot.script.rs2.map.Position;

import java.util.ArrayList;

/**
 * WalkNode.java
 * <p/>
 * Created by Pandemic on 1/22/14.
 */
public class WalkNode implements Comparable<WalkNode> {

    private final Position position;

    private final ArrayList<WalkNode> neighbors = new ArrayList<WalkNode>();

    private double minimumDistance = Double.POSITIVE_INFINITY;

    private WalkNode previousNode;

    public WalkNode(Position position) {
        this.position = position;
    }

    public void addNeighbors(ArrayList<WalkNode> neighbor) {
        for (WalkNode n : neighbor)
            addNeighbor(n);
    }

    public void addNeighbor(WalkNode node) {
        if (!neighbors.contains(node)) {
            neighbors.add(node);
            node.addNeighbor(this);
        }
    }

    public ArrayList<WalkNode> getNeighbors() {
        return neighbors;
    }

    public Position getPosition() {
        return position;
    }

    public void setMinimumDistance(double distance) {
        minimumDistance = distance;
    }

    public double getMinimumDistance() {
        return minimumDistance;
    }

    public void setPreviousNode(WalkNode previousNode) {
        this.previousNode = previousNode;
    }

    public WalkNode getPreviousNode() {
        return previousNode;
    }

    public int getApproximateDistance(WalkNode node) {
        return position.distance(node.getPosition());
    }

    public int compareTo(WalkNode node) {
        return Double.compare(minimumDistance, node.getMinimumDistance());
    }

}

You'll have to add nodes to the webwalker before it will try and find paths (don't think it'll just make them up ).

 

Here's an example for use in your script:

@ScriptManifest(version = 1.0, author = "Pandemic", name = "Web Walk Test", info = "Boom")
public class WebWalkerTest extends Script {

    private WebWalker webWalker;

    private Position[] path;

    @Override
    public void onStart() {
        webWalker = new WebWalker(this);
        path = webWalker.getPath(webWalker.getClosestNode(myPosition()), webWalker.getClosestNode(new Position(3221, 3217, 0)));
    }
}

I'd also like to thank @FrostBug for his suggestion on changing to a quicker path finding algorithm

 

Thanks for checking this out!

Edited January 24, 2014 by Pandemic

[Celeos]

How are you storing the nodes?

[Pandemic]

How are you storing the nodes?

 

Currently I'm not storing any nodes, that's for you to add.

 

Just change the fillWalkNodes() to add your nodes to walkNodes array list

[Celeos]

Currently I'm not storing any nodes, that's for you to add.

 

Just change the fillWalkNodes() to add your nodes to walkNodes array list

Oh okay. So this is similar to regular array walking?

[Pandemic]

Oh okay. So this is similar to regular array walking?

 

Not at all, this is a web walker.

 

Say you add the nodes (positions) from lumbridge to varrock, and varrock to falador, and falador to edgeville.

 

You can (given you're near any node) generate a path to any other node in your list (you could get the path from lumbridge to edgeville in one line).

 

Also, once I add all of the nodes, you can essentials walk anywhere given you know where the ending position is and it will generate a path.

[FrostBug]

If the cost of a graph edge is measured in distance, why would you use Dijkstra and not A*?

A* Would reach the destination much faster, since it would search a lot less nodes. Using Euclid or a modified Manhattan heuristic would provide good results

Edited January 22, 2014 by FrostBug

[Pandemic]

If the cost of graph edges is measured in distance, why would you use Dijkstra and not A*?

A* Would reach the destination much faster, since it would search a lot less nodes. Using Euclid or a modified Manhattan heuristic would provide good results

 

A* uses heuristics, which I'm not interested in doing (I'd like to make sure the shortest path is available, not just guesses or approximations).

 

"Dijkstra is a special case for A* (when the heuristics is zero)."

 

Going through more nodes (in my opinion) is a good thing, as it opens it up to seeing more available paths (even while being slightly less efficient).

 

I managed to add and connect 111 nodes in 34ms, so efficiency really isn't an issue here.

 

Ultimately, it works, and that's all that really matters, right? 

Edited January 22, 2014 by Pandemic

[FrostBug]

A* uses heuristics, which I'm not interested in doing (I'd like to make sure the shortest path is available, not just guesses or approximations).

 

Going through more nodes (in my opinion) is a good thing, as it opens it up to seeing more available paths (even while being slightly less efficient).

 

I managed to add and connect 111 nodes in 34ms, so efficiency really isn't an issue here.

 

Ultimately, it works, and that's all that really matters, right? 

A* implemented with an accurate heuristic (eg. A heuristic that is incapable of overestimations, which is easy in this case) is incapable of returning a path that is not the shortest possible.

 

Also, 111 nodes in 34ms is relatively slow

looking at your implementation, I can see that this really isnt a real Dijkstra algorithm, It wont search in the pattern illustrated by your gif. It works, but it will search very inefficiently. Dijkstra is implemented using a PriorityQueue or something of the like, with the ability to sort its content by comparing their potential (Accumulated distance from starting point). Using a deque simply does not accomplish this. It polls random nodes rather than the ones with the shortest distance, which may ultimately return suboptimal paths

 

Overall its a decent piece of code, but has room for some improvements

Edited January 22, 2014 by FrostBug

[Solution]

I thought osbot had webwalking? or are they adding it way in osb 2.0

[Pandemic]

A* implemented with an accurate heuristic (eg. A heuristic that is incapable of overestimations, which is easy in this case) is incapable of returning a path that is not the shortest possible.

 

Also, 111 nodes in 34ms is relatively slow

looking at your implementation, I can see that this really isnt a real Dijkstra algorithm, It wont search in the pattern illustrated by your gif. It works, but it will search very inefficiently. Dijkstra is implemented using a PriorityQueue or something of the like, with the ability to sort its content by comparing their potential. Using a deque simply does not accomplish this. It polls random nodes rather than the ones with the shortest distance, which may ultimately return suboptimal paths

 

Overall its a decent piece of code, but has room for some improvements

 

Yeah it's a WIP, haha, I'll definitely improve it based on what you suggest

 

EDIT: How's that?

Edited January 22, 2014 by Pandemic

[FrostBug]

Yeah it's a WIP, haha, I'll definitely improve it based on what you suggest

Sounds good :E, since OSBot kinda does need this

 

Id recommend using java's PriorityQueue, it will automatically sort whatever you push into it by comparing. Which means that if you have your WalkingNode implement the Comparable interface, and have it compare their accumulated distances from the starting point, when popping a node from the queue, it will always be the node with the least distance from the starting point.

 

Add a heuristic ontop of that (accumulated distance from start node + estimated distance to goal), and you're golden. Doing so it will always pop the node with the best potential for reaching the goal in the best possible way

 

[Pandemic]

Sounds good :E, since OSBot kinda does need this

 

Id recommend using java's PriorityQueue, it will automatically sort whatever you push into it by comparing. Which means that if you have your WalkingNode implement the Comparable interface, and have it compare their accumulated distances from the starting point, when popping a node from the queue, it will always be the node with the least distance from the starting point.

 

Add a heuristic ontop of that (accumulated distance from start node + estimated distance to goal), and you're golden. Doing so it will always pop the node with the best potential for reaching the goal in the best possible way

 

 

Haha, beat you to it

 

 

Well, there isn't a heuristic yet, but I might add that soon ;)

Edited January 22, 2014 by Pandemic

[Jack]

ty

 

[FrostBug]

Haha, beat you to it

 

 

Well, there isn't a heuristic yet, but I might add that soon

 

:L nice

 

This is a neat tool to play around with. it really shows the difference in efficiency

http://qiao.github.io/PathFinding.js/visual/

 

What you had initially somewhat resembled a Depth First Search (DFS). Those are usually good for tree spanning. Unfortunatly that tool can't demonstrate DFS

 

good luck with it

[Pandemic]

:L nice

 

This is a neat tool to play around with. it really shows the difference in efficiency

http://qiao.github.io/PathFinding.js/visual/

 

What you had initially somewhat resembled a Depth First Search (DFS). Those are usually good for tree spanning. Unfortunatly that tool can't demonstrate DFS

 

good luck with it

 

That's super cool to play with, I know what I'll be doing for the next 30 minutes or so