| | | 1 | | using Godot; |
| | | 2 | | |
| | | 3 | | |
| | | 4 | | namespace Safarimacik.Model; |
| | | 5 | | |
| | | 6 | | |
| | | 7 | | /// <summary> |
| | | 8 | | /// Represents a board in the game. |
| | | 9 | | /// </summary> |
| | | 10 | | /// A 2D grid of tiles, where each tile can be a different type of terrain. Map generation is done when the board is cre |
| | | 11 | | public class Board { |
| | | 12 | | private Tile[,] _board; |
| | | 13 | | private IRandomGenerator _rng; |
| | | 14 | | |
| | 1 | 15 | | public Tile this[int x, int y] { get { return _board[x, y]; } } |
| | | 16 | | |
| | | 17 | | /// <summary> |
| | | 18 | | /// Creates a new board with the X and Y dimensions. |
| | | 19 | | /// </summary> |
| | | 20 | | /// <param name="x">X (horizontal) size of the board.</param> |
| | | 21 | | /// <param name="y">Y (vertical) size of the board.</param> |
| | | 22 | | /// <exception cref="ArgumentOutOfRangeException">The X and Y parameters must be positive.</exception> |
| | | 23 | | /// <exception cref="ArgumentException">The X and Y parameters bust be in a 16, and 9 ratio respectively.</exception> |
| | | 24 | | /// <remarks> |
| | | 25 | | /// The board is generated using Perlin noise to create a natural-looking terrain. The following invariants are used: |
| | | 26 | | /// - The leftmost tile is a Gateway tile with the direction set to false. |
| | | 27 | | /// - The rightmost tile is a Gateway tile with the direction set to true. |
| | | 28 | | /// - The Gateways are connected by a path of Grass tiles, so the player can connect them with a road. |
| | | 29 | | /// - If the board is large enough, at least one river is generated. |
| | | 30 | | /// </remarks> |
| | 1 | 31 | | public Board(int x, int y) : this(x, y, new RandomGenerator()) { } |
| | | 32 | | |
| | | 33 | | /// <summary> |
| | | 34 | | /// Creates a new board with the X and Y dimensions. |
| | | 35 | | /// </summary> |
| | | 36 | | /// <param name="x">X (horizontal) size of the board.</param> |
| | | 37 | | /// <param name="y">Y (vertical) size of the board.</param> |
| | | 38 | | /// <exception cref="ArgumentOutOfRangeException">The X and Y parameters must be positive.</exception> |
| | | 39 | | /// <exception cref="ArgumentException">The X and Y parameters bust be in a 16, and 9 ratio respectively.</exception> |
| | | 40 | | /// <remarks> |
| | | 41 | | /// The board is generated using Perlin noise to create a natural-looking terrain. The following invariants are used: |
| | | 42 | | /// - The leftmost tile is a Gateway tile with the direction set to false. |
| | | 43 | | /// - The rightmost tile is a Gateway tile with the direction set to true. |
| | | 44 | | /// - The Gateways are connected by a path of Grass tiles, so the player can connect them with a road. |
| | | 45 | | /// - If the board is large enough, at least one river is generated. |
| | | 46 | | /// </remarks> |
| | 1 | 47 | | public Board(int x, int y, IRandomGenerator random) { |
| | 1 | 48 | | if (x <= 0) throw new ArgumentOutOfRangeException(nameof(x), x, "Board sizes must be positive!"); |
| | 1 | 49 | | if (y <= 0) throw new ArgumentOutOfRangeException(nameof(y), y, "Board sizes must be positive!"); |
| | 1 | 50 | | if ((float)x / y != 16f / 9) { |
| | 1 | 51 | | throw new ArgumentException("Board size ratio has to be 16:9!"); |
| | | 52 | | } |
| | 1 | 53 | | _rng = random; |
| | | 54 | | |
| | 1 | 55 | | int maxGenIterations = 20; |
| | 1 | 56 | | do { |
| | 1 | 57 | | maxGenIterations--; |
| | 1 | 58 | | if (maxGenIterations <= 0) { |
| | 0 | 59 | | throw new Exception("Failed to generate a board with a path between the Gateways!"); |
| | | 60 | | } |
| | | 61 | | |
| | 1 | 62 | | _board = new Tile[x, y]; |
| | | 63 | | |
| | 1 | 64 | | FastNoiseLite waterNoise = new() { |
| | 1 | 65 | | NoiseType = FastNoiseLite.NoiseTypeEnum.Perlin, |
| | 1 | 66 | | Frequency = 0.05f, |
| | 1 | 67 | | Seed = _rng.RandI(0, 1000), |
| | 1 | 68 | | FractalType = FastNoiseLite.FractalTypeEnum.Fbm, |
| | 1 | 69 | | FractalOctaves = 2, |
| | 1 | 70 | | FractalLacunarity = 2.0f, |
| | 1 | 71 | | FractalGain = 0, |
| | 1 | 72 | | }; |
| | | 73 | | |
| | 1 | 74 | | FastNoiseLite hillNoise = new() { |
| | 1 | 75 | | NoiseType = FastNoiseLite.NoiseTypeEnum.Perlin, |
| | 1 | 76 | | Frequency = 0.09f, |
| | 1 | 77 | | Seed = _rng.RandI(0, 1000), |
| | 1 | 78 | | FractalType = FastNoiseLite.FractalTypeEnum.Fbm, |
| | 1 | 79 | | FractalOctaves = 2, |
| | 1 | 80 | | FractalLacunarity = 1.0f, |
| | 1 | 81 | | FractalGain = 0, |
| | 1 | 82 | | }; |
| | | 83 | | |
| | | 84 | | // Define thresholds for different terrain types. A larger threshold makes the tiles rarer. |
| | 1 | 85 | | float waterThreshold = 0.55f; |
| | 1 | 86 | | float hillThreshold = 0.62f; |
| | | 87 | | |
| | 1 | 88 | | for (int i = 0; i < x; i++) { |
| | 1 | 89 | | for (int j = 0; j < y; j++) { |
| | 1 | 90 | | float waterNoiseValue = waterNoise.GetNoise2D(i, j); |
| | 1 | 91 | | float hillNoiseValue = hillNoise.GetNoise2D(i, j); |
| | | 92 | | |
| | | 93 | | // If the water noise value is above the water threshold, create a Water tile. |
| | 1 | 94 | | if (waterNoiseValue > waterThreshold) { |
| | 1 | 95 | | _board[i, j] = new Water(); |
| | 1 | 96 | | } else if (hillNoiseValue > hillThreshold) { |
| | | 97 | | // If the hill noise value is above the hill threshold, first check if the tile is near water. |
| | 1 | 98 | | bool isNearWater = false; |
| | 1 | 99 | | for (int nx = i - 1; nx <= i + 1; nx++) { |
| | 1 | 100 | | for (int ny = j - 1; ny <= j + 1; ny++) { |
| | 1 | 101 | | if (nx >= 0 && nx < x && ny >= 0 && ny < y && _board[nx, ny] is Water) { |
| | 1 | 102 | | isNearWater = true; |
| | 1 | 103 | | break; |
| | | 104 | | } |
| | 1 | 105 | | } |
| | 1 | 106 | | if (isNearWater) break; |
| | 1 | 107 | | } |
| | | 108 | | // If the tile is not near water, create a Hill tile. |
| | 1 | 109 | | if (!isNearWater) _board[i, j] = new Hill(); |
| | 1 | 110 | | } |
| | | 111 | | // If no tile has been placed in this location, create a Grass tile. |
| | 1 | 112 | | if (_board[i, j] == null) { |
| | 1 | 113 | | _board[i, j] = new Grass(); |
| | 1 | 114 | | } |
| | 1 | 115 | | } |
| | 1 | 116 | | } |
| | | 117 | | |
| | | 118 | | // Create 1-4 rivers |
| | 1 | 119 | | for (int n = 0; n < _rng.RandI(1, 4); n++) { |
| | 1 | 120 | | int startX = 0, startY = 0, endX = 0, endY = 0, maxIter = 10; |
| | | 121 | | // Find a random starting point for the river, that is not on a water tile. |
| | 1 | 122 | | do { |
| | 1 | 123 | | maxIter--; |
| | 1 | 124 | | if (maxIter <= 0) break; |
| | 1 | 125 | | startX = _rng.RandI(2, x - 3); |
| | 1 | 126 | | startY = _rng.RandI(2, y - 3); |
| | 1 | 127 | | } while (_board[startX, startY].GetType() == typeof(Water)); |
| | 1 | 128 | | if (maxIter <= 0) continue; |
| | 1 | 129 | | maxIter = 10; |
| | | 130 | | |
| | | 131 | | // Find a random ending point for the river, that is not on a water tile and is at least 10 tiles away, but no f |
| | 1 | 132 | | do { |
| | 1 | 133 | | maxIter--; |
| | 1 | 134 | | if (maxIter <= 0) break; |
| | 1 | 135 | | endX = _rng.RandI(2, x - 3); |
| | 1 | 136 | | endY = _rng.RandI(2, y - 3); |
| | 1 | 137 | | } while (Math.Abs(startX - endX) < 10 || Math.Abs(startY - endY) < 10 || _board[endX, endY].GetType() == typeof( |
| | 1 | 138 | | if (maxIter <= 0) continue; |
| | | 139 | | |
| | | 140 | | // Find a path between the starting and ending points, but only through Grass tiles. Place Water tiles along the |
| | 1 | 141 | | var river = FindPath(new Vector2I(startX, startY), new Vector2I(endX, endY), false, typeof(Grass)); |
| | 1 | 142 | | if (river.Count > 0) { |
| | 1 | 143 | | for (int i = 1; i < river.Count - 1; i++) { |
| | 1 | 144 | | _board[river[i].X, river[i].Y] = new Water(); |
| | 1 | 145 | | } |
| | 1 | 146 | | } |
| | 1 | 147 | | } |
| | | 148 | | |
| | 1 | 149 | | _board[0, y / 2] = new Gateway(false); |
| | 1 | 150 | | _board[x - 1, y / 2] = new Gateway(true); |
| | 1 | 151 | | } while ( |
| | 1 | 152 | | // If no path is found between the Gateways, try the generation again. |
| | 1 | 153 | | FindPath(new Vector2I(0, y / 2), new Vector2I(x - 1, y / 2), false, typeof(Grass), typeof(Gateway)).Count == 0 |
| | 1 | 154 | | ); |
| | 1 | 155 | | } |
| | | 156 | | |
| | 1 | 157 | | public int GetLength(int dimension) { |
| | 1 | 158 | | return _board.GetLength(dimension); |
| | 1 | 159 | | } |
| | | 160 | | |
| | | 161 | | /// <summary> |
| | | 162 | | /// Changes a tile on the board at the given coordinates. |
| | | 163 | | /// </summary> |
| | | 164 | | /// <param name="x">X (horizontal) coordinate of the tile.</param> |
| | | 165 | | /// <param name="y">Y (horizontal) coordinate of the tile.</param> |
| | | 166 | | /// <param name="newTile">Tile to replace the old one with.</param> |
| | | 167 | | /// <exception cref="ArgumentOutOfRangeException">The X and Y parameters must be within the board's dimensions.</excep |
| | 1 | 168 | | public void ChangeTile(int x, int y, Tile newTile) { |
| | 1 | 169 | | if (x < 0 || x >= _board.GetLength(0)) { |
| | 1 | 170 | | throw new ArgumentOutOfRangeException(nameof(x), x, "Must be between 0 and horizontal size - 1!"); |
| | | 171 | | } |
| | 1 | 172 | | if (y < 0 || y >= _board.GetLength(1)) { |
| | 1 | 173 | | throw new ArgumentOutOfRangeException(nameof(y), y, "Must be between 0 and vertical size - 1!"); |
| | | 174 | | } |
| | 1 | 175 | | _board[x, y] = newTile; |
| | 1 | 176 | | } |
| | | 177 | | |
| | | 178 | | /// <summary> |
| | | 179 | | /// Finds a path between two points on the board using the A* algorithm. |
| | | 180 | | /// </summary> |
| | | 181 | | /// <param name="start">The coordinates of the point where we start the pathfinding.</param> |
| | | 182 | | /// <param name="end">The destination coordinates where we want a route.</param> |
| | | 183 | | /// <param name="weighted">Whether the pathfinding should take into account the travel speed of the different tiles. A |
| | | 184 | | /// <param name="tileTypes">The whitelisted tiles that we can use to pathfind. All tiles are allowed if this parameter |
| | | 185 | | /// <returns>A list of the coordinates on the grid used to get to the destination, where first element is the start po |
| | | 186 | | /// <exception cref="ArgumentOutOfRangeException">The start and end coordinates must be within the board's dimensions. |
| | 1 | 187 | | public List<Vector2I> FindPath(Vector2I start, Vector2I end, bool weighted, params Type[] tileTypes) { |
| | 1 | 188 | | if (start.X < 0 || start.Y < 0 || start.X >= _board.GetLength(0) || start.Y >= _board.GetLength(1)) { |
| | 0 | 189 | | throw new ArgumentOutOfRangeException(nameof(start), start, "Start coordinates must be within the board's dimensio |
| | | 190 | | } |
| | 1 | 191 | | if (end.X < 0 || end.Y < 0 || end.X >= _board.GetLength(0) || end.Y >= _board.GetLength(1)) { |
| | 0 | 192 | | throw new ArgumentOutOfRangeException(nameof(end), end, "End coordinates must be within the board's dimensions!"); |
| | | 193 | | } |
| | 1 | 194 | | if (start == end) return [start]; |
| | | 195 | | |
| | 1 | 196 | | AStarGrid2D astarGrid = new() { |
| | 1 | 197 | | Region = new Rect2I(0, 0, _board.GetLength(0), _board.GetLength(1)), |
| | 1 | 198 | | DiagonalMode = weighted ? AStarGrid2D.DiagonalModeEnum.Always : AStarGrid2D.DiagonalModeEnum.Never, |
| | 1 | 199 | | }; |
| | 1 | 200 | | astarGrid.Update(); |
| | | 201 | | |
| | 1 | 202 | | for (int i = 0; i < _board.GetLength(0); i++) { |
| | 1 | 203 | | for (int j = 0; j < _board.GetLength(1); j++) { |
| | 1 | 204 | | if (tileTypes.Length > 0 && !tileTypes.Contains(_board[i, j].GetType())) { |
| | 1 | 205 | | astarGrid.SetPointSolid(new Vector2I(i, j), true); |
| | 1 | 206 | | } |
| | 1 | 207 | | if (weighted) { |
| | 1 | 208 | | astarGrid.SetPointWeightScale(new Vector2I(i, j), 1 / _board[i, j].Speed); |
| | 1 | 209 | | } |
| | 1 | 210 | | } |
| | 1 | 211 | | } |
| | | 212 | | |
| | 1 | 213 | | List<Vector2I> path = [.. astarGrid.GetIdPath(start, end)]; |
| | 1 | 214 | | return path; |
| | 1 | 215 | | } |
| | | 216 | | |
| | | 217 | | /// <summary> |
| | | 218 | | /// Finds a path between two points on the board using the FindPath method, used for animal pathfinding. |
| | | 219 | | /// </summary> |
| | | 220 | | /// <param name="start">The coordinates of the point where we start the pathfinding.</param> |
| | | 221 | | /// <param name="end">The destination coordinates where we want a route.</param> |
| | | 222 | | /// <param name="weighted">Whether the pathfinding should take into account the travel speed of the different tiles. A |
| | | 223 | | /// <returns></returns> |
| | 1 | 224 | | public List<Vector2> FindPathR(Vector2I start, Vector2I end, bool weighted) { |
| | 1 | 225 | | List<Vector2I> path = FindPath(start, end, weighted, typeof(Grass), typeof(Road), typeof(Hill), typeof(Water)); |
| | 1 | 226 | | List<Vector2> ret = []; |
| | | 227 | | Vector2 updated; |
| | | 228 | | |
| | | 229 | | |
| | 1 | 230 | | for (int i = 0; i < path.Count; i++) { |
| | 1 | 231 | | updated = path[i] * 16 + new Vector2(_rng.Rand(0, 15), _rng.Rand(0, 15)); |
| | 1 | 232 | | ret.Add(updated.Clamp(new Vector2(0, 0), new Vector2(GetLength(0) - 1, GetLength(1) - 1) * 16)); |
| | 1 | 233 | | } |
| | | 234 | | |
| | 1 | 235 | | return ret; |
| | 1 | 236 | | } |
| | | 237 | | |
| | | 238 | | /// <summary> |
| | | 239 | | /// Finds a random path of Roads from start to end using DFS algorithm. |
| | | 240 | | /// </summary> |
| | | 241 | | /// <param name="start">The entrance Gateway of the board.</param> |
| | | 242 | | /// <param name="end">The exit Gateway of the board.</param> |
| | | 243 | | /// <param name="shortest">Whether the pathfinding should return the shortest path instead of a random one.</param> |
| | | 244 | | /// <returns>A path as a List of Vector2 points or null of there was none.</returns> |
| | 1 | 245 | | public List<Vector2>? FindJeepPath(Vector2I start, Vector2I end, bool shortest = false) { |
| | 1 | 246 | | if (shortest) { |
| | 1 | 247 | | return ShortenFloat(FindPath(start, end, false, typeof(Road), typeof(Gateway))); |
| | | 248 | | } |
| | | 249 | | |
| | 1 | 250 | | Stack<List<Vector2I>> paths = new(); |
| | 1 | 251 | | HashSet<Vector2I> visited = []; |
| | | 252 | | |
| | 1 | 253 | | paths.Push([start]); |
| | 1 | 254 | | visited.Add(start); |
| | | 255 | | |
| | 1 | 256 | | while (paths.Count > 0) { |
| | 1 | 257 | | List<Vector2I> path = paths.Pop(); |
| | 1 | 258 | | Vector2I current = path.Last(); |
| | | 259 | | |
| | 1 | 260 | | if (current == end) { |
| | 1 | 261 | | return ShortenFloat(path); |
| | | 262 | | } |
| | | 263 | | |
| | 1 | 264 | | List<Vector2I> neighbours = [.. GetValidNeighbours(current).Where(n => !visited.Contains(n))]; |
| | | 265 | | |
| | 1 | 266 | | neighbours = [.. neighbours.OrderBy(_ => _rng.Rand(1, 100))]; |
| | | 267 | | |
| | 1 | 268 | | foreach (Vector2I neighbour in neighbours) { |
| | 1 | 269 | | visited.Add(neighbour); |
| | 1 | 270 | | List<Vector2I> newPath = [.. path, neighbour]; |
| | 1 | 271 | | paths.Push(newPath); |
| | 1 | 272 | | } |
| | 1 | 273 | | } |
| | 1 | 274 | | return null; |
| | 1 | 275 | | } |
| | | 276 | | |
| | | 277 | | /// <summary> |
| | | 278 | | /// Converts the points to global position from board indexes, shortens the path to leave only corner points in. |
| | | 279 | | /// </summary> |
| | | 280 | | /// <param name="origin">Original path with board indexes and middle points.</param> |
| | | 281 | | /// <returns>List of significant points of the path</returns> |
| | 1 | 282 | | private List<Vector2> ShortenFloat(List<Vector2I> origin) { |
| | 1 | 283 | | List<Vector2> shortened = [origin[0] * 16]; |
| | | 284 | | |
| | 1 | 285 | | for (int i = 1; i < origin.Count - 1; i++) { |
| | 1 | 286 | | Vector2 prev = origin[i - 1]; |
| | 1 | 287 | | Vector2 curr = origin[i]; |
| | 1 | 288 | | Vector2 next = origin[i + 1]; |
| | | 289 | | |
| | 1 | 290 | | Vector2 dir1 = prev - curr; |
| | 1 | 291 | | Vector2 dir2 = curr - next; |
| | | 292 | | |
| | 1 | 293 | | if (dir1 != dir2) { |
| | 0 | 294 | | shortened.Add(curr * 16); |
| | 0 | 295 | | } |
| | 1 | 296 | | } |
| | | 297 | | |
| | 1 | 298 | | shortened.Add(origin.Last() * 16); |
| | | 299 | | |
| | 1 | 300 | | return shortened; |
| | 1 | 301 | | } |
| | | 302 | | |
| | | 303 | | /// <summary> |
| | | 304 | | /// Finds the neighbours of a cell on the board |
| | | 305 | | /// </summary> |
| | | 306 | | /// <param name="position">Cell whose neighbours are searched</param> |
| | | 307 | | /// <returns>List of neighbouring cells</returns> |
| | 1 | 308 | | private List<Vector2I> GetValidNeighbours(Vector2I position) { |
| | 1 | 309 | | List<Vector2I> neighbours = []; |
| | 1 | 310 | | for (int i = -1; i <= 1; i += 2) { |
| | 1 | 311 | | if (position.X + i >= 0 && position.X + i < _board.GetLength(0)) { |
| | 1 | 312 | | if (_board[position.X + i, position.Y] is Road || _board[position.X + i, position.Y] is Gateway) { |
| | 1 | 313 | | neighbours.Add(new Vector2I(position.X + i, position.Y)); |
| | 1 | 314 | | } |
| | 1 | 315 | | } |
| | 1 | 316 | | if (position.Y + i >= 0 && position.Y + i < _board.GetLength(1)) { |
| | 1 | 317 | | if (_board[position.X, position.Y + i] is Road || _board[position.X, position.Y + i] is Gateway) { |
| | 0 | 318 | | neighbours.Add(new Vector2I(position.X, position.Y + i)); |
| | 0 | 319 | | } |
| | 1 | 320 | | } |
| | 1 | 321 | | } |
| | 1 | 322 | | return neighbours; |
| | 1 | 323 | | } |
| | | 324 | | } |