Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (769)
Games in Android Showcase (230)
games submitted by our members
Games in WIP (855)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
  JavaGaming.org - Pastebin



Author: nelsongames (posted 2018-03-05 17:56:34, viewed 855 times)

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172   173   174   175   176   177   178   179   180   181   182   183   184   185   186   187   188   189   190   191   192   193   194   195   196   197   198   199   200   201   202   203   204   205   206   207   208   209   210   211   212   213   214   215   216   217   218   219   220   221   222   223   224   225   226   227   228   229   230   231   232   233   234   235   236   237   238   239   240   241   242   243   244   245   246   247   248   249   250   251   252   253   254   255   256   257   258   259   260   261   262   263   264   265   266   267   268   269   270   271   272   273   274   275   276   277   278   279   280   281   282   283   284   285   286   287   288   289   290   291   292   293   294   295   296   297   298   299   300   301   302   303   304   305   306   307   308   309   310   311   312   313   314   315   316   317   318   319   320   321   322   323   324   325   326   327   328   329   330   331   332   333   334   335   336   337   338   339   340   341  
/*******************************************************************************
 * Copyright 2014 See AUTHORS file.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ******************************************************************************/

package com.badlogic.gdx.ai.pfa.indexed;

import com.badlogic.gdx.ai.pfa.Connection;
import com.badlogic.gdx.ai.pfa.GraphPath;
import com.badlogic.gdx.ai.pfa.Heuristic;
import com.badlogic.gdx.ai.pfa.PathFinder;
import com.badlogic.gdx.ai.pfa.PathFinderQueue;
import com.badlogic.gdx.ai.pfa.PathFinderRequest;
import com.badlogic.gdx.utils.Array;
import com.badlogic.gdx.utils.BinaryHeap;
import com.badlogic.gdx.utils.TimeUtils;

/** A fully implemented {@link PathFinder} that can perform both interruptible and non-interruptible pathfinding.
 * <p>
 * This implementation is a common variation of the A* algorithm that is faster than the general A*.
 * <p>
 * In the general A* implementation, data are held for each node in the open or closed lists, and these data are held as a
 * NodeRecord instance. Records are created when a node is first considered and then moved between the open and closed lists, as
 * required. There is a key step in the algorithm where the lists are searched for a node record corresponding to a particular
 * node. This operation is something time-consuming.
 * <p>
 * The indexed A* algorithm improves execution speed by using an array of all the node records for every node in the graph. Nodes
 * must be numbered using sequential integers (see {@link IndexedGraph#getIndex(Object)}), so we don't need to search for a node in the
 * two lists at all. We can simply use the node index to look up its record in the array (creating it if it is missing). This
 * means that the close list is no longer needed. To know whether a node is open or closed, we use the {@link NodeRecord#category
 * category} of the node record. This makes the search step very fast indeed (in fact, there is no search, and we can go straight
 * to the information we need). Unfortunately, we can't get rid of the open list because we still need to be able to retrieve the
 * element with the lowest cost. However, we use a {@link BinaryHeap} for the open list in order to keep performance as high as
 * possible.
 * 
 * @param <N> Type of node
 * 
 * @author davebaol */
public class IndexedAStarPathFinder<N> implements PathFinder<N> {
   IndexedGraph<N> graph;
   NodeRecord<N>[] nodeRecords;
   BinaryHeap<NodeRecord<N>> openList;
   NodeRecord<N> current;
   public Metrics metrics;

   /** The unique ID for each search run. Used to mark nodes. */
   private int searchId;

   private static final int UNVISITED = 0;
   private static final int OPEN = 1;
   private static final int CLOSED = 2;

   @SuppressWarnings("unchecked")
   public IndexedAStarPathFinder (IndexedGraph<N> graph, boolean calculateMetrics) {
      this.graph = graph;
      this.nodeRecords = (NodeRecord<N>[])new NodeRecord[graph.getNodeCount()];
      this.openList = new BinaryHeap<NodeRecord<N>>();
      if (calculateMetrics) this.metrics = new Metrics();
   }

