Jump to content

Simple path finding


meanzie
 Share

Recommended Posts

Hello there, so ehh, I started working on my first bot script today, 

And I couldn't really find any good pathfinding utilities to use, so I threw up one on my own.

	/**
	 * Tries to find the best node in the path to walk on
	 * 
	 * @param path
	 * 
	 * @return
	 */
	public Position getBestNode(Position[] path) {
		int radius = 15;
		List<Integer> candidates = new LinkedList<>();
		for (int i = 0; i < path.length; i++) {
			if (path[i].distance(myPosition()) < radius) {
				candidates.add(i);
			}
		}
		if (candidates.size() == 0) {
			warn("Tried to find best node for path, but no candidates were found.");
			return null;
		}
		int bestCandidate = 0;
		for (int i : candidates) {
			if (path[i].distance(path[path.length - 1]) < path[bestCandidate]
					.distance(path[path.length - 1])) {
				bestCandidate = i;
			}
		}
		// Check if this is the last point in the path
		if (bestCandidate + 1 >= path.length) {
			return path[bestCandidate];
		}

		// We should try and interpolate between this point and the next point
		// so that distance is always radius
		Position pointA = path[bestCandidate];
		Position pointB = path[bestCandidate + 1];

		// So let's take p2 - p1 and get the direction vector
		int dirX = pointB.getX() - pointA.getX();
		int dirY = pointB.getY() - pointA.getY();

		// Now find a's distance to the target
		double distA = pointA.distance(myPosition());

		// Let's normalize our direction vector
		double dirVecL = Math.sqrt(dirX * dirX + dirY * dirY);
		double dirVecX = dirX / dirVecL;
		double dirVecY = dirY / dirVecL;

		// Now let's create our destination vector
		Position pointD = new Position(
				(int) (dirVecX * (radius - distA) + pointA.getX()),
				(int) (dirVecY * (radius - distA) + pointA.getY()), 0);

		return pointD;
	}

This function assumes that you are giving it a forward path, meaning that path[0] is the start point and path[n] is the end point.

The script will find the node that is closest to the player and closest to the target.

 

Of course there is room for improvements, and I am sure there are scenarios where this method wouldn't work.

Also, each path node has to be < 15 tiles away from each other, or else it won't find them.

Link to comment
Share on other sites

This isn't really pathfinding, more just finding the next tile to walk on given a manually entered path. Pathfinding would be entering, tile A and tile B, and walking all the way from A to B, without knowing what's in between ahead of time.

Agreed. I got excited when I saw this title but I'm still on the lookout for a path finder I guess :(

Link to comment
Share on other sites

 

This isn't really pathfinding, more just finding the next tile to walk on given a manually entered path. Pathfinding would be entering, tile A and tile B, and walking all the way from A to B, without knowing what's in between ahead of time.

Agreed. I got excited when I saw this title but I'm still on the lookout for a path finder I guess sad.png

 

 

i have this but not that good http://osbot.org/forum/topic/20077-generating-straight-line-path/

 

will work on a path finder on thursday

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...