Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package rpc.entities.pathfinder;
- import java.util.ArrayList;
- import java.util.PriorityQueue;
- import org.newdawn.slick.Graphics;
- import org.newdawn.slick.SlickException;
- import rpc.entities.EntityBase;
- import rpc.map.MapModule;
- import rpc.objects.ObjectBase;
- import rpc.objects.ObjectModule;
- import rpc.resources.ResourceModule;
- import rpc.resources.ResourceModule.ResourceType;
- import rpc.states.StateBase;
- import rpc.utilities.OrderedPair;
- import rpc.utilities.Utilities;
- public class PathFinder {
- private MapModule map = StateBase.getMapModule();;
- private ResourceModule resource = StateBase.getResourceModule();
- private ObjectModule object = StateBase.getObjectModule();
- private PriorityQueue<PathNode> openPathNodes = new PriorityQueue<PathNode>();
- private PriorityQueue<SearchNode> openSearchNodes = new PriorityQueue<SearchNode>();
- private PathNode basePathNode;
- private SearchNode baseSearchNode;
- private int mapWidth, mapHeight;
- private PathNode[][] pathNodes;
- private SearchNode[][] searchNodes;
- //For faster reading of entitylists, to find targets
- byte[][] entityMap;
- public PathFinder() throws SlickException{
- mapWidth = map.getMapWidth();
- mapHeight = map.getMapHeight();
- entityMap = new byte[mapWidth][mapHeight];
- pathNodes = new PathNode[mapWidth][mapHeight];
- searchNodes = new SearchNode[mapWidth][mapHeight];
- for (int x = 0; x < pathNodes.length; x++){
- for (int y = 0; y < pathNodes[x].length; y++){
- pathNodes[x][y] = new PathNode();
- searchNodes[x][y] = new SearchNode();
- }
- }
- }
- public ArrayList<OrderedPair> findPath(int startX, int startY, int goalX, int goalY, boolean allowBlocked) {
- if ((goalX < 0) || (goalX > map.getMapWidth()-1) || (goalY < 0) || (goalY > map.getMapHeight()-1))
- return null;
- //We are already here, so just return the coordinates at your feet.
- if ((startX == goalX) && (startY == goalY)){
- ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
- returnedPath.add(OrderedPair.getOrderedPair(goalX, goalY));
- return returnedPath;
- }
- boolean running = true;
- boolean searchBlocked = false;
- int pathVariance = Utilities.randomInt(10)+1;
- while (running){
- for (int x = 0; x < pathNodes.length; x++){
- for (int y = 0; y < pathNodes[x].length; y++){
- pathNodes[x][y].flagResettable();
- //pathNodes[x][y].resetNode(x, y, goalX, goalY, pathVariance);
- }
- }
- openPathNodes.clear();
- basePathNode = pathNodes[startX][startY];
- openPathNodes.add(pathNodes[startX][startY]);
- pathNodes[startX][startY].openNode();
- pathNodes[startX][startY].resetNode(startX, startY, goalX, goalY, pathVariance);
- boolean foundPath = false;
- while (!foundPath){
- //baseNode = openNodes.get(openNodes.size()-1);
- basePathNode = openPathNodes.poll();
- //Check the values around the next ordered pair.
- int thisX = basePathNode.getX();
- int thisY = basePathNode.getY();
- for (int x = -1; x < 2; x++) {
- y:
- for (int y = -1; y < 2; y++) {
- if ((x == 0) && (y == 0))
- continue;
- int checkX = thisX+x;
- int checkY = thisY+y;
- if ((checkX > map.getMapWidth()-2) || (checkX < 2) || (checkY > map.getMapHeight()-2) || (checkY < 2))
- continue;
- //If the node needs to be reset, reset it!
- if (pathNodes[checkX][checkY].isResettable())
- pathNodes[checkX][checkY].resetNode(checkX, checkY, goalX, goalY, pathVariance);
- // If it's not on the closed list, add it to the checkList to look at later.
- if (pathNodes[checkX][checkY].isClosed())
- continue;
- //If you're not allowed to pass blocked tiles, don't!
- if (map.getBlockMap()[checkX][checkY] > 0){
- if (searchBlocked){
- for (int l = 0; l < map.getMapLayers(); l++) {
- int tileID = map.getTileId(checkX, checkY, l);
- if (map.getMapTileLoader().isTileInvulnerable(tileID)){
- continue y;
- }
- }
- }else{
- continue y;
- }
- }
- //TODO: This works for now, although there are situations where when the second pass to dig a path triggers,
- //it may cause a logical shortest path to be ignored.
- //Check the diagonal movement to see if it's valid.
- if ((checkX > thisX) && (checkY > thisY)
- && (map.getBlockMap()[checkX-1][checkY] > 0 || map.getBlockMap()[checkX][checkY-1] > 0)){
- continue;
- }else if ((checkX < thisX) && (checkY < thisY)
- && (map.getBlockMap()[checkX+1][checkY] > 0 || map.getBlockMap()[checkX][checkY+1] > 0)){
- continue;
- }else if ((checkX > thisX) && (checkY < thisY)
- && (map.getBlockMap()[checkX-1][checkY] > 0 || map.getBlockMap()[checkX][checkY+1] > 0)){
- continue;
- }else if ((checkX < thisX) && (checkY > thisY)
- && (map.getBlockMap()[checkX+1][checkY] > 0 || map.getBlockMap()[checkX][checkY-1] > 0)){
- continue;
- }
- PathNode checkNode = pathNodes[checkX][checkY];
- //Calculate movement costs for this tile.
- //Remember terrain movement costs should also be increased on diagonals from their base, not just added.
- int movementCost = 0;
- int nodeMValue = checkNode.getM();
- if (((checkX > thisX) && (checkY > thisY))
- || ((checkX < thisX) && (checkY < thisY))
- || ((checkX > thisX) && (checkY < thisY))
- || ((checkX < thisX) && (checkY > thisY))){
- movementCost = (int)(10+nodeMValue+((10+nodeMValue)*0.4));
- }else{
- movementCost = 10+nodeMValue;
- }
- // We are already on the open list.
- if (checkNode.isOpen()){
- int gValueCheck = basePathNode.getG()+movementCost;
- if (gValueCheck < checkNode.getG())
- checkNode.setParent(basePathNode);
- }else{
- //Open tile.
- checkNode.openNode();
- //Assign parent to this tile, should be the original we're fetching
- checkNode.setParent(basePathNode);
- //Calc gCost (NOTE: Incomplete. Is this where terrain would come in?)
- checkNode.setG(basePathNode.getG()+movementCost);
- //Calc fCost
- checkNode.calcF();
- openPathNodes.add(checkNode);
- //Break if you find the goal.
- if ((checkX == goalX) && (checkY == goalY))
- return buildPath(checkNode);
- }
- }
- }
- //Close the node.
- basePathNode.closeNode();
- //I've searched everywhere I could, and I've ran out of nodes.
- if (openPathNodes.size() <= 0)
- break;
- }
- if (allowBlocked && !searchBlocked){
- searchBlocked = true;
- }else{
- running = false;
- }
- }
- return null;
- }
- /**
- * Get a list of valid coordinates that are within the movement cost of the starting position.
- *
- * @param startX - The X coordinate we will start on.
- * @param startY - The Y coordinate we will start on.
- * @param range - The maximum range in tiles. Note, that the value inputed will be multiplied by 10 internally
- * for proper movement cost calculations.
- * @param allowBlocked - If we are allowed to search through blocked tiles.
- *
- * @return The movement cost map to reach all the tiles in range.
- */
- public ArrayList<OrderedPair> getCoordinatesInRange(int startX, int startY, int range, boolean allowBlocked) {
- //Only reset nodes and maps in range, why bother with the rest?
- for (int x = startX-range; x < startX+range; x++){
- for (int y = startY-range; y < startY+range; y++){
- if ((x > 250) || (x < 2) || (y > 250) || (y < 2))
- continue;
- searchNodes[x][y].flagResettable();
- }
- }
- int movementCostMax = range*10;
- ArrayList<OrderedPair> list = new ArrayList<OrderedPair>();
- openSearchNodes.clear();
- baseSearchNode = searchNodes[startX][startY];
- openSearchNodes.add(searchNodes[startX][startY]);
- searchNodes[startX][startY].openNode();
- searchNodes[startX][startY].resetNode(startX, startY);
- boolean foundPath = false;
- while (!foundPath){
- //baseNode = openNodes.get(openNodes.size()-1);
- baseSearchNode = openSearchNodes.poll();
- //Check the values around the next ordered pair.
- int thisX = baseSearchNode.getX();
- int thisY = baseSearchNode.getY();
- for (int x = -1; x < 2; x++) {
- for (int y = -1; y < 2; y++) {
- if ((x == 0) && (y == 0))
- continue;
- int checkX = thisX+x;
- int checkY = thisY+y;
- if ((checkX > map.getMapWidth()-2) || (checkX < 2) || (checkY > map.getMapHeight()-2) || (checkY < 2))
- continue;
- //If the node needs to be reset, reset it!
- if (searchNodes[checkX][checkY].isResettable())
- searchNodes[checkX][checkY].resetNode(checkX, checkY);
- // If it's not on the closed list, add it to the checkList to look at later.
- if (searchNodes[checkX][checkY].isClosed())
- continue;
- SearchNode checkNode = searchNodes[checkX][checkY];
- //Calculate movement costs for this tile.
- //Remember terrain movement costs should also be increased on diagonals from their base, not just added.
- int movementCost = 0;
- int nodeMValue = checkNode.getM();
- if (((checkX > thisX) && (checkY > thisY))
- || ((checkX < thisX) && (checkY < thisY))
- || ((checkX > thisX) && (checkY < thisY))
- || ((checkX < thisX) && (checkY > thisY))){
- movementCost = (int)(10+nodeMValue+((10+nodeMValue)*0.4));
- }else{
- movementCost = 10+nodeMValue;
- }
- // We are already on the open list.
- if (checkNode.isOpen()){
- int gValueCheck = baseSearchNode.getG()+movementCost;
- if (gValueCheck < checkNode.getG())
- checkNode.setParent(baseSearchNode);
- }else{
- //Open tile.
- checkNode.openNode();
- //Assign parent to this tile, should be the original we're fetching
- checkNode.setParent(baseSearchNode);
- //Calc gCost and add it to the nodelist if it's below range.
- if (baseSearchNode.getG()+movementCost <= movementCostMax){
- checkNode.setG(baseSearchNode.getG()+movementCost);
- openSearchNodes.add(checkNode);
- list.add(OrderedPair.getOrderedPair(checkX, checkY));
- }
- }
- }
- }
- //Close the node.
- baseSearchNode.closeNode();
- //I've searched everywhere I could, and I've ran out of nodes.
- if (openSearchNodes.size() <= 0)
- break;
- }
- return list;
- }
- public ArrayList<OrderedPair> buildPath(PathNode node) {
- ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
- PathNode nextNode = node;
- OrderedPair nextPair = OrderedPair.getOrderedPair(node.getX(), node.getY());
- returnedPath.add(nextPair);
- while (nextNode.getParent() != null){
- nextNode = nextNode.getParent();
- nextPair = OrderedPair.getOrderedPair(nextNode.getX(), nextNode.getY());
- returnedPath.add(nextPair);
- }
- return returnedPath;
- }
- public ArrayList<OrderedPair> buildPath(SearchNode node) {
- ArrayList<OrderedPair> returnedPath = new ArrayList<OrderedPair>();
- SearchNode nextNode = node;
- OrderedPair nextPair = OrderedPair.getOrderedPair(node.getX(), node.getY());
- returnedPath.add(nextPair);
- while (nextNode.getParent() != null){
- nextNode = nextNode.getParent();
- nextPair = OrderedPair.getOrderedPair(nextNode.getX(), nextNode.getY());
- returnedPath.add(nextPair);
- }
- return returnedPath;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement