001 package com.croftsoft.core.ai.astar; 002 003 import java.awt.Point; 004 import java.util.*; 005 006 import com.croftsoft.core.lang.NullArgumentException; 007 import com.croftsoft.core.lang.Testable; 008 009 /********************************************************************* 010 * An A* algorithm test. 011 * 012 * @version 013 * 2003-05-09 014 * @since 015 * 2002-04-21 016 * @author 017 * <a href="https://www.croftsoft.com/">David Wallace Croft</a> 018 *********************************************************************/ 019 020 public final class AStarTest 021 implements Cartographer, Testable 022 ////////////////////////////////////////////////////////////////////// 023 ////////////////////////////////////////////////////////////////////// 024 { 025 026 private static final int MIN_X = -10; 027 028 private static final int MIN_Y = -10; 029 030 private static final int MAX_X = 10; 031 032 private static final int MAX_Y = 10; 033 034 // 035 036 private final Set blockedSet; 037 038 private final Point goalPoint; 039 040 private final Point jumpPoint; 041 042 ////////////////////////////////////////////////////////////////////// 043 ////////////////////////////////////////////////////////////////////// 044 045 public static void main ( String [ ] args ) 046 ////////////////////////////////////////////////////////////////////// 047 { 048 System.out.println ( test ( args ) ); 049 } 050 051 public static boolean test ( String [ ] args ) 052 ////////////////////////////////////////////////////////////////////// 053 { 054 try 055 { 056 // Finds its way around a wall. 057 058 AStarTest test1 = new AStarTest ( 059 new Point ( 4, 0 ), 060 new Point [ ] { 061 new Point ( 1, 1 ), 062 new Point ( 1, 0 ), 063 new Point ( 1, -1 ) } ); 064 065 // Trapped by walls. 066 067 AStarTest test2 = new AStarTest ( 068 new Point ( 4, 0 ), 069 new Point [ ] { 070 new Point ( -1, -1 ), 071 new Point ( -1, 0 ), 072 new Point ( -1, 1 ), 073 new Point ( 0, -1 ), 074 new Point ( 0, 1 ), 075 new Point ( 1, -1 ), 076 new Point ( 1, 0 ), 077 new Point ( 1, 1 ) } ); 078 079 // Goal enclosed by walls. 080 081 AStarTest test3 = new AStarTest ( 082 new Point ( 5, 0 ), 083 new Point [ ] { 084 new Point ( 4, -1 ), 085 new Point ( 4, 0 ), 086 new Point ( 4, 1 ), 087 new Point ( 5, -1 ), 088 new Point ( 5, 1 ), 089 new Point ( 6, -1 ), 090 new Point ( 6, 0 ), 091 new Point ( 6, 1 ) } ); 092 093 // Goal enclosed by walls but teleport jump available. 094 095 AStarTest test4 = new AStarTest ( 096 new Point ( 4, 0 ), 097 new Point [ ] { 098 new Point ( 3, -1 ), 099 new Point ( 3, 0 ), 100 new Point ( 3, 1 ), 101 new Point ( 4, -1 ), 102 new Point ( 4, 1 ), 103 new Point ( 5, -1 ), 104 new Point ( 5, 0 ), 105 new Point ( 5, 1 ) }, 106 new Point ( MIN_X, MIN_Y ) ); 107 108 // Goal clear on right but teleport jump on left closer. 109 110 AStarTest test5 = new AStarTest ( 111 new Point ( MAX_X, 0 ), 112 new Point [ 0 ], 113 new Point ( -3, 0 ) ); 114 115 return test ( test1 ) 116 && test ( test2 ) 117 && test ( test3 ) 118 && test ( test4 ) 119 && test ( test5 ); 120 } 121 catch ( Exception ex ) 122 { 123 ex.printStackTrace ( ); 124 125 return false; 126 } 127 } 128 129 public static boolean test ( AStarTest test ) 130 ////////////////////////////////////////////////////////////////////// 131 { 132 System.out.println ( "Testing..." ); 133 134 AStar aStar = new AStar ( test ); 135 136 aStar.reset ( new Point ( 0, 0 ) ); 137 138 while ( true ) 139 { 140 aStar.loop ( ); 141 142 if ( aStar.isListEmpty ( ) ) 143 { 144 break; 145 } 146 } 147 148 System.out.println ( "goalFound: " + aStar.isGoalFound ( ) ); 149 150 Iterator iterator = aStar.getPath ( ); 151 152 while ( iterator.hasNext ( ) ) 153 { 154 System.out.println ( iterator.next ( ) ); 155 } 156 157 return true; 158 } 159 160 ////////////////////////////////////////////////////////////////////// 161 ////////////////////////////////////////////////////////////////////// 162 163 public AStarTest ( 164 Point goalPoint, 165 Point [ ] blockedPoints, 166 Point jumpPoint ) 167 ////////////////////////////////////////////////////////////////////// 168 { 169 this.goalPoint = goalPoint; 170 171 blockedSet = new HashSet ( ); 172 173 for ( int i = 0; i < blockedPoints.length; i++ ) 174 { 175 blockedSet.add ( blockedPoints [ i ] ); 176 } 177 178 this.jumpPoint = jumpPoint; 179 } 180 181 public AStarTest ( 182 Point goalPoint, 183 Point [ ] blockedPoints ) 184 ////////////////////////////////////////////////////////////////////// 185 { 186 this ( goalPoint, blockedPoints, null ); 187 } 188 189 ////////////////////////////////////////////////////////////////////// 190 ////////////////////////////////////////////////////////////////////// 191 192 public double estimateCostToGoal ( Object node ) 193 ////////////////////////////////////////////////////////////////////// 194 { 195 return getCostToAdjacentNode ( node, goalPoint ); 196 } 197 198 public Iterator getAdjacentNodes ( Object node ) 199 ////////////////////////////////////////////////////////////////////// 200 { 201 Point nodePoint = ( Point ) node; 202 203 int x = nodePoint.x; 204 205 int y = nodePoint.y; 206 207 List list = new ArrayList ( ); 208 209 if ( nodePoint.equals ( jumpPoint ) ) 210 { 211 list.add ( goalPoint ); 212 213 return list.iterator ( ); 214 } 215 216 for ( int offsetX = -1; offsetX < 2; offsetX++ ) 217 { 218 for ( int offsetY = -1; offsetY < 2; offsetY++ ) 219 { 220 if ( ( offsetX == 0 ) 221 && ( offsetY == 0 ) ) 222 { 223 continue; 224 } 225 226 int newX = x + offsetX; 227 228 int newY = y + offsetY; 229 230 if ( ( newX < MIN_X ) 231 || ( newY < MIN_Y ) 232 || ( newX > MAX_X ) 233 || ( newY > MAX_Y ) ) 234 { 235 continue; 236 } 237 238 Point point = new Point ( newX, newY ); 239 240 if ( !blockedSet.contains ( point ) ) 241 { 242 list.add ( point ); 243 } 244 } 245 } 246 247 return list.iterator ( ); 248 } 249 250 public double getCostToAdjacentNode ( 251 Object fromNode, 252 Object toNode ) 253 ////////////////////////////////////////////////////////////////////// 254 { 255 if ( fromNode.equals ( jumpPoint ) ) 256 { 257 return 0.0; 258 } 259 260 return ( ( Point ) fromNode ).distance ( ( Point ) toNode ); 261 } 262 263 public boolean isGoalNode ( Object node ) 264 ////////////////////////////////////////////////////////////////////// 265 { 266 return ( ( Point ) node ).equals ( goalPoint ); 267 } 268 269 ////////////////////////////////////////////////////////////////////// 270 ////////////////////////////////////////////////////////////////////// 271 }