How can I fix these pathfinding issues? For enter edgeville and south varrock is little buggy when it comes to pathfinding. I believe it has to do with maps because my pathfinding classes look fine. It feels like there's invisible objects in certain tiles..
ClippedPathFinder Class:
Code:
package com.rs2.util.clip;
import java.util.LinkedList;
import com.rs2.model.Position;
import com.rs2.model.players.Player;
public class ClippedPathFinder {
private static final ClippedPathFinder pathFinder = new ClippedPathFinder();
public static ClippedPathFinder getPathFinder() {
return pathFinder;
}
public ClippedPathFinder() {
}
public void findRoute(Player c, int destX, int destY, boolean moveNear, int xLength, int yLength) {
if (destX == c.getPosition().getLocalX() && destY == c.getPosition().getLocalY() && !moveNear) {
c.getActionSender().sendMessage("ERROR!");
return;
}
destX = destX - 8 * c.getPosition().getRegionX();
destY = destY - 8 * c.getPosition().getRegionY();
int[][] via = new int[104][104];
int[][] cost = new int[104][104];
LinkedList<Integer> tileQueueX = new LinkedList<Integer>();
LinkedList<Integer> tileQueueY = new LinkedList<Integer>();
for (int xx = 0; xx < 104; xx++) {
for (int yy = 0; yy < 104; yy++) {
cost[xx][yy] = 99999999;
}
}
int curX = c.getPosition().getLocalX();
int curY = c.getPosition().getLocalY();
via[curX][curY] = 99;
cost[curX][curY] = 0;
int tail = 0;
tileQueueX.add(curX);
tileQueueY.add(curY);
boolean foundPath = false;
int pathLength = 4000;
while (tail != tileQueueX.size() && tileQueueX.size() < pathLength) {
curX = tileQueueX.get(tail);
curY = tileQueueY.get(tail);
int curAbsX = c.getPosition().getRegionX() * 8 + curX;
int curAbsY = c.getPosition().getRegionY() * 8 + curY;
if (curX == destX && curY == destY) {
foundPath = true;
break;
}
tail = (tail + 1) % pathLength;
int thisCost = cost[curX][curY] + 1;
if (curY > 0 && via[curX][curY - 1] == 0 && (Region.getClipping(curAbsX, curAbsY - 1, c.getPosition().getZ()) & 0x1280102) == 0) {
tileQueueX.add(curX);
tileQueueY.add(curY - 1);
via[curX][curY - 1] = 1;
cost[curX][curY - 1] = thisCost;
}
if (curX > 0 && via[curX - 1][curY] == 0 && (Region.getClipping(curAbsX - 1, curAbsY, c.getPosition().getZ()) & 0x1280108) == 0) {
tileQueueX.add(curX - 1);
tileQueueY.add(curY);
via[curX - 1][curY] = 2;
cost[curX - 1][curY] = thisCost;
}
if (curY < 104 - 1 && via[curX][curY + 1] == 0 && (Region.getClipping(curAbsX, curAbsY + 1, c.getPosition().getZ()) & 0x1280120) == 0) {
tileQueueX.add(curX);
tileQueueY.add(curY + 1);
via[curX][curY + 1] = 4;
cost[curX][curY + 1] = thisCost;
}
if (curX < 104 - 1 && via[curX + 1][curY] == 0 && (Region.getClipping(curAbsX + 1, curAbsY, c.getPosition().getZ()) & 0x1280180) == 0) {
tileQueueX.add(curX + 1);
tileQueueY.add(curY);
via[curX + 1][curY] = 8;
cost[curX + 1][curY] = thisCost;
}
if (curX > 0 && curY > 0 && via[curX - 1][curY - 1] == 0 && (Region.getClipping(curAbsX - 1, curAbsY - 1, c.getPosition().getZ()) & 0x128010e) == 0 && (Region.getClipping(curAbsX - 1, curAbsY, c.getPosition().getZ()) & 0x1280108) == 0 && (Region.getClipping(curAbsX, curAbsY - 1, c.getPosition().getZ()) & 0x1280102) == 0) {
tileQueueX.add(curX - 1);
tileQueueY.add(curY - 1);
via[curX - 1][curY - 1] = 3;
cost[curX - 1][curY - 1] = thisCost;
}
if (curX > 0 && curY < 104 - 1 && via[curX - 1][curY + 1] == 0 && (Region.getClipping(curAbsX - 1, curAbsY + 1, c.getPosition().getZ()) & 0x1280138) == 0 && (Region.getClipping(curAbsX - 1, curAbsY, c.getPosition().getZ()) & 0x1280108) == 0 && (Region.getClipping(curAbsX, curAbsY + 1, c.getPosition().getZ()) & 0x1280120) == 0) {
tileQueueX.add(curX - 1);
tileQueueY.add(curY + 1);
via[curX - 1][curY + 1] = 6;
cost[curX - 1][curY + 1] = thisCost;
}
if (curX < 104 - 1 && curY > 0 && via[curX + 1][curY - 1] == 0 && (Region.getClipping(curAbsX + 1, curAbsY - 1, c.getPosition().getZ()) & 0x1280183) == 0 && (Region.getClipping(curAbsX + 1, curAbsY, c.getPosition().getZ()) & 0x1280180) == 0 && (Region.getClipping(curAbsX, curAbsY - 1, c.getPosition().getZ()) & 0x1280102) == 0) {
tileQueueX.add(curX + 1);
tileQueueY.add(curY - 1);
via[curX + 1][curY - 1] = 9;
cost[curX + 1][curY - 1] = thisCost;
}
if (curX < 104 - 1 && curY < 104 - 1 && via[curX + 1][curY + 1] == 0 && (Region.getClipping(curAbsX + 1, curAbsY + 1, c.getPosition().getZ()) & 0x12801e0) == 0 && (Region.getClipping(curAbsX + 1, curAbsY, c.getPosition().getZ()) & 0x1280180) == 0 && (Region.getClipping(curAbsX, curAbsY + 1, c.getPosition().getZ()) & 0x1280120) == 0) {
tileQueueX.add(curX + 1);
tileQueueY.add(curY + 1);
via[curX + 1][curY + 1] = 12;
cost[curX + 1][curY + 1] = thisCost;
}
}
if (!foundPath) {
if (moveNear) {
int i_223_ = 1000;
int thisCost = 100;
int i_225_ = 10;
for (int x = destX - i_225_; x <= destX + i_225_; x++) {
for (int y = destY - i_225_; y <= destY + i_225_; y++) {
if (x >= 0 && y >= 0 && x < 104 && y < 104 && cost[x][y] < 100) {
int i_228_ = 0;
if (x < destX) {
i_228_ = destX - x;
} else if (x > destX + xLength - 1) {
i_228_ = x - (destX + xLength - 1);
}
int i_229_ = 0;
if (y < destY) {
i_229_ = destY - y;
} else if (y > destY + yLength - 1) {
i_229_ = y - (destY + yLength - 1);
}
int i_230_ = i_228_ * i_228_ + i_229_ * i_229_;
if (i_230_ < i_223_ || i_230_ == i_223_ && cost[x][y] < thisCost) {
i_223_ = i_230_;
thisCost = cost[x][y];
curX = x;
curY = y;
}
}
}
}
if (i_223_ == 1000) {
return;
}
} else {
return;
}
}
tail = 0;
tileQueueX.set(tail, curX);
tileQueueY.set(tail++, curY);
int l5;
for (int j5 = l5 = via[curX][curY]; curX != c.getPosition().getLocalX() || curY != c.getPosition().getLocalY(); j5 = via[curX][curY]) {
if (j5 != l5) {
l5 = j5;
tileQueueX.set(tail, curX);
tileQueueY.set(tail++, curY);
}
if ((j5 & 2) != 0) {
curX++;
} else if ((j5 & 8) != 0) {
curX--;
}
if ((j5 & 1) != 0) {
curY++;
} else if ((j5 & 4) != 0) {
curY--;
}
}
c.getMovementHandler().reset();
int size = tail--;
int pathX = c.getPosition().getRegionX() * 8 + tileQueueX.get(tail);
int pathY = c.getPosition().getRegionY() * 8 + tileQueueY.get(tail);
c.getMovementHandler().addToPath(new Position(pathX, pathY));
for (int i = 1; i < size; i++) {
tail--;
pathX = c.getPosition().getRegionX() * 8 + tileQueueX.get(tail);
pathY = c.getPosition().getRegionY() * 8 + tileQueueY.get(tail);
c.getMovementHandler().addToPath(new Position(pathX, pathY));
}
c.getMovementHandler().finish();
// c.getMovementHandler().resetOnWalkPacket();
}
public int localize(int x, int mapRegion) {
return x - 8 * mapRegion;
}
/**
* Determines the NPCs simple follow path - This will only block the NPC
* from moving when an object blocks it, not search for a path.
*/
public static int checkDirection(Position position, int direction, boolean alternateRoute) {
int newDirection = direction;
/*
* switch (direction) { case 0: blocked =
* Region.blockedNorthWest(position.getX(), position.getY(), 0, false);
* if (blocked && !alternateRoute) newDirection = 3; else if (blocked &&
* alternateRoute) newDirection = 1; break; case 1: blocked =
* Region.blockedNorth(position.getX(), position.getY(), 0, false);
* break; case 2: blocked = Region.blockedNorthEast(position.getX(),
* position.getY(), 0, false); if (blocked && !alternateRoute)
* newDirection = 4; else if (blocked && alternateRoute) newDirection =
* 1; break; case 3: blocked = Region.blockedWest(position.getX(),
* position.getY(), 0, false); break; case 4: blocked =
* Region.blockedEast(position.getX(), position.getY(), 0, false);
* break; case 5: blocked = Region.blockedSouthWest(position.getX(),
* position.getY(), 0, false); if (blocked && !alternateRoute)
* newDirection = 3; else if (blocked && alternateRoute) newDirection =
* 6; break; case 6: blocked = Region.blockedSouth(position.getX(),
* position.getY(), 0, false); break; case 7: blocked =
* Region.blockedSouthEast(position.getX(), position.getY(), 0, false);
* if (blocked && !alternateRoute) newDirection = 4; else if (blocked &&
* alternateRoute) newDirection = 6; break; }
*/
return newDirection;
}
/*
* public static boolean clipAllowsAttack(Position attackerPosition,
* Position defenderPosition) { int xModifier = defenderPosition.getX() -
* attackerPosition.getX(); int yModifier = defenderPosition.getY() -
* attackerPosition.getY(); return Region.tileClipped(attackerPosition,
* xModifier, yModifier, attackerPosition.getZ(), false); }
*/
}
Tile Class:
Code:
package com.rs2.pf;
/**
* An individual tile on a <code>TileMap</code>. Immutable.
*
* @author Graham Edgecombe
*
*/
public class Tile {
/**
* Constant values used by the bitmask.
*/
public static final int NORTH_TRAVERSAL_PERMITTED = 1, EAST_TRAVERSAL_PERMITTED = 2, SOUTH_TRAVERSAL_PERMITTED = 4, WEST_TRAVERSAL_PERMITTED = 8;
/**
* A bitmask which determines which directions can be traversed.
*/
private final int traversalMask;
/**
* Creates the tile.
*
* @param traversalMask
* The traversal bitmask.
*/
public Tile(int traversalMask) {
this.traversalMask = traversalMask;
}
/**
* Gets the traversal bitmask.
*
* @return The traversal bitmask.
*/
public int getTraversalMask() {
return traversalMask;
}
/**
* Checks if northern traversal is permitted.
*
* @return True if so, false if not.
*/
public boolean isNorthernTraversalPermitted() {
return (traversalMask & NORTH_TRAVERSAL_PERMITTED) > 0;
}
/**
* Checks if eastern traversal is permitted.
*
* @return True if so, false if not.
*/
public boolean isEasternTraversalPermitted() {
return (traversalMask & EAST_TRAVERSAL_PERMITTED) > 0;
}
/**
* Checks if southern traversal is permitted.
*
* @return True if so, false if not.
*/
public boolean isSouthernTraversalPermitted() {
return (traversalMask & SOUTH_TRAVERSAL_PERMITTED) > 0;
}
/**
* Checks if western traversal is permitted.
*
* @return True if so, false if not.
*/
public boolean isWesternTraversalPermitted() {
return (traversalMask & WEST_TRAVERSAL_PERMITTED) > 0;
}
}
TileMap Class:
Code:
package com.rs2.pf;
/**
* A class which stores a grid of tiles and manages which directions can or
* cannot be traversed.
*
* @author Graham Edgecombe
*
*/
public class TileMap {
/**
* A tile in which traversal in any direction is permitted.
*/
public static final Tile EMPTY_TILE = new Tile(Tile.NORTH_TRAVERSAL_PERMITTED | Tile.EAST_TRAVERSAL_PERMITTED | Tile.SOUTH_TRAVERSAL_PERMITTED | Tile.WEST_TRAVERSAL_PERMITTED);
/**
* A tile in which traversal in no directions is permitted.
*/
public static final Tile SOLID_TILE = new Tile(0);
/**
* A two dimensional array of tiles.
*/
private final Tile[][] tiles;
/**
* The width of the tile map.
*/
private final int width;
/**
* The height of the tile map.
*/
private final int height;
/**
* Creates the tile map with the specified initial grid of tiles.
*
* @param tiles
* The tiles array.
* @throws IllegalArgumentException
* if the width is zero or the heights are zero or differ.
*/
public TileMap(Tile[][] tiles) {
this.tiles = tiles;
width = tiles.length;
if (width == 0) {
throw new IllegalArgumentException("Width is zero.");
}
int possibleHeight = tiles[0].length;
if (possibleHeight == 0) {
throw new IllegalArgumentException("Height is zero.");
}
for (int x = 0; x < width; x++) {
if (tiles[x].length != possibleHeight) {
throw new IllegalArgumentException("The heights differ.");
}
}
height = possibleHeight;
}
/**
* Creates a blank tile map with the specified width and height. The map is
* filled with <code>EMPTY_TILE</code>s.
*
* @param width
* The width of the tile map.
* @param height
* The height of the tile map.
*/
public TileMap(int width, int height) {
this(width, height, EMPTY_TILE);
}
/**
* Creates and fills a map with the specified width, height and default
* tile.
*
* @param width
* The width of the tile map.
* @param height
* The height of the tile map.
* @param defaultTile
* The default tile, which the map is filled with.
*/
public TileMap(int width, int height, Tile defaultTile) {
this.width = width;
this.height = height;
this.tiles = new Tile[width][height];
for (int x = 0; x < width; x++) {
for (int y = 0; y < width; y++) {
tiles[x][y] = defaultTile;
}
}
}
/**
* Checks the bounds of the specified coordinates.
*
* @param x
* X coordinate.
* @param y
* Y coordinate.
* @throw IllegalArgumentException if either coordinate is out of bounds.
*/
private void checkBounds(int x, int y) {
if (x < 0 || x >= width) {
throw new IllegalArgumentException("X coordinate out of permitted range.");
}
if (y < 0 || y >= height) {
throw new IllegalArgumentException("Y coordinate out of permitted range.");
}
}
/**
* Gets the width of the tile map.
*
* @return The width of the tile map.
*/
public int getWidth() {
return width;
}
/**
* Gets the height of the tile map.
*
* @return The height of the tile map.
*/
public int getHeight() {
return height;
}
/**
* Gets a tile.
*
* @param x
* The x coordinate.
* @param y
* The y coordinate.
* @return The tile at the coordinates.
* @throws IllegalArgumentException
* if the coordinates are out of bounds.
*/
public Tile getTile(int x, int y) {
checkBounds(x, y);
return tiles[x][y];
}
/**
* Sets a tile.
*
* @param x
* The x coordinate.
* @param y
* The y coordinate.
* @param tile
* The new tile.
* @throws IllegalArgumentException
* if the coordinates are out of bounds.
*/
public void setTile(int x, int y, Tile tile) {
checkBounds(x, y);
tiles[x][y] = tile;
}
}
TileMapBuilder Class:
Code:
package com.rs2.pf;
import java.util.HashSet;
import java.util.Set;
import com.rs2.cache.object.CacheObject;
import com.rs2.cache.object.GameObjectData;
import com.rs2.cache.region.RegionManager;
import com.rs2.cache.region.Regions;
import com.rs2.model.Position;
import com.rs2.model.World;
/**
* A class which assist in building <code>TileMap</code>s from a collection of
* <code>GameObject</code>s.
*
* @author Graham Edgecombe
*
*/
public class TileMapBuilder {
/**
* The tile map being built.
*/
private final TileMap tileMap;
/**
* The center position.
*/
private final Position centerPosition;
/**
* The radius.
*/
private final int radius;
/**
* Sets up the tile map builder with the specified radius, and center
* position.
*
* @param position
* The center position.
* @param radius
* The rad
*/
public TileMapBuilder(Position position, int radius) {
this.centerPosition = position;
this.tileMap = new TileMap(radius * 2 + 1, radius * 2 + 1);
this.radius = radius;
}
/**
* Builds the tile map.
*
* @return The built tile map.
*/
public TileMap build() {
// the region manager
RegionManager mgr = World.getWorld().getRegionManager();
// a set of regions covered by our center position + radius
Set<Regions> coveredRegions = new HashSet<Regions>();
// populates the set of covered regions
for (int x = (-radius - 1); x <= (radius + 1); x++) {
for (int y = (-radius - 1); y <= (radius + 1); y++) {
Position loc = centerPosition.transform(x, y, 0);
coveredRegions.add(mgr.getRegionByLocation(loc));
}
}
// calculate top left positions
int topX = centerPosition.getX() - radius;
int topY = centerPosition.getY() - radius;
// now fills in the tile map
for (Regions region : coveredRegions) {
for (CacheObject obj : region.getGameObjects()) {
GameObjectData definition = GameObjectData.forId(obj.getDef().getId());
if (!definition.isSolid()) {
continue;
}
Position loc = obj.getLocation();
if (loc.getZ() != centerPosition.getZ()) {
continue;
}
int sizeX = definition.getSizeX();
int sizeY = definition.getSizeY();
// position in the tile map
int posX = loc.getX() - topX;
int posY = loc.getY() - topY;
if (obj.getRotation() == 1 || obj.getRotation() == 3) {
// switch sizes if rotated
int temp = sizeX;
sizeX = sizeY;
sizeY = temp;
}
if ((posX + sizeX) < 0 || (posY + sizeY) < 0 || (posX) >= tileMap.getWidth() || (posY) >= tileMap.getHeight()) {
continue;
}
if (obj.getType() >= 0 && obj.getType() <= 3) {
// walls
if (posX >= 0 && posY >= 0 && posX < tileMap.getWidth() && posY < tileMap.getHeight()) {
// int finalRotation = (obj.getType() +
// obj.getRotation()) % 4;
int finalRotation = obj.getRotation();
// finalRotation - 0 = west, 1 = north, 2 = east, 3 =
// south
Tile t = tileMap.getTile(posX, posY);
int flags = t.getTraversalMask();
// clear flags
if (finalRotation == 0) {
flags &= ~Tile.WEST_TRAVERSAL_PERMITTED;
} else if (finalRotation == 1) {
flags &= ~Tile.NORTH_TRAVERSAL_PERMITTED;
} else if (finalRotation == 2) {
flags &= ~Tile.EAST_TRAVERSAL_PERMITTED;
} else {
flags &= ~Tile.SOUTH_TRAVERSAL_PERMITTED;
}
if (flags != t.getTraversalMask()) {
tileMap.setTile(posX, posY, new Tile(flags));
}
}
} else if (obj.getType() == 9) {
// diagonal walls
if (posX >= 0 && posY >= 0 && posX < tileMap.getWidth() && posY < tileMap.getHeight()) {
tileMap.setTile(posX, posY, TileMap.SOLID_TILE);
}
} else if (obj.getType() == 10 || obj.getType() == 11) {
// world objects
for (int offX = 0; offX <= sizeX; offX++) {
for (int offY = 0; offY <= sizeY; offY++) {
int x = offX + posX;
int y = offY + posY;
if (x >= 0 && y >= 0 && x < tileMap.getWidth() && y < tileMap.getHeight()) {
tileMap.setTile(x, y, TileMap.SOLID_TILE);
}
}
}
} else if (obj.getType() == 22) {
// floor decoration
if (definition.hasActions()) {
if (posX >= 0 && posY >= 0 && posX < tileMap.getWidth() && posY < tileMap.getHeight()) {
tileMap.setTile(posX, posY, TileMap.SOLID_TILE);
}
}
} else {
// 4-8 are wall decorations and 12-21 are roofs
// we can ignore those
}
}
}
return tileMap;
}
public Position getCenterPosition() {
return centerPosition;
}
}