From 398bc41a3075cfa9c9ad5dc607a86c56a4e7e913 Mon Sep 17 00:00:00 2001 From: brady Date: Sun, 25 Apr 2010 02:29:23 +0000 Subject: [PATCH] AI initial calculations almost done, still a few small bugs. Used to determine lines of sight. git-svn-id: https://bd85.net/svn/cs3505_group@144 92bb83a3-7c8f-8a45-bc97-515c4e399668 --- CarFire/CarFire/CarFire/AI.cs | 346 ++++++++++++++++++++++++++++++++ CarFire/CarFire/CarFire/Game.cs | 4 +- 2 files changed, 349 insertions(+), 1 deletion(-) create mode 100644 CarFire/CarFire/CarFire/AI.cs diff --git a/CarFire/CarFire/CarFire/AI.cs b/CarFire/CarFire/CarFire/AI.cs new file mode 100644 index 0000000..8b8a25f --- /dev/null +++ b/CarFire/CarFire/CarFire/AI.cs @@ -0,0 +1,346 @@ +//#define DisplayRegions +#define DisplayFinalRegions + +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using Microsoft.Xna.Framework; + +namespace CarFire +{ + /// + /// AI infomation to be used by monsters. The map is split into deferent regions, + /// each region is then linked to other regions that it can see. + /// + public class AI + { + Game game; + int[,] regions; + List regionList; + int regionCnt; + + public AI(Game _game) + { + game = _game; + regions = new int[game.State.Map.Width, game.State.Map.Height]; + regionList = new List(); + regionCnt = 0; + + //set all square to -1 to show they have not been assigned to a region yet. + for (int y = 0; y < regions.GetLength(1); y++) + { + for (int x = 0; x < regions.GetLength(0); x++) + { + regions[x, y] = -1; + } + } + regionList.Add(new Region(0)); //region 0 will represent all walls and things like it. + + #if DisplayRegions + printRegions(); + #endif + + setUpRegions(); + foreach (Region r in regionList) + r.CalcCenter(); + + + #if (DisplayRegions || DisplayFinalRegions) + printRegions(); + #endif + linkRegions(); + } + + /// + /// check to see if a spot on the map is visible from another spot + /// + /// Current X position + /// Current Y position + /// X location to test + /// Y location to test + public bool spaceVisible(int curX, int curY, int testX, int testY) + { + return regionList[regions[curX, curY]].VisibleRegions.Contains(regions[testX, testY]); + } + + //find regions in map. these regions will be large groups of connected grid squares. + public int setUpRegions() + { + + //find open space that has not been assigned yet + for (int y = 0; y < regions.GetLength(1); y++) + { + for (int x = 0; x < regions.GetLength(0); x++) + { + if (regions[x, y] == -1 && spaceOpen(x, y)) + { + regionCnt++; + regionList.Add(new Region(regionCnt)); + createRegion(x, y); + } + else if (regions[x, y] == -1) //grid square is a wall + { + regions[x, y] = 0; + } + else //grid already assigned to region, do nothing + { + } + } + } + + return regionList.Count; + } + + #region Private Methods + private void createRegion(int x, int y) + { + regionList[regionCnt].Left = x; + regionList[regionCnt].Top = y; + + for (int rY = 0; rY < 5 && y + rY < regions.GetLength(1); rY++) // creates a region as large as possible up to 5x5 + { + for (int rX = 0; rX < 5 && x + rX < regions.GetLength(0); rX++) + { + if (regions[x + rX, y + rY] == -1 && spaceOpen(x + rX, y + rY)) + { + regions[x + rX, y + rY] = regionCnt; + } + else if (regions[x + rX, y + rY] == -1) //grid square is a wall + { + regions[x + rX, y + rY] = 0; + regionList[regionCnt].Right = x + rX; + regionList[regionCnt].Bottom = y + rY; + #if DisplayRegions + printRegions(); + #endif + if (!spaceOpen(x + rX + 1, y + rY)) // hit horizontal wall end region + if(x + rX >= regions.GetLength(0)-1) + break; + else + return; + else + break; + + //todo: figure out how to get region to stop being created when + } + else //grid already assigned to region, do nothing + { + } + regionList[regionCnt].Right = x + rX; + } + + regionList[regionCnt].Bottom = y + rY; + } + #if DisplayRegions + printRegions(); + #endif + return; + } + private bool spaceOpen(int x, int y) + { + if (x >= regions.GetLength(0)) return false; + if (y >= regions.GetLength(1)) return false; + return !game.State.Map.IsWall(x, y); + } + //TODO: scans out from each corner, some areas are still missed + private void linkRegions() + { + foreach (Region r in regionList) + { + if (r.Label == 0) + continue; + //scan from center + + //scan from corners + //top Left + int x = r.Left; + int y = r.Top; + //scan up + for (int t = 1; spaceOpen(x, y - t); t++) + { + if ( regions[x, y] != regions[x, y - t] ) + { + regionList[regions[x, y]].AddVisible(regions[x, y - t]); + } + } + //scan left + for (int t = 1; spaceOpen(x - t, y); t++) + { + if ( regions[x, y] != regions[x - t, y] ) + { + regionList[regions[x, y]].AddVisible(regions[x - t, y]); + } + } + //scan diag + for (int t = 1; spaceOpen(x - t, y - t); t++) + { + if (regions[x, y] != regions[x - t, y - t]) + { + regionList[regions[x, y]].AddVisible(regions[x - t, y - t]); + } + } + + //top Right + x = r.Right; + y = r.Top; + //scan up + for (int t = 1; spaceOpen(x, y - t); t++) + { + if (regions[x, y] != regions[x, y - t]) + { + regionList[regions[x, y]].AddVisible(regions[x, y - t]); + } + } + //scan Right + for (int t = 1; spaceOpen(x + t, y); t++) + { + if (regions[x, y] != regions[x + t, y]) + { + regionList[regions[x, y]].AddVisible(regions[x + t, y]); + } + } + //scan diag + for (int t = 1; spaceOpen(x + t, y - t); t++) + { + if (regions[x, y] != regions[x + t, y - t]) + { + regionList[regions[x, y]].AddVisible(regions[x + t, y - t]); + } + } + + //bottom Right + x = r.Right; + y = r.Bottom; + //scan down + for (int t = 1; spaceOpen(x, y + t); t++) + { + if (regions[x, y] != regions[x, y + t]) + { + regionList[regions[x, y]].AddVisible(regions[x, y + t]); + } + } + //scan Right + for (int t = 1; spaceOpen(x + t, y); t++) + { + if (regions[x, y] != regions[x + t, y]) + { + regionList[regions[x, y]].AddVisible(regions[x + t, y]); + } + } + //scan diag + for (int t = 1; spaceOpen(x + t, y + t); t++) + { + if (regions[x, y] != regions[x + t, y + t]) + { + regionList[regions[x, y]].AddVisible(regions[x + t, y + t]); + } + } + + //bottom left + x = r.Left; + y = r.Bottom; + //scan down + for (int t = 1; spaceOpen(x, y + t); t++) + { + if (regions[x, y] != regions[x, y + t]) + { + regionList[regions[x, y]].AddVisible(regions[x, y + t]); + } + } + //scan Left + for (int t = 1; spaceOpen(x - t, y); t++) + { + if (regions[x, y] != regions[x - t, y]) + { + regionList[regions[x, y]].AddVisible(regions[x - t, y]); + } + } + //scan diag + for (int t = 1; spaceOpen(x - t, y + t); t++) + { + if (regions[x, y] != regions[x - t, y + t]) + { + regionList[regions[x, y]].AddVisible(regions[x - t, y + t]); + } + } + } + } + #endregion + //for testing print the region grid to the console + public void printRegions() + { + Console.WriteLine("--Printing Regions--"); + for (int y = 0; y < regions.GetLength(1); y++) + { + for (int x = 0; x < regions.GetLength(0); x++) + { + Console.Write(regions[x, y]); + } + Console.WriteLine(""); + } + } + } + + /// + /// a chuck of the map that is at most 5x5 used to determine line of sight + /// + public class Region + { + List visibleRegions; //other regions that are in this regions sight + int label; + int centerX; + int centerY; + + //edges + int left, right, top, bottom; + + public Region(int _label) + { + label = _label; + visibleRegions = new List(); + } + + public void AddVisible(int region) + { + if(!visibleRegions.Contains(region)) + visibleRegions.Add(region); + } + + public void CalcCenter() + { + if (right != left) centerX = right + (right - left) / 2; + else centerX = right; + if (top != bottom) centerY = top + (bottom - top) / 2; + else centerY = top; + } + + public int Left + { + get { return left; } + set { left = value; } + } + public int Right + { + get { return right; } + set { right = value; } + } + public int Top + { + get { return top; } + set { top = value; } + } + public int Bottom + { + get { return bottom; } + set { bottom = value; } + } + + public Point Center { get { return new Point(centerX, centerY); } } + public int Label { get { return label; } } + + public List VisibleRegions { get { return visibleRegions; } } + + + } +} diff --git a/CarFire/CarFire/CarFire/Game.cs b/CarFire/CarFire/CarFire/Game.cs index c2a7aaf..f91882e 100644 --- a/CarFire/CarFire/CarFire/Game.cs +++ b/CarFire/CarFire/CarFire/Game.cs @@ -27,7 +27,7 @@ namespace CarFire public List mProjectiles = new List(); public Player[] mCharacters; public Display mDisplay; - + public AI AIData; #endregion @@ -369,6 +369,8 @@ namespace CarFire State.Map.Tilemap = tilemap; State.Entities = State.Map.GetAllEntities(this); + State.AIData = new AI(this); + /* mPlayers.Clear(); for (int i = 0; i < PlayerIdentifiers.Length; i++) -- 2.45.2