Dogcows Code - chaz/carfire/blob - CarFire/CarFire/CarFire/AI.cs

   1 //#define DisplayRegions
   2 #define DisplayFinalRegions
   3
   4 using System;
   5 using System.Collections.Generic;
   6 using System.Linq;
   7 using System.Text;
   8 using Microsoft.Xna.Framework;
   9
  10 namespace CarFire
  11 {
  12     /// <summary>
  13     /// AI infomation to be used by monsters. The map is split into deferent regions,
  14     /// each region is then linked to other regions that it can see.
  15     /// </summary>
  16     public class AI
  17     {
  18         Game game;
  19         int[,] regions;
  20         List<Region> regionList;
  21         int regionCnt;
  22
  23         public AI(Game _game)
  24         {
  25             game = _game;
  26             regions = new int[game.State.Map.Width, game.State.Map.Height];
  27             regionList = new List<Region>();
  28             regionCnt = 0;
  29
  30             //set all square to -1 to show they have not been assigned to a region yet.
  31             for (int y = 0; y < regions.GetLength(1); y++)
  32             {
  33                 for (int x = 0; x < regions.GetLength(0); x++)
  34                 {
  35                     regions[x, y] = -1;
  36                 }
  37             }
  38             regionList.Add(new Region(0)); //region 0 will represent all walls and things like it.
  39
  40             #if DisplayRegions
  41             printRegions();
  42             #endif
  43
  44             setUpRegions();
  45             foreach (Region r in regionList)
  46                 r.CalcCenter();
  47
  48
  49             #if (DisplayRegions || DisplayFinalRegions)
  50             printRegions();
  51             #endif
  52             linkRegions();
  53         }
  54
  55         /// <summary>
  56         /// check to see if a spot on the map is visible from another spot
  57         /// </summary>
  58         /// <param name="curX">Current X position</param>
  59         /// <param name="curY">Current Y position</param>
  60         /// <param name="testX">X location to test</param>
  61         /// <param name="testY">Y location to test</param>
  62         public bool spaceVisible(int curX, int curY, int testX, int testY)
  63         {
  64             return regionList[regions[curX, curY]].VisibleRegions.Contains(regions[testX, testY]);
  65         }
  66
  67         //find regions in map. these regions will be large groups of connected grid squares.
  68         public int setUpRegions()
  69         {
  70
  71             //find open space that has not been assigned yet
  72             for (int y = 0; y < regions.GetLength(1); y++)
  73             {
  74                 for (int x = 0; x < regions.GetLength(0); x++)
  75                 {
  76                     if (regions[x, y] == -1 && spaceOpen(x, y))
  77                     {
  78                         regionCnt++;
  79                         regionList.Add(new Region(regionCnt));
  80                         createRegion(x, y);
  81                     }
  82                     else if (regions[x, y] == -1)  //grid square is a wall
  83                     {
  84                         regions[x, y] = 0;
  85                     }
  86                     else //grid already assigned to region, do nothing
  87                     {
  88                     }
  89                 }
  90             }
  91
  92             return regionList.Count;
  93         }
  94
  95         #region Private Methods
  96         private void createRegion(int x, int y)
  97         {
  98             regionList[regionCnt].Left = x;
  99             regionList[regionCnt].Top = y;
 100
 101             for (int rY = 0; rY < 5 && y + rY < regions.GetLength(1); rY++) // creates a region as large as possible up to 5x5
 102             {
 103                 for (int rX = 0; rX < 5 && x + rX < regions.GetLength(0); rX++)
 104                 {
 105                     if (regions[x + rX, y + rY] == -1 && spaceOpen(x + rX, y + rY))
 106                     {
 107                         regions[x + rX, y + rY] = regionCnt;
 108                     }
 109                     else if (regions[x + rX, y + rY] == -1)  //grid square is a wall
 110                     {
 111                         regions[x + rX, y + rY] = 0;
 112                         regionList[regionCnt].Right = x + rX;
 113                         regionList[regionCnt].Bottom = y + rY;
 114                         #if DisplayRegions
 115                         printRegions();
 116                         #endif
 117                         if (!spaceOpen(x + rX + 1, y + rY)) // hit horizontal wall end region
 118                             if(x + rX >= regions.GetLength(0)-1)
 119                                 break;
 120                             else
 121                                 return;
 122                         else
 123                             break;
 124
 125                         //todo: figure out how to get region to stop being created when
 126                     }
 127                     else //grid already assigned to region, do nothing
 128                     {
 129                     }
 130                     regionList[regionCnt].Right = x + rX;
 131                 }
 132
 133                 regionList[regionCnt].Bottom = y + rY;
 134             }
 135             #if DisplayRegions
 136             printRegions();
 137             #endif
 138             return;
 139         }
 140         private bool spaceOpen(int x, int y)
 141         {
 142             if (x >= regions.GetLength(0)) return false;
 143             if (y >= regions.GetLength(1)) return false;
 144             return !game.State.Map.IsWall(x, y);
 145         }
 146         //TODO: scans out from each corner, some areas are still missed
 147         private void linkRegions()
 148         {
 149             foreach (Region r in regionList)
 150             {
 151                 if (r.Label == 0)
 152                     continue;
 153                 //scan from center
 154
 155                 //scan from corners
 156                 //top Left
 157                 int x = r.Left;
 158                 int y = r.Top;
 159                 //scan up
 160                 for (int t = 1; spaceOpen(x, y - t); t++)
 161                 {
 162                     if ( regions[x, y] != regions[x, y - t] )
 163                     {
 164                         regionList[regions[x, y]].AddVisible(regions[x, y - t]);
 165                     }
 166                 }
 167                 //scan left
 168                 for (int t = 1; spaceOpen(x - t, y); t++)
 169                 {
 170                     if ( regions[x, y] != regions[x - t, y] )
 171                     {
 172                         regionList[regions[x, y]].AddVisible(regions[x - t, y]);
 173                     }
 174                 }
 175                 //scan diag
 176                 for (int t = 1; spaceOpen(x - t, y - t); t++)
 177                 {
 178                     if (regions[x, y] != regions[x - t, y - t])
 179                     {
 180                         regionList[regions[x, y]].AddVisible(regions[x - t, y - t]);
 181                     }
 182                 }
 183
 184                 //top Right
 185                 x = r.Right;
 186                 y = r.Top;
 187                 //scan up
 188                 for (int t = 1; spaceOpen(x, y - t); t++)
 189                 {
 190                     if (regions[x, y] != regions[x, y - t])
 191                     {
 192                         regionList[regions[x, y]].AddVisible(regions[x, y - t]);
 193                     }
 194                 }
 195                 //scan Right
 196                 for (int t = 1; spaceOpen(x + t, y); t++)
 197                 {
 198                     if (regions[x, y] != regions[x + t, y])
 199                     {
 200                         regionList[regions[x, y]].AddVisible(regions[x + t, y]);
 201                     }
 202                 }
 203                 //scan diag
 204                 for (int t = 1; spaceOpen(x + t, y - t); t++)
 205                 {
 206                     if (regions[x, y] != regions[x + t, y - t])
 207                     {
 208                         regionList[regions[x, y]].AddVisible(regions[x + t, y - t]);
 209                     }
 210                 }
 211
 212                 //bottom Right
 213                 x = r.Right;
 214                 y = r.Bottom;
 215                 //scan down
 216                 for (int t = 1; spaceOpen(x, y + t); t++)
 217                 {
 218                     if (regions[x, y] != regions[x, y + t])
 219                     {
 220                         regionList[regions[x, y]].AddVisible(regions[x, y + t]);
 221                     }
 222                 }
 223                 //scan Right
 224                 for (int t = 1; spaceOpen(x + t, y); t++)
 225                 {
 226                     if (regions[x, y] != regions[x + t, y])
 227                     {
 228                         regionList[regions[x, y]].AddVisible(regions[x + t, y]);
 229                     }
 230                 }
 231                 //scan diag
 232                 for (int t = 1; spaceOpen(x + t, y + t); t++)
 233                 {
 234                     if (regions[x, y] != regions[x + t, y + t])
 235                     {
 236                         regionList[regions[x, y]].AddVisible(regions[x + t, y + t]);
 237                     }
 238                 }
 239
 240                 //bottom left
 241                 x = r.Left;
 242                 y = r.Bottom;
 243                 //scan down
 244                 for (int t = 1; spaceOpen(x, y + t); t++)
 245                 {
 246                     if (regions[x, y] != regions[x, y + t])
 247                     {
 248                         regionList[regions[x, y]].AddVisible(regions[x, y + t]);
 249                     }
 250                 }
 251                 //scan Left
 252                 for (int t = 1; spaceOpen(x - t, y); t++)
 253                 {
 254                     if (regions[x, y] != regions[x - t, y])
 255                     {
 256                         regionList[regions[x, y]].AddVisible(regions[x - t, y]);
 257                     }
 258                 }
 259                 //scan diag
 260                 for (int t = 1; spaceOpen(x - t, y + t); t++)
 261                 {
 262                     if (regions[x, y] != regions[x - t, y + t])
 263                     {
 264                         regionList[regions[x, y]].AddVisible(regions[x - t, y + t]);
 265                     }
 266                 }
 267             }
 268         }
 269         #endregion
 270         //for testing print the region grid to the console
 271         public void printRegions()
 272         {
 273             Console.WriteLine("--Printing Regions--");
 274             for (int y = 0; y < regions.GetLength(1); y++)
 275             {
 276                 for (int x = 0; x < regions.GetLength(0); x++)
 277                 {
 278                     Console.Write(regions[x, y]);
 279                 }
 280                 Console.WriteLine("");
 281             }
 282         }
 283     }
 284
 285     /// <summary>
 286     /// a chuck of the map that is at most 5x5 used to determine line of sight
 287     /// </summary>
 288     public class Region
 289     {
 290         List<int> visibleRegions; //other regions that are in this regions sight
 291         int label;
 292         int centerX;
 293         int centerY;
 294
 295         //edges
 296         int left, right, top, bottom;
 297
 298         public Region(int _label)
 299         {
 300             label = _label;
 301             visibleRegions = new List<int>();
 302         }
 303
 304         public void AddVisible(int region)
 305         {
 306             if(!visibleRegions.Contains(region))
 307                 visibleRegions.Add(region);
 308         }
 309
 310         public void CalcCenter()
 311         {
 312              if (right != left) centerX = right + (right - left) / 2;
 313              else centerX = right;
 314              if (top != bottom) centerY = top + (bottom - top) / 2;
 315              else centerY = top;
 316         }
 317
 318         public int Left
 319         {
 320             get { return left; }
 321             set { left = value; }
 322         }
 323         public int Right
 324         {
 325             get { return right; }
 326             set { right = value; }
 327         }
 328         public int Top
 329         {
 330             get { return top; }
 331             set { top = value; }
 332         }
 333         public int Bottom
 334         {
 335             get { return bottom; }
 336             set { bottom = value; }
 337         }
 338
 339         public Point Center { get { return new Point(centerX, centerY); } }
 340         public int Label { get { return label; } }
 341
 342         public List<int> VisibleRegions { get { return visibleRegions; } }
 343
 344
 345     }
 346 }