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="http://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 }