Vorkath Poison Phase DFS solution

[yfoo]

I'm thinking of writing a Vorkath script, IMO the hardest part to code is the poison pool phase. My solution is to use a modified version of DFS that searches for a line at least 5 consecutive tiles and if needed a path to reach the start of the consecutive tiles. Initially I want to make a plugin to test that the code works. My question is what solution would you use to find a safe path for the poison phase or what errors or edges cases did I not account for in my algorithm.

The poison phase can be represented as a graph problem where each tile is a node and has edges to its surrounding tiles. However in my case I only have edges to surrounding edges in cardinal directions to simplify code logic.

My proposed solution needs the following variables/functions to work...

• lastDirection: what direction are the consecutive tiles going in
• consecutiveTiles: how many tiles in the same direction expanded
• startConsecutiveTile: where to start counting consecutive tiles from
• endConsecutiveTile: " " stop " ", start and stop needed to later to generate a path to the solution
• directionChanges: num times directions have changed 90 degrees, stop expanding nodes in the current DFS path when this is over some value, lets limit to 2 direction changes. This is similar to how depth limited DFS limits search to some depth. The less 90 degree direction changes the better because osrs shows the tile that you were on 1 tick before (I think) and in order to properly do a 90 degree turn at some specific tile you need to click about 1 tile before the turn. There some fuzziness due to lag.
• dfsStack: stack holding Dragon Fire Shield charges
• visitedSet: a set containing visited tiles to prevent tile re-expansion
• predessorPaths: a dict keeping track of pre-req paths to get to the final path. Key: a path, Value: last path needed to get to the path in the key. This is similar to how a dict is used to hold predecessor nodes in regular DFS to get the path to the solution.
• finalPath: the path that is used to walk back and forth during the poison phase while vork rapid fires fireballs
• initialTile: passed parameter for this function, the starting tile to find a solution from
• tile.getSuccessors(lastDirection): returns an array where the tile in the lastDirection is last element in the array, this is because these tiles get placed in the dfsStack and we want to expand tiles in the same direction. This makes it such that the tile that expands in the same direction is at the top of the stack. getSuccessors does not return tiles that are inaccessible or have poison. If currDirection is null, return directions in counter clockwise order starting with the west tile.
• getDirection(currentTile, lastTile): returns the direction (N, W, S, E) from the lastTile to the currentTile.
• expandInOtherDirection(currentTile, lastDirection: it is possible that there are tiles on the same x or y axis starting from startConsecutiveTile in the opposite direction of lastDirection that are unexpanded that can create a straight path of 5+ tiles. This function would return a tile before a poison pool or inaccessible tile in the opposite direction.

PsuedoCode:

vorkDFS(initialTile){
	# bookkeeping variables
	consecutiveTiles = 0
	directionChanges = 0
	lastDirection = None
	startConsecutiveTile = initialTile
	endConsecutiveTile = None
	lastTile = initialTile
	lastPreReqPath = None
	finalPath = None
	
	# DFS data structures
	dfsStack = [initialTile]
	visitedSet = Set(initialTile)
	predessorPaths = Dict()
	
	while(dfsStack not empty):
		currentTile = dfsStack.pop()
		successors = currentTile.getSuccessors(lastDirection)
		# the first run the initialTile is expanded, a direction cannot be determined until
		# the next tile gets expanded. Basically for the first loop, do not run this part.
		if currentTile != initialTile:
			direction = getDirection(lastTile, currentTile)
			if lastDirection == direction: 
				# still continuing on in the same direction
				consecutiveTiles++
				lastDirection = direction
				if consecutiveTiles >= 4:
					# soln found of at least 5 tiles! The start tile (1) + (4) additional tiles for 5. 
					finalPath = (startConsecutiveTile, endConsecutiveTile)
					break
			else:
  				# it is possible that there are tiles on the same x or y axis starting from startConsecutiveTile that are unexpanded that can create a 					# straight path of 5+ tiles 
				extendedStartTile = expandInOtherDirection(currentTile, lastDirection)
				endConsecutiveTile = currentTile
				if startConsecutiveTile != extendedStartTile:
					#if the extendedStartTile is different then there are additional tiles that may form a staight line path of 5+ tiles
					if abs(startConsecutiveTile[0] - extendedStartTile[0]) + endConsecutiveTile[0] >= 5 
						or  abs(startConsecutiveTile[1] - extendedStartTile[1]) + endConsecutiveTile[1] >= 5:
						finalPath = (extendedStartTile, endConsecutiveTile)
						break
  
				# making a direction change
				consecutiveTiles = 0
				directionChanges++
				if directionChanges > 2:
					# exceed direction change threshold, terminate
					break
					
				# remember the start and end tiles of this line so once a solution is found the prerequsite paths to get the soln can be retrieved
				# paths are straight lines of consecutive tiles
				endConsecutiveTile = currentTile
				if lastPreReqPath:
					# there is some pre-req path to get to this path. i.e: a direction changed happened.
					predessorPaths[(startConsecutiveTile, endConsecutiveTile), lastPreReqPath]
				else:
					# if this path starts off the initial tile there is no lastPreReqPath, set it. Since the value in the dict is None, that means some 					# path is the start.
					predessorPaths[(startConsecutiveTile, endConsecutiveTile), None]
				
				# a new path started, reset these variables
				startConsecutiveTile = currentTile
				endConsecutiveTile = None
		
		for tile in successors:
			if tile not in visitedSet:
				dfsStack.push(tile)
				visitedSet.add(tile)
	
	if finalPath != None:
          # use predessorPaths to get the solution
          soln = [finalPath]
          backTrackingKey = finalPath
          while(predessorPaths[backTrackingKey] != None):
              # if the value is none, this path starts off the inital tile. 
              soln.append(predessorPaths[backTrackingKey])	
              backTrackingKey = predessorPaths[backTrackingKey]
          return soln
		
  	return None 
  	# no solution found ~ there might be a code error or there is just no soln without having to step over a poison pool. 
	# if there is no solution, prehaps rerun the vorkDFS but allow the stepping over 1 poison pool, repeat this until a soln is found or a threshold is 	# determined. 
}

If I were to run this algorithm on a simulated graph, this is what I think will happen.

Blue tiles = Vorkath, Green = poison pools, Red= Start Position, Yellow = Expanded tiles, White = Nodes in Frontier (DFSstack)

https://imgur.com/5asbIHj

From here b/c the player (red) is surrounded by poison pools except to the east, east is expanded. The east tile continues to be the one to be expanded because I purposelessly put the tile in the same direction at the top of the DFS stack. This will happen until hitting the poison tile directly to the east.

At this point the startConsecutiveTile is labled start, same for end.

https://imgur.com/L2L8uId

Because continuing east is no longer an option, the algorithm will expand north until it is right adjacent to Vorkath, this also sets lastDirection to North. This is a direction change so the algorithm scans west from the start tile to see if there are additional safe tiles in the opposite (west) direction. In this case there are none. Instead directionChanges is incremented to 1. Furthermore consecutive start and end tiles are cached in predessorPaths.

https://imgur.com/4Wql4MN

After hitting vorkath who occupies inaccessable tiles, a direction change is noted again, but this time the expandInOtherDirection finds that there are more tiles opposite (south) direction of lastDirection (north) that form a straight line path of 5+ tiles. A finalPath is noted and the while loop breaks.

https://imgur.com/AWOMO1Q

Finally predessorPaths is queried with finalPath as the key, this will continuously append pre-req paths into the soln list until we end up back at the initial tile. This soln is returned.

How would you code this?

 

[Rays]

Wouldn't a consistent Wooxwalk require lot less logic?

Might be harder to get done beutifully.

[yfoo]

32 minutes ago, Rays said:

Wouldn't a consistent Wooxwalk require lot less logic?

Might be harder to get done beutifully.

I can't even do that as a human.

[packthebowlll]

I'm interested in the script if or when you get it done, gonna make it public or private? 

[Dave]

I'm open to testing if you need someone. I personally think this would be a great release!

[Rays]

1 hour ago, PayPalMeRSGP said:

I can't even do that as a human.

It's honestly insanely simple method but is hard to pull off because it requires good timing. Timing which can be achieved easily in a script I reckon.

Edited August 14, 2018 by Rays

[liverare]

If all you have to do is to move to 5 sequential tiles that

1. Is not a poison pool
2. Is not the 'previous' tile

Then a simple loop would do:

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

import org.osbot.rs07.api.map.Position;
import org.osbot.rs07.api.model.RS2Object;
import org.osbot.rs07.script.API;

public class VorkathPoisonPhase extends API {

	Position startTile;
	List<Position> badTiles;

	@Override
	public void initializeModule() {
		startTile = myPosition();
		badTiles = objects.getAll().stream()
				.filter(VorkathPoisonPhase::isPoisonPool)
				.map(RS2Object::getPosition)
				.collect(Collectors.toList());
	}
	
	public Position getNextTile() {
		return getAdjacentTiles(myPosition()).stream()
				.filter(this::isGoodTile)
				.sorted(this::sortByClosestToStartTile)
				.findFirst()
				.orElse(null);
	}
	
	private List<Position> getAdjacentTiles(Position p) {
		List<Position> tiles = new LinkedList<Position>();
		tiles.add(p.translate(0, -1)); // north
		tiles.add(p.translate(1, 0));  // east
		tiles.add(p.translate(0, 1));  // south
		tiles.add(p.translate(-1, 0)); // west
		return tiles;
	}
	
	private boolean isGoodTile(Position p) {
		return !badTiles.contains(p);
	}
	
	private int sortByClosestToStartTile(Position p1, Position p2) {
		return Integer.compare(startTile.distance(p1), startTile.distance(p2));
	}

	private static boolean isPoisonPool(RS2Object obj) {
		return false; // TODO
	}
	
}

Note: isPoisionPool is incomplete. I don't know if the poison is an object/npc/projectile/etc.

1. Get start tile and all poison tiles
2. Create a function to get a list of all adjacent tiles to start tile
3. Get next tile (filter out tiles that have poison and sort by distance (closest) to start tile)
4. Then...

public class Test extends Script {

	VorkathPoisonPhase vorkathPoisonPhase;

	@Override
	public void onStart() throws InterruptedException {
		vorkathPoisonPhase = new VorkathPoisonPhase();
		vorkathPoisonPhase.exchangeContext(bot);
	}
	
	@Override
	public int onLoop() throws InterruptedException {
		
		// When poision phase...
		
		vorkathPoisonPhase.initializeModule();
		for (int i = 0; i < 5; i++) {
			walking.walk(vorkathPoisonPhase.getNextTile());
		}
		

		return 500;
	}
	
	
}

It's incomplete and untested, but the idea is to simply find the next suitable tile to walk to, preferably located nearby the start time.

[yfoo]

9 hours ago, liverare said:

If all you have to do is to move to 5 sequential tiles that

1. Is not a poison pool
2. Is not the 'previous' tile

Then a simple loop would do:

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

import org.osbot.rs07.api.map.Position;
import org.osbot.rs07.api.model.RS2Object;
import org.osbot.rs07.script.API;

public class VorkathPoisonPhase extends API {

	Position startTile;
	List<Position> badTiles;

	@Override
	public void initializeModule() {
		startTile = myPosition();
		badTiles = objects.getAll().stream()
				.filter(VorkathPoisonPhase::isPoisonPool)
				.map(RS2Object::getPosition)
				.collect(Collectors.toList());
	}
	
	public Position getNextTile() {
		return getAdjacentTiles(myPosition()).stream()
				.filter(this::isGoodTile)
				.sorted(this::sortByClosestToStartTile)
				.findFirst()
				.orElse(null);
	}
	
	private List<Position> getAdjacentTiles(Position p) {
		List<Position> tiles = new LinkedList<Position>();
		tiles.add(p.translate(0, -1)); // north
		tiles.add(p.translate(1, 0));  // east
		tiles.add(p.translate(0, 1));  // south
		tiles.add(p.translate(-1, 0)); // west
		return tiles;
	}
	
	private boolean isGoodTile(Position p) {
		return !badTiles.contains(p);
	}
	
	private int sortByClosestToStartTile(Position p1, Position p2) {
		return Integer.compare(startTile.distance(p1), startTile.distance(p2));
	}

	private static boolean isPoisonPool(RS2Object obj) {
		return false; // TODO
	}
	
}

Note: isPoisionPool is incomplete. I don't know if the poison is an object/npc/projectile/etc.

1. Get start tile and all poison tiles
2. Create a function to get a list of all adjacent tiles to start tile
3. Get next tile (filter out tiles that have poison and sort by distance (closest) to start tile)
4. Then...

public class Test extends Script {

	VorkathPoisonPhase vorkathPoisonPhase;

	@Override
	public void onStart() throws InterruptedException {
		vorkathPoisonPhase = new VorkathPoisonPhase();
		vorkathPoisonPhase.exchangeContext(bot);
	}
	
	@Override
	public int onLoop() throws InterruptedException {
		
		// When poision phase...
		
		vorkathPoisonPhase.initializeModule();
		for (int i = 0; i < 5; i++) {
			walking.walk(vorkathPoisonPhase.getNextTile());
		}
		

		return 500;
	}
	
	
}

It's incomplete and untested, but the idea is to simply find the next suitable tile to walk to, preferably located nearby the start time.

I get your solution but the 5+ tiles have to be in a straight line to give me enough buffer room to turn around. The reasoning being your to dodge fireballs your character has to be on a different tile every game tick or you take 20+ damage, this is registered server side. Lets say I were to make a 90 degree turn, if I were to click on a tile to turn after seeing my character arrive at the turning point, I will take damage; the server registers I am 1+ tiles ahead than what is shown on my client screen. In the server's calculations it sees that I arrived at my destination tile, then sends data to my game client, my game client then shows I am at the destination tile. By the time I send data to the server indicating a direction change I have stopped moving (the server sees that I have been at the same tile for 2+ ticks) and would have taken damage.

In a straight line, I am constantly moving therefore preventing damage. Just before the end of my path (ex: lets say 2 tiles b4, thats why I need enough buffer room) I change direction 180 degrees (click opposite tile of path) but still am constantly shifting my position 1 tile every game tick. As long as I input another move command before I arrive at my destination tile I am always moving both server and client side. Taking 90 degree turns is therefore risky as I need to input the move command when I think the server has registered I am at the turning tile which is before my game client shows my character at the actual turning tile. If I guess too early I may prematurely turn, too late I take damage.

Your solution may actually work because you click to move before every 600ms game tick (assuming each walk is synced to game ticks) but honestly when I do vork manually I don't dare try moving 1 tile at a time.

Thanks for writing the code though, I need be better familiarize myself with java 8 streams.

Edited August 15, 2018 by PayPalMeRSGP

[irmagical189]

I am not sure if this will help you or not but this is what I do. I currently range vorkath from the row of tiles I am currently standing on now.  Using this method, all I have to do is step back as soon as I see the acid pool attack. The yellow line will ALWAYS be free of acid pools if you do it this way. The green x on each side represents where an acid pool will land or at least the closest it will land. Sometimes they are a ways away but this is the closest they will be. Once I step back onto the yellow line of tiles, I just spam click each side. It takes 2-3 seconds to walk, which I typically have a tick to eat a shark then spam click the other side and never take damage. If you use this method, you should have a far easier time writing code as after the initial step back into the safe zone of tiles and clicking a side, a timer could work. I always return to the line of tiles I am currently standing on in this picture.

A couple things:

1. When  he sends the white fire ball your way to freeze you before the undead crab, have the script click somewhere off vorkath. I usually just click on the tile I am standing. I found that if you don't stop attacking vorkath, you might try to hit him again while the crab is running to you and you will not have the time to kill the crab before it will explode and hit you on death. If you click on your tile once the attack freezes  you and then get your crumble undead ready, you will have 100% success rate unless you screw up clicking on the crab. 

2. When he lobs the fire bomb, always move in one direction. I have found that if he uses that attack 2 to 3 times in a row, if you move backwards it will actually land on the tile you are moving to and NOT on the tile you were standing on when he used the attack. 

I can't remember the last time I died at vorkath while killing him like this. Currently my fastest run is 1min 20s and I got vorki on KC 108 lol. 

[packthebowlll]

4 hours ago, irmagical189 said:

I am not sure if this will help you or not but this is what I do. I currently range vorkath from the row of tiles I am currently standing on now.  Using this method, all I have to do is step back as soon as I see the acid pool attack. The yellow line will ALWAYS be free of acid pools if you do it this way. The green x on each side represents where an acid pool will land or at least the closest it will land. Sometimes they are a ways away but this is the closest they will be. Once I step back onto the yellow line of tiles, I just spam click each side. It takes 2-3 seconds to walk, which I typically have a tick to eat a shark then spam click the other side and never take damage. If you use this method, you should have a far easier time writing code as after the initial step back into the safe zone of tiles and clicking a side, a timer could work. I always return to the line of tiles I am currently standing on in this picture.

A couple things:

1. When  he sends the white fire ball your way to freeze you before the undead crab, have the script click somewhere off vorkath. I usually just click on the tile I am standing. I found that if you don't stop attacking vorkath, you might try to hit him again while the crab is running to you and you will not have the time to kill the crab before it will explode and hit you on death. If you click on your tile once the attack freezes  you and then get your crumble undead ready, you will have 100% success rate unless you screw up clicking on the crab. 

2. When he lobs the fire bomb, always move in one direction. I have found that if he uses that attack 2 to 3 times in a row, if you move backwards it will actually land on the tile you are moving to and NOT on the tile you were standing on when he used the attack. 

I can't remember the last time I died at vorkath while killing him like this. Currently my fastest run is 1min 20s and I got vorki on KC 108 lol. 

nice I never knew about that path never getting acid if you did it that way, will give it a try later.

 

Are you using blowpipe or crossbow? I tried with bp and I'd have to use long range to stand there. 

Edited August 15, 2018 by packthebowlll

[yfoo]

4 hours ago, irmagical189 said:

I am not sure if this will help you or not but this is what I do. I currently range vorkath from the row of tiles I am currently standing on now.  Using this method, all I have to do is step back as soon as I see the acid pool attack. The yellow line will ALWAYS be free of acid pools if you do it this way. The green x on each side represents where an acid pool will land or at least the closest it will land. Sometimes they are a ways away but this is the closest they will be. Once I step back onto the yellow line of tiles, I just spam click each side. It takes 2-3 seconds to walk, which I typically have a tick to eat a shark then spam click the other side and never take damage. If you use this method, you should have a far easier time writing code as after the initial step back into the safe zone of tiles and clicking a side, a timer could work. I always return to the line of tiles I am currently standing on in this picture.

A couple things:

1. When  he sends the white fire ball your way to freeze you before the undead crab, have the script click somewhere off vorkath. I usually just click on the tile I am standing. I found that if you don't stop attacking vorkath, you might try to hit him again while the crab is running to you and you will not have the time to kill the crab before it will explode and hit you on death. If you click on your tile once the attack freezes  you and then get your crumble undead ready, you will have 100% success rate unless you screw up clicking on the crab. 

2. When he lobs the fire bomb, always move in one direction. I have found that if he uses that attack 2 to 3 times in a row, if you move backwards it will actually land on the tile you are moving to and NOT on the tile you were standing on when he used the attack. 

I can't remember the last time I died at vorkath while killing him like this. Currently my fastest run is 1min 20s and I got vorki on KC 108 lol. 

Never knew that the yellow line indicated is always poison free. This actually makes things alot easier if it was the case, ill do some testing later today.

[irmagical189]

3 hours ago, packthebowlll said:

nice I never knew about that path never getting acid if you did it that way, will give it a try later.

 

Are you using blowpipe or crossbow? I tried with bp and I'd have to use long range to stand there. 

I started Vorkath using ACB but switched to DHCB. I have yet to try it with BP. I use rapid and hit him standing on the line of tiles immediately in front of the yellow line. On rapid or accurate I cannot reach him from the yellow line. My method might not be the fastest, but it is very consistent and likely the easiest method to script.

[liverare]

You could create a projectile listener, listen out for the flaming one that you have to constantly move to avoid, grab the destination tile for those projectiles and then fire off an event handler that speedily moves your character using a custom mouse API (so you can click tiles much more quickly).

[yfoo]

3 hours ago, liverare said:

You could create a projectile listener, listen out for the flaming one that you have to constantly move to avoid, grab the destination tile for those projectiles and then fire off an event handler that speedily moves your character using a custom mouse API (so you can click tiles much more quickly).

I was thinking of something like this. Set up an VorkathObserver interface for relevant classes. The code that calls onVorkEvent runs on a seperate thread and inserts events into a priority queue. 

interface VorkathObservor {
	onVorkathEvent(VorkathEvent e);
}

VorkathEvent (maybe an extension of Event) instances have a predefined weight, the instakill fireball and poison phase will have the highest weight. This is so that a priority queue can be assembled with vorkath events, onLoop() will pop the PQ, and execute the event. The events that need an immediate response (fireball, poison, ice breath) will be at the top of the PQ and executed ASAP. 

Since there are 2 threads operating on the PQ, I don't know if synchronization is needed. Specifically what happens if the listener thread attempts to insert while the onLoop thread attempts to poll?

Edited August 15, 2018 by PayPalMeRSGP