001/* 002 * Trident - A Multithreaded Server Alternative 003 * Copyright 2014 The TridentSDK Team 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018package net.tridentsdk.server.entity.ai.pathfind; 019 020import net.tridentsdk.base.Block; 021import net.tridentsdk.base.Position; 022import net.tridentsdk.base.Substance; 023import net.tridentsdk.entity.Entity; 024import net.tridentsdk.util.Vector; 025 026import javax.annotation.concurrent.NotThreadSafe; 027import java.util.ArrayList; 028import java.util.HashSet; 029import java.util.List; 030 031@NotThreadSafe 032public class Pathfinder { 033 private final Entity entity; 034 private final Node start; 035 private final Node end; 036 private final double range; 037 038 private final HashSet<Node> openList = new HashSet<>(); 039 private final HashSet<Node> closedList = new HashSet<>(); 040 private Path result; 041 042 public Pathfinder(Entity entity, Position target, double range) { 043 this.entity = entity; 044 this.start = new Node(null, entity.position()); 045 this.end = new Node(null, target); 046 this.range = range; 047 } 048 049 public void find() { 050 // Possibly run this on its own thread and let the entity wait until getResult != null 051 openList.add(start); 052 closedList.add(start); 053 while(!openList.isEmpty()) { 054 Node current = getBestTile(); 055 openList.remove(current); 056 for(Node neighbor : getNeighbors(current)) { 057 closedList.add(neighbor); 058 if(start.distance(neighbor) > range * range || !canWalkThrough(neighbor)) { 059 continue; 060 } 061 062 Node floor; 063 if(!canWalkThrough(neighbor)) { 064 // Floor isn't really the floor anymore, its now the block above the neighbor 065 if(canWalkThrough(floor = neighbor.getRelative(0, 1, 0))) { 066 neighbor = floor; 067 neighbor.setParent(current); 068 } else { 069 continue; 070 } 071 } else if(!canWalkOn(floor = neighbor.getRelative(0, -1, 0))) { 072 if(canWalkThrough(floor) && canWalkOn(floor.getRelative(0, -1, 0))) { 073 // We can down ^-^ 074 neighbor = floor; 075 } else { 076 continue; 077 } 078 } 079 080 openList.add(neighbor); 081 if(end.equals(neighbor)) { 082 // We found our destination! 083 end.setParent(current); 084 openList.clear(); 085 break; 086 } 087 088 neighbor.calculateHGF(end); 089 } 090 } 091 092 if(end.parent() != null) { 093 this.result = new Path(end); 094 } 095 } 096 097 public Path getResult() { 098 return result; 099 } 100 101 private List<Node> getNeighbors(Node current) { 102 List<Node> list = new ArrayList<>(); 103 for(int x = -1; x <= 1; x++) { 104 for(int z = -1; z <= 1; z++) { 105 if(x == 0 && z == 0) { 106 continue; 107 } 108 109 Node neighbor = current.getRelative(x, 0, z); 110 if(!closedList.contains(neighbor)) { 111 list.add(neighbor); 112 } 113 } 114 } 115 116 return list; 117 } 118 119 private Node getBestTile() { 120 Node best = null; 121 double bestScore = Double.MAX_VALUE; 122 for(Node node : openList) { 123 if(node.getF() < bestScore) { 124 best = node; 125 bestScore = node.getF(); 126 } 127 } 128 129 return best; 130 } 131 132 private boolean canWalkOn(Node node) { 133 Block block = entity.world().blockAt(Position.create(entity.world(), node.x(), node.y(), node.z())); 134 return block.substance().isSolid(); 135 } 136 137 private boolean canWalkThrough(Node node) { 138 Block block = entity.world().blockAt(Position.create(entity.world(), node.x(), node.y(), node.z())); 139 return canWalkThrough(block.substance()) && canWalkThrough(block.relativeBlock(new Vector(0, 1, 0)).substance()); 140 } 141 142 private boolean canWalkThrough(Substance type) { 143 return type == Substance.AIR || type == Substance.LONG_GRASS || type == Substance.DEAD_BUSH || type == Substance.SAPLING 144 || type == Substance.RED_ROSE || type == Substance.YELLOW_FLOWER || type == Substance.VINE; 145 } 146}