SRL Archive - Research & Development Lounge

Here's an example of how 'all' bots, using NPC/Object tracking, will find the nearest object.

The Red line represents the path taken to get to the nearest object.


Notice that even though it takes longer to get to the nearest object, the bot will still do so, ignoring the closest object to get to in the time factor. So why is this? Has this issue ever been brought up before, or has anyone tried to find a more realistic alternative?

Well, I gave it a shot, and at my current progress I've just gotten to debugging how many objects (intractable) are within the path from you to your destination. If we could use this, or a much further modified version of this, to estimate the closest objects to us in time rather than distance, we could have the advantage above all in speed and as well as human-characteristics.

Ok, here's my little debugger tool, just define the destination's tile and it'll tell you how many objects lay in your path. BIG thanks to TRiLeZ, the bulk of the code is from him.

{*******************************************************************************
Procedure getObjCount
By: Flight
Description: Returns the # of obj's between you and your target
*******************************************************************************}
  Procedure getObjCount(DestTile: TTile);
  Var
    myTile,ObjTile: TTile;
    xDist,yDist,tDist,xStep,
    yStep,xN,yN,i,Count: integer;
    myObj: TRSObject;
  begin
		myTile := GetMyPos;
    tDist := Distance(myTile.x, myTile.y, DestTile.x, DestTile.y);
    if (tDist <= 1) then
      Exit;

    if (DestTile.x > myTile.x) then
      xDist := (DestTile.x - myTile.x);
    if (DestTile.x < myTile.x) then
      xDist := (myTile.x - DestTile.x);
    if (DestTile.y > myTile.y) then
      yDist := (DestTile.y - myTile.y);
    if (DestTile.y < myTile.y) then
      yDist := (myTile.y - DestTile.y);

		xStep := (xDist / tDist);
		yStep := (yDist / tDist);

    for i := 1 to tDist do
    begin

      if (DestTile.x > myTile.x) then
        xN := myTile.x + (xStep * i);
      if (DestTile.x < myTile.x) then
        xN := myTile.x - (xStep * i);
      if (DestTile.x = myTile.x) then
        xN := myTile.x;
      if (DestTile.y > myTile.y) then
        yN := myTile.y + (yStep * i);
      if (DestTile.y < myTile.y) then
        yN := myTile.y - (yStep * i);
      if (DestTile.y = myTile.y) then
        yN := myTile.y;

      ObjTile := PointToTile(Point(xN,yN));

      MyObj := GetObjectAt(ObjTile, OBJECT_TYPE_INTERACTABLE);

      if MyObj.ID > 0 then
        Inc(Count);
        //writeln ('ID: '+inttostr(MyObj.ID)+', Tile('+inttostr(MyObj.Tile.x)+','+inttostr(MyObj.Tile.y)+')');
    end;

    Count := Count-1;  //Because it counts your target tile

    if (Count < 0) then
      Count := 0;

    writeln(''+IntToStr(Count)+' objects in path.');
  end;

So my idea is this: For example I'll use "GetObjectByIDEx" Find the nearest and second nearest object tiles, use my bit of code to detect which of the two tiles has the most objects laying in the path, compare the distance - to - objectcount to determine which object is the real nearest.

Of course this is very much just a rough draft and is no where near official, but anyways you get the idea of how this could be possible. This part: "MyObj := GetObjectAt(ObjTile, OBJECT_TYPE_INTERACTABLE);" could be changed to wall objects or even floor objects such as water. If you've ever seen the bots in the fishing guild fishing on Dock A, when their spot moves just 5 tiles away on the same dock, they'll instead run all the way to the other dock just because it's closer to their current X/Y.

