source: branches/AlphaChannel/AI Template/Project/Lib/Sprawl.cs

Last change on this file was 191, checked in by chronos, 6 years ago
  • Added: AI Template directory with manual for development of custom AI from original game.
File size: 21.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using Common;
4
5namespace CevoAILib
6{
7 struct TravelDistance
8 {
9 public static TravelDistance Invalid { get { return new TravelDistance(-1, 0, true); } }
10
11 public readonly int Turns;
12 public readonly int MovementLeft;
13 public readonly bool NewTurn;
14 // NewTurn does not correspond to Turns since Turns might already be increased for mountain delay or hostile
15 // terrain recovery although location is reached within same turn
16
17 public TravelDistance(int turns, int movementLeft, bool newTurn)
18 {
19 if (turns < 0)
20 {
21 this.Turns = -1;
22 this.MovementLeft = 0;
23 this.NewTurn = true;
24 }
25 else
26 {
27 this.Turns = turns;
28 this.MovementLeft = movementLeft;
29 this.NewTurn = newTurn;
30 }
31 }
32
33 public override string ToString()
34 {
35 return string.Format("{0}.{1}", Turns, MovementLeft);
36 }
37
38 public static bool operator <(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) < 0; }
39 public static bool operator >(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) > 0; }
40 public static bool operator ==(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) == 0; }
41 public static bool operator !=(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) != 0; }
42 public static bool operator <=(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) <= 0; }
43 public static bool operator >=(TravelDistance d1, TravelDistance d2) { return Comparison(d1, d2) >= 0; }
44 public override bool Equals(object obj) { return Comparison(this, (TravelDistance)obj) == 0; }
45 public override int GetHashCode() { return (Turns + 2) << 12 - MovementLeft; }
46
47 public static int Comparison(TravelDistance d1, TravelDistance d2)
48 {
49 return ((d1.Turns + 2) << 12) - d1.MovementLeft - ((d2.Turns + 2) << 12) + d2.MovementLeft;
50 }
51 }
52
53 class Sprawl : IEnumerable<Location>
54 {
55 protected readonly AEmpire theEmpire;
56 protected readonly int originID;
57 protected readonly int startValue;
58 protected int approachLocationID = -1;
59 protected bool approachLocationWasIterated = false;
60 protected readonly AddressPriorityQueue Q;
61 protected int currentLocationID = -1;
62 protected int currentValue = 0;
63 protected int[] neighborIDs = new int[8];
64 protected ushort[] backtrace;
65 Enumerator enumerator = null;
66
67 public Sprawl(AEmpire empire, Location origin, int startValue)
68 {
69 this.theEmpire = empire;
70 this.originID = origin.ID;
71 this.startValue = startValue;
72 Q = new AddressPriorityQueue(empire.Map.Size - 1);
73 backtrace = new ushort[empire.Map.Size];
74 }
75
76 public bool WasIterated(Location location)
77 {
78 if (location.ID == approachLocationID)
79 return approachLocationWasIterated;
80 else
81 {
82 int distance = Q.Distance(location.ID);
83 return (distance != AddressPriorityQueue.Unknown && distance != AddressPriorityQueue.Disallowed);
84 }
85 }
86
87 public Location[] Path(Location location)
88 {
89 if (WasIterated(location))
90 {
91 int stepCount = 0;
92 ushort locationID = (ushort)location.ID;
93 if (locationID == approachLocationID)
94 locationID = backtrace[locationID];
95 while (locationID != originID)
96 {
97 stepCount++;
98 locationID = backtrace[locationID];
99 }
100 Location[] result = new Location[stepCount];
101 locationID = (ushort)location.ID;
102 if (locationID == approachLocationID)
103 locationID = backtrace[locationID];
104 while (locationID != originID)
105 {
106 stepCount--;
107 result[stepCount] = new Location(theEmpire, locationID);
108 locationID = backtrace[locationID];
109 }
110 return result;
111 }
112 else
113 return null; // not reached yet
114 }
115
116 protected enum StepValidity { OK, ForbiddenStep, ForbiddenLocation }
117
118 protected virtual StepValidity Step(int fromLocationId, int toLocationId, int distance, int fromValue, ref int toValue)
119 {
120 toValue = fromValue + distance;
121 return StepValidity.OK;
122 }
123
124 protected virtual bool MoveNext()
125 {
126 bool approached = false;
127 if (currentLocationID >= 0 && currentLocationID != approachLocationID)
128 { // first check to reach neighbors from last iterated location
129 theEmpire.Map.GetNeighborIDs(currentLocationID, neighborIDs);
130 for (int V8 = 0; V8 < 8; V8++)
131 {
132 int nextLocationID = neighborIDs[V8];
133 if (nextLocationID >= 0)
134 {
135 if (nextLocationID == approachLocationID && !approachLocationWasIterated)
136 {
137 backtrace[nextLocationID] = (ushort)currentLocationID;
138 approached = true;
139 }
140 else if (Q.Distance(nextLocationID) == AddressPriorityQueue.Unknown)
141 {
142 int nextValue = 0;
143 switch (Step(currentLocationID, nextLocationID, 2 + (V8 & 1), currentValue, ref nextValue))
144 {
145 case StepValidity.OK:
146 {
147 if (Q.Offer(nextLocationID, nextValue))
148 backtrace[nextLocationID] = (ushort)currentLocationID;
149 break;
150 }
151 case StepValidity.ForbiddenStep: break; // just don't offer
152 case StepValidity.ForbiddenLocation: Q.Disallow(nextLocationID); break; // don't try to reach from every direction again
153 }
154 }
155 }
156 }
157 }
158
159 if (approached)
160 {
161 currentLocationID = approachLocationID;
162 approachLocationWasIterated = true;
163 return true;
164 }
165 else
166 return Q.TakeClosest(out currentLocationID, out currentValue);
167 }
168
169 void EnumerationEnded()
170 {
171 if (enumerator == null)
172 throw new Exception("Error in Sprawl: Only started foreach loop can end!");
173 enumerator.DisposeEvent -= EnumerationEnded;
174 enumerator = null;
175 }
176
177 #region IEnumerable members
178 class Enumerator : IEnumerator<Location>
179 {
180 Sprawl parent;
181 public Enumerator(Sprawl parent) { this.parent = parent; }
182 public delegate void DisposeEventHandler();
183 public event DisposeEventHandler DisposeEvent;
184 public void Reset() { throw new NotSupportedException(); }
185 public bool MoveNext() { return parent.MoveNext(); }
186 public void Dispose() { DisposeEvent(); }
187 public Location Current { get { return new Location(parent.theEmpire, parent.currentLocationID); } }
188 object System.Collections.IEnumerator.Current { get { return Current; } }
189 }
190
191 public IEnumerator<Location> GetEnumerator()
192 {
193 if (enumerator != null)
194 throw new Exception("Sprawl: Nested iteration is not supported!");
195 Q.Clear();
196 Q.Offer(originID, startValue);
197 currentLocationID = -1;
198 approachLocationWasIterated = false;
199 enumerator = new Enumerator(this);
200 enumerator.DisposeEvent += EnumerationEnded;
201 return enumerator;
202 }
203 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
204 #endregion
205 }
206
207 /// <summary>
208 /// A formation iterator, where the formation might be an island, waters or coherent tiles of the Shore terrain type only.
209 /// Tiles not discovered yet always count as end of formation and are never iterated.
210 /// </summary>
211 class RestrictedSprawl : Sprawl
212 {
213 public enum TerrainGroup { AllLand, AllWater, Shore }
214
215 TerrainGroup restriction;
216
217 public RestrictedSprawl(AEmpire empire, Location origin, TerrainGroup restriction)
218 : base(empire, origin, 0)
219 {
220 this.restriction = restriction;
221 }
222
223 public int Distance(Location location)
224 {
225 int distance = Q.Distance(location.ID);
226 if (distance != AddressPriorityQueue.Unknown && distance != AddressPriorityQueue.Disallowed)
227 return distance;
228 else
229 return -1; // not reached yet
230 }
231
232 protected override StepValidity Step(int fromLocationId, int toLocationId, int distance, int fromValue, ref int toValue)
233 {
234 Location toLocation = new Location(theEmpire, toLocationId);
235 toValue = fromValue + distance;
236 switch (restriction)
237 {
238 default: // TerrainGroup.AllLand:
239 if (toLocation.IsDiscovered && !toLocation.IsWater)
240 return StepValidity.OK;
241 else
242 return StepValidity.ForbiddenLocation;
243
244 case TerrainGroup.AllWater:
245 if (toLocation.IsDiscovered && toLocation.IsWater)
246 return StepValidity.OK;
247 else
248 return StepValidity.ForbiddenLocation;
249
250 case TerrainGroup.Shore:
251 if (toLocation.BaseTerrain == Terrain.Shore)
252 return StepValidity.OK;
253 else
254 return StepValidity.ForbiddenLocation;
255 }
256 }
257 }
258
259 /// <summary>
260 /// A unit movement iterator.
261 /// </summary>
262 class TravelSprawl : Sprawl
263 {
264 static readonly MovementKind[] rawTerrainMovementKind =
265 {
266 MovementKind.Plain, //Ocn
267 MovementKind.Plain, //Sho
268 MovementKind.Plain, //Gra
269 MovementKind.Plain, //Dst
270 MovementKind.Plain, //Pra
271 MovementKind.Plain, //Tun
272 MovementKind.Difficult, //Arc
273 MovementKind.Difficult, //Swa
274 MovementKind.Difficult, //-
275 MovementKind.Difficult, //For
276 MovementKind.Difficult, //Hil
277 MovementKind.Mountains //Mou
278 };
279
280 [Flags]
281 public enum Options
282 {
283 None = 0x00, IgnoreBlocking = 0x001, IgnoreZoC = 0x002, IgnoreTreaty = 0x004, EmptyPlanet = 0x007,
284 ZeroCostRailroad = 0x010, TerrainResistant = 0x020, Overweight = 0x040, Alpine = 0x080, Navigation = 0x100
285 }
286
287 const int NewTurn = 0x1;
288
289 protected ModelDomain domain;
290 protected int speed;
291 protected Options options;
292 protected int baseDifficultMoveCost;
293 protected int baseRailroadMoveCost;
294
295 /// <summary>
296 /// Create general unit movement iterator for an existing or hypothetical unit.
297 /// </summary>
298 /// <param name="empire">empire</param>
299 /// <param name="nation">nation of the unit</param>
300 /// <param name="origin">initial unit location</param>
301 /// <param name="domain">unit domain</param>
302 /// <param name="unitSpeed">speed of the unit</param>
303 /// <param name="initialMovementLeft">initial movement points left</param>
304 /// <param name="options">options</param>
305 public TravelSprawl(AEmpire empire, Nation nation, Location origin, ModelDomain domain, int unitSpeed, int initialMovementLeft, Options options)
306 : base(empire, origin, unitSpeed - initialMovementLeft)
307 {
308 this.domain = domain;
309 this.speed = unitSpeed;
310 this.options = options;
311 if (nation != empire.Us)
312 options |= Options.EmptyPlanet; // default location info relates to own nation, so it can't be considered then
313 if (nation.HasWonder(Building.ShinkansenExpress))
314 options |= Options.ZeroCostRailroad;
315 if (nation.HasWonder(Building.HangingGardens))
316 options |= Options.TerrainResistant;
317 baseDifficultMoveCost = 100 + (unitSpeed - 150) / 5;
318 if ((options & Options.ZeroCostRailroad) != 0)
319 baseRailroadMoveCost = 0;
320 else
321 baseRailroadMoveCost = (unitSpeed / 50) * 4;
322 }
323
324 /// <summary>
325 /// Unit movement iterator for an own unit.
326 /// </summary>
327 /// <param name="empire">empire</param>
328 /// <param name="unit">the unit</param>
329 public TravelSprawl(AEmpire empire, AUnit unit)
330 : this(empire, unit.Nation, unit.Location, unit.Model.Domain, unit.Speed, unit.MovementLeft, Options.None)
331 {
332 SetOptionsFromUnit(unit);
333 }
334
335 /// <summary>
336 /// Special unit movement iterator when the goal is to move an own unit adjacent to a certain location.
337 /// </summary>
338 /// <param name="empire">empire</param>
339 /// <param name="unit">the unit</param>
340 /// <param name="approachLocation">loaction to approach to</param>
341 public TravelSprawl(AEmpire empire, AUnit unit, Location approachLocation)
342 : this(empire, unit)
343 {
344 approachLocationID = approachLocation.ID;
345 if (unit.Location != approachLocation)
346 Q.Disallow(approachLocationID);
347 }
348
349 /// <summary>
350 /// Unit movement iterator for a foreign unit.
351 /// </summary>
352 /// <param name="empire">empire</param>
353 /// <param name="unit">the unit</param>
354 public TravelSprawl(AEmpire empire, ForeignUnit unit)
355 : this(empire, unit.Nation, unit.Location, unit.Model.Domain, unit.Speed, unit.Speed, Options.None)
356 {
357 SetOptionsFromUnit(unit);
358 }
359
360 public TravelDistance Distance(Location location)
361 {
362 int distance = 0;
363 if (location.ID == approachLocationID)
364 {
365 if (!approachLocationWasIterated)
366 return TravelDistance.Invalid; // not reached yet
367
368 distance = Q.Distance(backtrace[approachLocationID]);
369 }
370 else
371 distance = Q.Distance(location.ID);
372 if (distance != AddressPriorityQueue.Unknown && distance != AddressPriorityQueue.Disallowed)
373 return new TravelDistance(distance >> 12, speed - ((distance >> 1) & 0x7FF), (distance & NewTurn) != 0);
374 else
375 return TravelDistance.Invalid; // not reached yet
376 }
377
378 /// <summary>
379 /// damage the unit would receive from hostile terrain travelling to a location before it reaches an intermediate non-hostile terrain location
380 /// </summary>
381 /// <param name="location">the location to travel to</param>
382 /// <returns>the damage</returns>
383 public int DamageToNextNonHostileLocation(Location fromLocation, Location toLocation)
384 {
385 if ((options & Options.TerrainResistant) == 0 && WasIterated(toLocation))
386 {
387 int damage = 0;
388 ushort locationID = (ushort)toLocation.ID;
389 if (locationID == approachLocationID)
390 locationID = backtrace[locationID];
391 int sourceTerrainDamage = 0;
392 int sourceDistance = 0;
393 int destinationTerrainDamage = new Location(theEmpire, locationID).OneTurnHostileDamage;
394 int destinationDistance = Q.Distance(locationID);
395 while (locationID != fromLocation.ID)
396 {
397 locationID = backtrace[locationID];
398 sourceTerrainDamage = new Location(theEmpire, locationID).OneTurnHostileDamage;
399 sourceDistance = Q.Distance(locationID);
400 if (locationID != fromLocation.ID && sourceTerrainDamage == 0)
401 damage = 0;
402 else if ((destinationDistance & NewTurn) != 0)
403 { // move has to wait for next turn
404 if (sourceTerrainDamage > 0 &&
405 ((sourceDistance >> 1) & 0x7FF) < speed) // movement left
406 damage += (sourceTerrainDamage * (speed - ((sourceDistance >> 1) & 0x7FF)) - 1) / speed + 1; // unit spends rest of turn here
407 if (destinationTerrainDamage > 0)
408 damage += (destinationTerrainDamage * ((destinationDistance >> 1) & 0x7FF) - 1) / speed + 1; // move
409 }
410 else
411 {
412 if (destinationTerrainDamage > 0)
413 damage += (destinationTerrainDamage * (((destinationDistance >> 1) & 0x7FF) - ((sourceDistance >> 1) & 0x7FF)) - 1) / speed + 1; // move
414 }
415 destinationTerrainDamage = sourceTerrainDamage;
416 destinationDistance = sourceDistance;
417 }
418 return damage;
419 }
420 else
421 return 0;
422 }
423
424 void SetOptionsFromUnit(IUnitInfo unit)
425 {
426 if (unit.Model.Domain != ModelDomain.Ground || unit.Model.Kind == ModelKind.SpecialCommando)
427 options |= Options.IgnoreZoC;
428 if (unit.Model.Kind == ModelKind.SpecialCommando)
429 options |= Options.IgnoreTreaty;
430 if (domain != ModelDomain.Ground || unit.IsTerrainResistant)
431 options |= Options.TerrainResistant;
432 if (unit.Model.HasFeature(ModelProperty.Overweight))
433 options |= Options.Overweight;
434 if (unit.Model.HasFeature(ModelProperty.Alpine))
435 options |= Options.Alpine;
436 if (unit.Model.HasFeature(ModelProperty.Navigation))
437 options |= Options.Navigation;
438 }
439
440 unsafe protected override StepValidity Step(int fromLocationID, int toLocationID, int distance, int fromValue, ref int toValue)
441 {
442 switch (domain)
443 {
444 default: // case ModelDomain.Ground
445 {
446 int fromTile = theEmpire.Map.Ground[fromLocationID];
447 int toTile = theEmpire.Map.Ground[toLocationID];
448 int moveCost = 100;
449
450 if ((toTile & 0x1F) == 0x1F)
451 return StepValidity.ForbiddenLocation; // not discovered
452
453 if ((toTile & 0x600000) == 0x400000 && (options & Options.IgnoreBlocking) == 0)
454 return StepValidity.ForbiddenLocation; // foreign unit
455
456 if ((toTile & 0x1E) == 0x00)
457 return StepValidity.ForbiddenLocation; // water
458
459 if ((toTile & 0x40000000) != 0 && (options & Options.IgnoreTreaty) == 0)
460 {
461 if ((fromTile & 0x40000000) == 0 ||
462 new Location(theEmpire, fromLocationID).TerritoryNation != new Location(theEmpire, toLocationID).TerritoryNation)
463 return StepValidity.ForbiddenStep; // treaty
464 }
465
466 if ((options & Options.IgnoreZoC) == 0 &&
467 (fromTile & 0x800000) == 0 && // not coming out of city
468 (toTile & 0xA00000) != 0xA00000 && // not moving into own city
469 (fromTile & 0x20000000) != 0 && // fromLocation in ZoC
470 (toTile & 0x30000000) == 0x20000000) // toLocation in ZoC
471 return StepValidity.ForbiddenStep; // ZoC violation
472
473 if ((fromTile & 0x800200) != 0 && (toTile & 0x800200) != 0) // both locations have railroad or city
474 moveCost = baseRailroadMoveCost;
475 else if ((options & Options.Alpine) != 0 ||
476 ((fromTile & 0x800300) != 0 && (toTile & 0x800300) != 0) || // both locations have road, railroad or city
477 (fromTile & toTile & 0x480) != 0) // both locations have river or both locations have canal
478 {
479 if ((options & Options.Overweight) != 0)
480 moveCost = 80;
481 else
482 moveCost = 40;
483 }
484 else
485 {
486 if ((options & Options.Overweight) != 0)
487 return StepValidity.ForbiddenStep;
488
489 switch (rawTerrainMovementKind[toTile & 0xF])
490 {
491 case MovementKind.Plain: { moveCost = 100; break; }
492 case MovementKind.Difficult: { moveCost = baseDifficultMoveCost; break; }
493
494 case MovementKind.Mountains:
495 {
496 if (((fromValue >> 1) & 0x7FF) == 0) // only possible in first step
497 toValue = (fromValue & 0x7FFFF000) + 0x1000 + (speed << 1);
498 else
499 {
500 toValue = ((fromValue & 0x7FFFF000) + 0x2000 + (speed << 1)) | NewTurn; // must wait for next turn
501 if ((options & Options.TerrainResistant) == 0
502 && ((fromValue >> 1) & 0x7FF) < speed // movement left
503 && (fromTile & 0x800480) == 0 // no city, river or canal
504 && (fromTile & 0xF000) != 0x5000 // no base
505 && ((fromTile & 0x1F) == 0x06 || (fromTile & 0x3F) == 0x03)) // arctic or desert but not an oasis
506 { // add recovery turns for waiting on hostile terrain
507 int waitDamage = (Cevo.DamagePerTurnInDesert * (speed - ((fromValue >> 1) & 0x7FF)) - 1) / speed + 1;
508 toValue += ((waitDamage + 4) >> 3) << 12; // actually: toValue += Math.Round(waitDamage / Cevo.RecoveryOutsideCity) << 12
509 }
510 }
511 return StepValidity.OK;
512 }
513 }
514 }
515 if (distance == 3)
516 moveCost += moveCost >> 1;
517 int damageMovement = 0;
518 if ((options & Options.TerrainResistant) == 0
519 && (toTile & 0x800480) == 0 // no city, river or canal
520 && (toTile & 0xF000) != 0x5000 // no base
521 && ((toTile & 0x1F) == 0x06 || (toTile & 0x3F) == 0x03)) // arctic or desert but not an oasis
522 damageMovement = moveCost;
523
524 if (((fromValue >> 1) & 0x7FF) + moveCost <= speed && ((fromValue >> 1) & 0x7FF) < speed)
525 toValue = (fromValue & ~NewTurn) + (moveCost << 1);
526 else
527 {
528 toValue = ((fromValue & 0x7FFFF000) + 0x1000 + (moveCost << 1)) | NewTurn; // must wait for next turn
529
530 if ((options & Options.TerrainResistant) == 0
531 && (fromTile & 0x800480) == 0 // no city, river or canal
532 && (fromTile & 0xF000) != 0x5000 // no base
533 && ((fromTile & 0x1F) == 0x06 || (fromTile & 0x3F) == 0x03)) // arctic or desert but not an oasis
534 damageMovement += speed - ((fromValue >> 1) & 0x7FF);
535 }
536 if (damageMovement > 0) // add recovery turns for waiting on hostile terrain and moving in it
537 {
538 int damage = (Cevo.DamagePerTurnInDesert * damageMovement - 1) / speed + 1;
539 toValue += ((damage + 4) >> 3) << 12; // actually: toValue += Math.Round(damage / Cevo.RecoveryOutsideCity) << 12
540 }
541
542 return StepValidity.OK;
543 }
544
545 case ModelDomain.Sea:
546 {
547 int toTile = theEmpire.Map.Ground[toLocationID];
548 if (((toTile & 0x800400) == 0 && (toTile & 0x1E) != 0x00))
549 return StepValidity.ForbiddenLocation; // no city, no canal, no water
550 if ((toTile & 0x1F) == 0x00 && (options & Options.Navigation) == 0)
551 return StepValidity.ForbiddenLocation; // open sea, no navigation
552
553 int moveCost = 100;
554 if (distance == 3)
555 moveCost = 150;
556 if (((fromValue >> 1) & 0x7FF) + moveCost <= speed && ((fromValue >> 1) & 0x7FF) < speed)
557 toValue = (fromValue & ~NewTurn) + (moveCost << 1);
558 else
559 toValue = ((fromValue & 0x7FFFF000) + 0x1000 + (moveCost << 1)) | NewTurn; // must wait for next turn
560 return StepValidity.OK;
561 }
562
563 case ModelDomain.Air:
564 {
565 int moveCost = 100;
566 if (distance == 3)
567 moveCost = 150;
568 if (((fromValue >> 1) & 0x7FF) + moveCost <= speed && ((fromValue >> 1) & 0x7FF) < speed)
569 toValue = (fromValue & ~NewTurn) + (moveCost << 1);
570 else
571 toValue = ((fromValue & 0x7FFFF000) + 0x1000 + (moveCost << 1)) | NewTurn; // must wait for next turn
572 return StepValidity.OK;
573 }
574 }
575 }
576 }
577
578 /// <summary>
579 /// An island iterator. Same set of locations as a RestrictedSprawl with AllLand option but with different order of
580 /// iteration. Simulates the movement of a standard slow ground unit so tiles that are easier to reach are
581 /// iterated earlier.
582 /// Tiles not discovered yet count as end of the island and are never iterated.
583 /// </summary>
584 class ExploreSprawl : TravelSprawl
585 {
586 public ExploreSprawl(AEmpire empire, Location origin)
587 : base(empire, empire.Us, origin, ModelDomain.Ground, 150, 150, Options.EmptyPlanet)
588 {
589 }
590 }
591}
Note: See TracBrowser for help on using the repository browser.