   @Override
   public boolean searchConnectionPath (N startNode, N endNode, Heuristic<N> heuristic, GraphPath<Connection<N>> outPath) {

      // Perform AStar
      boolean found = search(startNode, endNode, heuristic);

      if (found) {
         // Create a path made of connections
         generateConnectionPath(startNode, outPath);
      }

      return found;
   }

   @Override
   public boolean searchNodePath (N startNode, N endNode, Heuristic<N> heuristic, GraphPath<N> outPath) {

      // Perform AStar
      boolean found = search(startNode, endNode, heuristic);

      if (found) {
         // Create a path made of nodes
         generateNodePath(startNode, outPath);
      }

      return found;
   }

   protected boolean search (N startNode, N endNode, Heuristic<N> heuristic) {

      initSearch(startNode, endNode, heuristic);

      // Iterate through processing each node
      do {
         // Retrieve the node with smallest estimated total cost from the open list
         current = openList.pop();
         current.category = CLOSED;

         // Terminate if we reached the goal node
         if (current.node == endNode) return true;

         visitChildren(endNode, heuristic);

      } while (openList.size > 0);

      // We've run out of nodes without finding the goal, so there's no solution
      return false;
   }

   @Override
   public boolean search (PathFinderRequest<N> request, long timeToRun) {

      long lastTime = TimeUtils.nanoTime();

      // We have to initialize the search if the status has just changed
      if (request.statusChanged) {
         initSearch(request.startNode, request.endNode, request.heuristic);
         request.statusChanged = false;
      }

      // Iterate through processing each node
      do {

         // Check the available time
         long currentTime = TimeUtils.nanoTime();
         timeToRun -= currentTime - lastTime;
         if (timeToRun <= PathFinderQueue.TIME_TOLERANCE) return false;

         // Retrieve the node with smallest estimated total cost from the open list
         current = openList.pop();
         current.category = CLOSED;

         // Terminate if we reached the goal node; we've found a path.
         if (current.node == request.endNode) {
            request.pathFound = true;

            generateNodePath(request.startNode, request.resultPath);

            return true;
         }

         // Visit current node's children
         visitChildren(request.endNode, request.heuristic);

         // Store the current time
         lastTime = currentTime;

      } while (openList.size > 0);

      // The open list is empty and we've not found a path.
      request.pathFound = false;
      return true;
   }

   protected void initSearch (N startNode, N endNode, Heuristic<N> heuristic) {
      if (metrics != null) metrics.reset();

      // Increment the search id
      if (++searchId < 0) searchId = 1;

      // Initialize the open list
      openList.clear();

      // Initialize the record for the start node and add it to the open list
      NodeRecord<N> startRecord = getNodeRecord(startNode);
      startRecord.node = startNode;
      startRecord.connection = null;
      startRecord.costSoFar = 0;
      addToOpenList(startRecord, heuristic.estimate(startNode, endNode));

      current = null;
   }

   protected void visitChildren (N endNode, Heuristic<N> heuristic) {
      // Get current node's outgoing connections
      Array<Connection<N>> connections = graph.getConnections(current.node);

      // Loop through each connection in turn
      for (int i = 0; i < connections.size; i++) {
         if (metrics != null) metrics.visitedNodes++;

         Connection<N> neighbor = connections.get(i);

         // Get the cost estimate for the node
         N node = neighbor.getToNode();
         float nodeCost = current.costSoFar + neighbor.getCost();

         float nodeHeuristic;
         NodeRecord<N> nodeRecord = getNodeRecord(node);
         if (nodeRecord.category == CLOSED) { // The node is closed

            // If we didn't find a shorter route, skip
            if (nodeRecord.costSoFar <= nodeCost)
               continue;

            // We can use the node's old cost values to calculate its heuristic
            // without calling the possibly expensive heuristic function
            nodeHeuristic = nodeRecord.getEstimatedTotalCost() - nodeRecord.costSoFar;
         } else if (nodeRecord.category == OPEN) { // The node is open

            // If our route is no better, then skip
            if (nodeRecord.costSoFar <= nodeCost)
               continue;

            // Remove it from the open list (it will be re-added with the new cost)
            openList.remove(nodeRecord);

            // We can use the node's old cost values to calculate its heuristic
            // without calling the possibly expensive heuristic function
            nodeHeuristic = nodeRecord.getEstimatedTotalCost() - nodeRecord.costSoFar;
         } else { // the node is unvisited

            // We'll need to calculate the heuristic value using the function,
            // since we don't have a node record with a previously calculated value

            nodeHeuristic = heuristic.estimate(node, endNode);
         }

         // Update node record's cost and connection
         nodeRecord.costSoFar = nodeCost;
         nodeRecord.connection = neighbor;

         // Add it to the open list with the estimated total cost
         addToOpenList(nodeRecord, nodeCost + nodeHeuristic);
      }

   }