So post your thoughts on how this might be done. Don't hand me bits of code because I think beyond this point it's out of my league. :( But you could imagine the advantage this would give us…

Really interesting. I hope this gets taken on board.

I noticed this when I did my farming bot… I had to sort tiles first, Find the objects only at a certain location or within a box.. thats what I modified the MeInBox to do..

But the fishing one is totally different.. it moves and I couldnt figure it out either.

I was thinking if u make something that radiates outward until it finds the object but if it hits a non-interactive object, then it knows not to go that way.. kinda like radial walk.

It seems more intuitive to me to grab all of the nearby objects that you're looking for and sort them based on the walking distance from your player. Of course, that would require some pathfinding algorithm (probably Dijkstra or A*) and access to the client's collision map, but you would end up with the "actual" closest object.

Anyone thinking SmartPaths?
Path walking that learns? :P

From: Dynamite
Anyone thinking SmartPaths?
Path walking that learns? :P

No reason at all.. The RS map is (mostly) static.

From: i luffs yeww
No reason at all.. The RS map is (mostly) static.

agreed+


This would be pretty easy to do. And i think it would be well worth it! (:

From: i luffs yeww
No reason at all.. The RS map is (mostly) static.

As in…
Take each path from x to each object and time? Or something similar.
Would need to do this once from each position then loop through from least time away through to longest away.

Here's an algorithm provided by Jacmob in rsbot/scripts/MapExplorer.java

/**
	 * A* impl using local rs collision map.
	 *
	 * @author Jacmob
	 */
	static class AStar {

		private static class Node {

			public int x, y;
			public Node prev;
			public double g, f;

			public Node(int x, int y) {
				this.x = x;
				this.y = y;
				g = f = 0;
			}

			@Override
			public int hashCode() {
				return (x << 4) | y;
			}

			@Override
			public boolean equals(Object o) {
				if (o instanceof Node) {
					Node n = (Node) o;
					return x == n.x && y == n.y;
				}
				return false;
			}

			@Override
			public String toString() {
				return "(" + x + "," + y + ")";
			}

			public RSTile toRSTile(int baseX, int baseY) {
				return new RSTile(x + baseX, y + baseY);
			}

		}

		private Walking walking;
		private Game game;

		private int[][] flags;
		private int off_x, off_y;

		public void init(Game game, Walking walking) {
			this.game = game;
			this.walking = walking;
		}

		public RSTile[] findPath(RSTile start, RSTile end) {
			int base_x = game.getBaseX(), base_y = game.getBaseY();
			int curr_x = start.getX() - base_x, curr_y = start.getY() - base_y;
			int dest_x = end.getX() - base_x, dest_y = end.getY() - base_y;

			// load client data
			flags = walking.getCollisionFlags(game.getPlane());
			RSTile offset = walking.getCollisionOffset(game.getPlane());
			off_x = offset.getX();
			off_y = offset.getY();

			// loaded region only
			if (flags == null || curr_x < 0 || curr_y < 0 ||
					curr_x >= flags.length || curr_y >= flags.length ||
					dest_x < 0 || dest_y < 0 ||
					dest_x >= flags.length || dest_y >= flags.length) {
				return null;
			}

			// structs
			HashSet<Node> open = new HashSet<Node>();
			HashSet<Node> closed = new HashSet<Node>();
			Node curr = new Node(curr_x, curr_y);
			Node dest = new Node(dest_x, dest_y);

			curr.f = heuristic(curr, dest);
			open.add(curr);

			// search
			while (!open.isEmpty()) {
				curr = lowest_f(open);
				if (curr.equals(dest)) {
					// reconstruct from pred tree
					return path(curr, base_x, base_y);
				}
				open.remove(curr);
				closed.add(curr);
				for (Node next : successors(curr)) {
					if (!closed.contains(next)) {
						double t = curr.g + dist(curr, next);
						boolean use_t = false;
						if (!open.contains(next)) {
							open.add(next);
							use_t = true;
						} else if (t < next.g) {
							use_t = true;
						}
						if (use_t) {
							next.prev = curr;
							next.g = t;
							next.f = t + heuristic(next, dest);
						}
					}
				}
			}

			// no path
			return null;
		}

		private double heuristic(Node start, Node end) {
			double dx = start.x - end.x;
			double dy = start.y - end.y;
			if (dx < 0) dx = -dx;
			if (dy < 0) dy = -dy;
			return dx < dy ? dy : dx;
			//double diagonal = dx > dy ? dy : dx;
			//double manhattan = dx + dy;
			//return 1.41421356 * diagonal + (manhattan - 2 * diagonal);
		}

		private double dist(Node start, Node end) {
			if (start.x != end.x && start.y != end.y) {
				return 1.41421356;
			} else {
				return 1.0;
			}
		}

		private Node lowest_f(Set<Node> open) {
			Node best = null;
			for (Node t : open) {
				if (best == null || t.f < best.f) {
					best = t;
				}
			}
			return best;
		}

		private RSTile[] path(Node end, int base_x, int base_y) {
			LinkedList<RSTile> path = new LinkedList<RSTile>();
			Node p = end;
			while (p != null) {
				path.addFirst(p.toRSTile(base_x, base_y));
				p = p.prev;
			}
			return path.toArray(new RSTile[path.size()]);
		}

		private java.util.List<Node> successors(Node t) {
			LinkedList<Node> tiles = new LinkedList<Node>();
			int x = t.x, y = t.y;
			int f_x = x - off_x, f_y = y - off_y;
			int here = flags[f_x][f_y];
			if (f_y > 0 && (here & WALL_SOUTH) == 0 && (flags[f_x][f_y - 1] & BLOCKED) == 0) {
				tiles.add(new Node(x, y - 1));
			}
			if (f_x > 0 && (here & WALL_WEST) == 0 && (flags[f_x - 1][f_y] & BLOCKED) == 0) {
				tiles.add(new Node(x - 1, y));
			}
			if (f_y < 103 && (here & WALL_NORTH) == 0 && (flags[f_x][f_y + 1] & BLOCKED) == 0) {
				tiles.add(new Node(x, y + 1));
			}
			if (f_x < 103 && (here & WALL_EAST) == 0 && (flags[f_x + 1][f_y] & BLOCKED) == 0) {
				tiles.add(new Node(x + 1, y));
			}
			if (f_x > 0 && f_y > 0 && (here & (WALL_SOUTH_WEST | WALL_SOUTH | WALL_WEST)) == 0
					&& (flags[f_x - 1][f_y - 1] & BLOCKED) == 0
					&& (flags[f_x][f_y - 1] & (BLOCKED | WALL_WEST)) == 0
					&& (flags[f_x - 1][f_y] & (BLOCKED | WALL_SOUTH)) == 0) {
				tiles.add(new Node(x - 1, y - 1));
			}
			if (f_x > 0 && f_y < 103 && (here & (WALL_NORTH_WEST | WALL_NORTH | WALL_WEST)) == 0
					&& (flags[f_x - 1][f_y + 1] & BLOCKED) == 0
					&& (flags[f_x][f_y + 1] & (BLOCKED | WALL_WEST)) == 0
					&& (flags[f_x - 1][f_y] & (BLOCKED | WALL_NORTH)) == 0) {
				tiles.add(new Node(x - 1, y + 1));
			}
			if (f_x < 103 && f_y > 0 && (here & (WALL_SOUTH_EAST | WALL_SOUTH | WALL_EAST)) == 0
					&& (flags[f_x + 1][f_y - 1] & BLOCKED) == 0
					&& (flags[f_x][f_y - 1] & (BLOCKED | WALL_EAST)) == 0
					&& (flags[f_x + 1][f_y] & (BLOCKED | WALL_SOUTH)) == 0) {
				tiles.add(new Node(x + 1, y - 1));
			}
			if (f_x > 0 && f_y < 103 && (here & (WALL_NORTH_EAST | WALL_NORTH | WALL_EAST)) == 0
					&& (flags[f_x + 1][f_y + 1] & BLOCKED) == 0
					&& (flags[f_x][f_y + 1] & (BLOCKED | WALL_EAST)) == 0
					&& (flags[f_x + 1][f_y] & (BLOCKED | WALL_NORTH)) == 0) {
				tiles.add(new Node(x + 1, y + 1));
			}
			return tiles;
		}

	}

MapExplorer.java finds the path taking into consideration collisions as you described in the first post.

uploaded here: http://paste.villavu.com/show/537/

From: i luffs yeww
No reason at all.. The RS map is (mostly) static.

Being static or not isn't the issue. The issue is whether you would want to spend your time developing custom walking algorithms for every spot on the static map, or develop one learning algorithm that will work for every spot on the static map.

It's just like SmartColors. I could go through and figure out every possible color value of red that a chicken head can be and put it into a static array, or I can let SmartColors figure it out on its own each time the script runs.

I favor the latter approach, but maybe I'm just lazy.

From: tarajunky
Being static or not isn't the issue. The issue is whether you would want to spend your time developing custom walking algorithms for every spot on the static map, or develop one learning algorithm that will work for every spot on the static map.

It's just like SmartColors. I could go through and figure out every possible color value of red that a chicken head can be and put it into a static array, or I can let SmartColors figure it out on its own each time the script runs.

I favor the latter approach, but maybe I'm just lazy.

I guess I misunderstood it. I don't know if comparing SmartColors to a SmartWalk sort of thing is fair, since colors are (somewhat) dynamic.

I do think there should be a change to how walking.. walks, though. What lordsaturn posted should help.

Why not just.

 Rock := GetObjectsByIDEx(Rock_IDs, OBJECT_TYPE_INTERACTABLE, 15);
  R_FindRandoms;
  for i := 0 to High(Rock) do begin
    if Length(Rock) <= What then Exit;
    if not TileOnMS(Rock[1].RealTile, 0)

~Home

From: Method
[DELETED excess] access to the client's collision map, but you would end up with the "actual" closest object.

So something like (written quickly, ignore typos)

groundDataArray = getFieldObjectArray(0, "gca.v"); //getGroundDataWrap/Array/some good name
groundData = groundDataArray[gettingPlaneShitHere()];
collisionFlags = getFieldObject2dArray(groundData, "nfa.e"); //getCollisionFlags

How about the algorithm I posted, its EXACTLY what you requested!

Lordsaturn that, from the looks of it, is exactly what I was looking. Unfortunately it's pretty far out of my league so there's not a whole lot more I can do. I was just hoping above all to spark some ideas, maybe get someone going on the right path to looking more into this.

From: pyroryan
So something like (written quickly, ignore typos)

groundDataArray = getFieldObjectArray(0, "gca.v"); //getGroundDataWrap/Array/some good name
groundData = groundDataArray[gettingPlaneShitHere()];
collisionFlags = getFieldObject2dArray(groundData, "nfa.e"); //getCollisionFlags

That doesn't look right at all, but I suppose you have the idea. You'd just access the CollisionMap array using whatever plane you're currently on as the index, then get the collision flags for that plane (if smart allows you to do so) or grab particular values when you look at particular tiles.

From: Flight
Lordsaturn that, from the looks of it, is exactly what I was looking. Unfortunately it's pretty far out of my league so there's not a whole lot more I can do. I was just hoping above all to spark some ideas, maybe get someone going on the right path to looking more into this.

I'll make that work with our reflection in a little bit.