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         }