001 package com.croftsoft.core.ai.astar; 002 003 import java.util.*; 004 005 import com.croftsoft.core.lang.NullArgumentException; 006 import com.croftsoft.core.math.geom.Point2DD; 007 import com.croftsoft.core.math.geom.PointXY; 008 009 /********************************************************************* 010 * Grid cartographer for continuous space. 011 * 012 * The nodes are spaced equally apart in the 8 cardinal directions. 013 * 014 * @version 015 * 2003-05-10 016 * @since 017 * 2003-04-21 018 * @author 019 * <a href="https://www.croftsoft.com/">David Wallace Croft</a> 020 *********************************************************************/ 021 022 public final class GridCartographer 023 implements Cartographer 024 ////////////////////////////////////////////////////////////////////// 025 ////////////////////////////////////////////////////////////////////// 026 { 027 028 public static final double DEFAULT_STEP_SIZE = 1.0; 029 030 // 031 032 private final List adjacentList; 033 034 private final double stepSize; 035 036 private final SpaceTester spaceTester; 037 038 // 039 040 private PointXY goalPointXY; 041 042 ////////////////////////////////////////////////////////////////////// 043 ////////////////////////////////////////////////////////////////////// 044 045 public GridCartographer ( 046 SpaceTester spaceTester, 047 double stepSize ) 048 ////////////////////////////////////////////////////////////////////// 049 { 050 NullArgumentException.check ( this.spaceTester = spaceTester ); 051 052 this.stepSize = stepSize; 053 054 adjacentList = new ArrayList ( ); 055 } 056 057 public GridCartographer ( SpaceTester spaceTester ) 058 ////////////////////////////////////////////////////////////////////// 059 { 060 this ( 061 spaceTester, 062 DEFAULT_STEP_SIZE ); 063 } 064 065 ////////////////////////////////////////////////////////////////////// 066 ////////////////////////////////////////////////////////////////////// 067 068 public void setGoalPointXY ( PointXY goalPointXY ) 069 ////////////////////////////////////////////////////////////////////// 070 { 071 NullArgumentException.check ( this.goalPointXY = goalPointXY ); 072 } 073 074 ////////////////////////////////////////////////////////////////////// 075 // interface Cartographer methods 076 ////////////////////////////////////////////////////////////////////// 077 078 public double estimateCostToGoal ( Object node ) 079 ////////////////////////////////////////////////////////////////////// 080 { 081 return ( ( PointXY ) node ).distanceXY ( goalPointXY ); 082 } 083 084 public Iterator getAdjacentNodes ( Object node ) 085 ////////////////////////////////////////////////////////////////////// 086 { 087 PointXY pointXY = ( PointXY ) node; 088 089 adjacentList.clear ( ); 090 091 double distanceToGoal = pointXY.distanceXY ( goalPointXY ); 092 093 if ( distanceToGoal <= stepSize ) 094 { 095 adjacentList.add ( goalPointXY ); 096 097 return adjacentList.iterator ( ); 098 } 099 100 double x = pointXY.getX ( ); 101 102 double y = pointXY.getY ( ); 103 104 for ( int ix = -1; ix < 2; ix++ ) 105 { 106 for ( int iy = -1; iy < 2; iy++ ) 107 { 108 if ( ( ix == 0 ) 109 && ( iy == 0 ) ) 110 { 111 continue; 112 } 113 114 PointXY step = new Point2DD ( 115 ( ( int ) ( x / stepSize ) + ix ) * stepSize, 116 ( ( int ) ( y / stepSize ) + iy ) * stepSize ); 117 118 if ( spaceTester.isSpaceAvailable ( step ) ) 119 { 120 adjacentList.add ( step ); 121 } 122 } 123 } 124 125 return adjacentList.iterator ( ); 126 } 127 128 public double getCostToAdjacentNode ( 129 Object fromNode, 130 Object toNode ) 131 ////////////////////////////////////////////////////////////////////// 132 { 133 return ( ( PointXY ) fromNode ).distanceXY ( ( PointXY ) toNode ); 134 } 135 136 public boolean isGoalNode ( Object node ) 137 ////////////////////////////////////////////////////////////////////// 138 { 139 return goalPointXY.distanceXY ( ( PointXY ) node ) == 0.0; 140 } 141 142 ////////////////////////////////////////////////////////////////////// 143 ////////////////////////////////////////////////////////////////////// 144 }