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}