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 }