   protected void generateConnectionPath (N startNode, GraphPath<Connection<N>> outPath) {

      // Work back along the path, accumulating connections
      // outPath.clear();
      while (current.node != startNode) {
         outPath.add(current.connection);
         current = nodeRecords[graph.getIndex(current.connection.getFromNode())];
      }

      // Reverse the path
      outPath.reverse();
   }

   protected void generateNodePath (N startNode, GraphPath<N> outPath) {

      // Work back along the path, accumulating nodes
      // outPath.clear();
      while (current.connection != null) {
         outPath.add(current.node);
         current = nodeRecords[graph.getIndex(current.connection.getFromNode())];
      }
      outPath.add(startNode);

      // Reverse the path
      outPath.reverse();
   }

   protected void addToOpenList (NodeRecord<N> nodeRecord, float estimatedTotalCost) {
      openList.add(nodeRecord, estimatedTotalCost);
      nodeRecord.category = OPEN;
      if (metrics != null) {
         metrics.openListAdditions++;
         metrics.openListPeak = Math.max(metrics.openListPeak, openList.size);
      }
   }

   protected NodeRecord<N> getNodeRecord (N node) {
      int index = graph.getIndex(node);
      NodeRecord<N> nr = nodeRecords[index];
      if (nr != null) {
         if (nr.searchId != searchId) {
            nr.category = UNVISITED;
            nr.searchId = searchId;
         }
         return nr;
      }
      nr = nodeRecords[index] = new NodeRecord<N>();
      nr.node = node;
      nr.searchId = searchId;
      return nr;
   }

   /** This nested class is used to keep track of the information we need for each node during the search.
    * 
    * @param <N> Type of node
    * 
    * @author davebaol */
   static class NodeRecord<N> extends BinaryHeap.Node {
      /** The reference to the node. */
      N node;

      /** The incoming connection to the node */
      Connection<N> connection;

      /** The actual cost from the start node. */
      float costSoFar;

      /** The node category: {@link #UNVISITED}, {@link #OPEN} or {@link #CLOSED}. */
      int category;

      /** ID of the current search. */
      int searchId;

      /** Creates a {@code NodeRecord}. */
      public NodeRecord () {
         super(0);
      }

      /** Returns the estimated total cost. */
      public float getEstimatedTotalCost () {
         return getValue();
      }
   }

   /** A class used by {@link IndexedAStarPathFinder} to collect search metrics.
    * 
    * @author davebaol */
   public static class Metrics {
      public int visitedNodes;
      public int openListAdditions;
      public int openListPeak;

      public Metrics () {
      }

      public void reset () {
         visitedNodes = 0;
         openListAdditions = 0;
         openListPeak = 0;
      }
   }
}





Dump your java code here :



Special syntax:
  • To highlight a line (yellow background), prefix it with '@@'
  • To indicate that a line should be removed (red background), prefix it with '-'
  • To indicate that a line should be added (green background), prefix it with '+'
  • To post multiple snippets, seperate them by '~~~~'
  EOF
 
EgonOlsen (1567 views)
2018-06-10 19:43:48

EgonOlsen (1539 views)
2018-06-10 19:43:44

EgonOlsen (1141 views)
2018-06-10 19:43:20

DesertCoockie (1567 views)
2018-05-13 18:23:11

nelsongames (1171 views)
2018-04-24 18:15:36

nelsongames (1548 views)
2018-04-24 18:14:32

ivj94 (2305 views)
2018-03-24 14:47:39

ivj94 (1514 views)
2018-03-24 14:46:31

ivj94 (2601 views)
2018-03-24 14:43:53

Solater (878 views)
2018-03-17 05:04:08
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!