Attempted to make a self contained benchmark, and it looks like your code just loops forever..
Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class AStarPathFinder {
public static void main(String[] args) {
WorldNode node = new WorldNode(40);
AStarPathFinder path = new AStarPathFinder(node);
path.getPath(new Position(10, 10), new Position(11, 11));
}
static class Position {
Position(int x, int y) {
this.x = x;
this.y = y;
}
int x, y;
int getX() {
return x;
}
int getY() {
return y;
}
}
private static final class Point implements Comparable<Point> {
private Position end, position;
private Point parent;
private int cost;
public Point(Position end, Point parent, Position position, int cost) {
this.end = end;
this.parent = parent;
this.position = position;
this.cost = cost;
}
/**
* Gets the heuristic score for this point.
*
* @return the heuristic score
*/
private int getHeuristicScore() {
return Math.abs(position.getX() - end.getX())
+ Math.abs(position.getY() - end.getY());
}
/**
* Gets the cost of the path up to this point.
*
* @return the path cost
*/
public int getPathCost() {
Point current = this;
int totalCost = 0;
while (current.parent != null) {
totalCost += current.cost;
current = current.parent;
}
return totalCost;
}
/**
* Gets the projected path cost if the point had a given parent and
* cost.
*
* @param projectedParent the parent
* @param costToParent the cost to the parent
* @return the projected path cost
*/
public int getProjectedPathCost(Point projectedParent, int costToParent) {
Point current = projectedParent;
int projectedCost = costToParent;
while (current.parent != null) {
projectedCost += current.cost;
current = current.parent;
}
return projectedCost;
}
/**
* Gets the total cost.
*
* @return the total cost
*/
public int getTotalCost() {
return getPathCost() + getHeuristicScore();
}
@Override
public int compareTo(Point other) {
return getTotalCost() - other.getTotalCost();
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Point point = (Point) o;
return position.equals(point.position);
}
@Override
public int hashCode() {
return position.hashCode();
}
public void setParent(Point parent) {
this.parent = parent;
}
public void setCost(int cost) {
this.cost = cost;
}
}
static class WorldNode {
WorldNode(int size) {
tiles = new boolean[size][size];
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
tiles[x][y] = Math.random() > 0.5D;
}
}
}
boolean[][] tiles;
boolean canStep(Position from, Position to) {
if(to.x < 0 || to.y < 0 || to.x >= tiles.length || to.y >= tiles.length) return false;
return tiles[to.x][to.y];
}
}
private WorldNode world;
public AStarPathFinder(WorldNode world) {
this.world = world;
}
public List<Position> getPath(Position start, Position end) {
List<Point> openTiles = new LinkedList<>();
List<Position> usedTiles = new LinkedList<>();
Point current = new Point(end, null, start, 0);
openTiles.add(current);
while (!current.position.equals(end)) {
if (openTiles.isEmpty()) {
// no more walkable tiles
break;
}
openTiles.remove(current);
usedTiles.add(current.position);
List<Position> adjacentTiles = getAdjacentWalkableTiles(current.position);
if (usedTiles.containsAll(adjacentTiles)) {
// we have tried every walkable tile
break;
}
for (Position position : adjacentTiles) {
if (usedTiles.contains(position)) {
continue;
}
int deltaX = position.getX() - current.position.getX(),
deltaY = position.getY() - current.position.getY();
int cost = (int) Math.sqrt(Math.pow(deltaX, 2) + Math.pow(deltaY, 2));
Point point = new Point(end, current, position, cost);
if (!openTiles.contains(point)) {
openTiles.add(point);
} else {
Point other = openTiles.get(openTiles.indexOf(point));
if (other.getProjectedPathCost(point, cost) < other.getPathCost()) {
other.setParent(point);
other.setCost(cost);
Collections.sort(openTiles);
}
}
}
Collections.sort(openTiles);
current = openTiles.get(0);
}
List<Position> path = new LinkedList<>();
while (current.parent != null) {
path.add(current.position);
current = current.parent;
}
List<Position> rev = new LinkedList<>();
for (int i = 0; i < path.size(); i++) {
rev.add(path.remove(path.size() - (i + 1)));
}
return rev;
}
/**
* Gets the walkable tiles that are adjacent to a position.
*
* @param pos the position
* @return the tiles
*/
private List<Position> getAdjacentWalkableTiles(Position pos) {
List<Position> tiles = new ArrayList<>();
for (int deltaX = -1; deltaX <= 1; deltaX++) {
for (int deltaY = -1; deltaY <= 1; deltaY++) {
Position deltaPosition = new Position(pos.getX() + deltaX,
pos.getY() + deltaY);
if (world.canStep(pos, deltaPosition)) {
tiles.add(deltaPosition);
}
}
}
return tiles;
}
}
Originally Posted by
Major
You want to hard-code every possible path an npc could take..?
No? NPCs just walk toward the target usually, that's how RS workes.
Originally Posted by
Major
1. 1ms is not "much too long", you've got 599 left (unless you meant 1ms per character, in which case this doesn't happen).
Yes I meant per player, obviously.. .5ms is too long. .25 ms is too long. .1ms is too long. How quick do you think this algorithm is?
Originally Posted by
Major
2. Runescape has calculated the path on the server for the last ~300 revisions. It's likely the only reason it wasn't done initially was to reduce the server processing time (hardware in 2001-2006 wasn't as good as it is now, surprisingly). It's not as expensive as you think.
Thank you for re stating what I said?
Originally Posted by
Major
3. NPCs use a dumb path-finder yes, but that's because they always have and such a change would be a huge overhall. Also some current NPCs (e.g. Nex) use the A* algorithm to find a path instead.
I see no problem with using path finding for bosses, as it would be only a few NPCs. Just not every npc.
Originally Posted by
Kale
Well people can use cheat clients to noclip
Not if you CHECK TILE CLIPS server sided like I said.. Please learn to read.
Major