// --- Terrain pondéré : chaque case a un coût de traversée ---
// 1 = route (rapide), 3 = herbe, 8 = marécage, '#' = mur infranchissable.
// Coûts CONTRASTÉS -> A* va explorer, Greedy va se tromper : terrain non-dégénéré.
using System.Collections.Generic;
// Coût de traversée par type de case (null = mur).
var TERRAIN_COST = new Dictionary<char, int?> {
['.'] = 1, ['g'] = 3, ['s'] = 8, ['#'] = null // s = swamp, g = grass
};
const int ROWS = 25, COLS = 25;
(int, int) start = (0, 0), goal = (ROWS - 1, COLS - 1);
// Grille : (row, col) -> type de case. RNG .NET (différent du Mersenne Twister Python).
Dictionary<(int, int), char> MakeGrid(int rows, int cols, int seed)
{
var rng = new Random(seed);
var grid = new Dictionary<(int, int), char>();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
{
double x = rng.NextDouble();
if (x < 0.15) grid[(r, c)] = '#'; // mur (15%)
else if (x < 0.45) grid[(r, c)] = 'g'; // herbe (30%)
else if (x < 0.60) grid[(r, c)] = 's'; // marécage (15%)
else grid[(r, c)] = '.'; // route (40%)
}
(int, int) start = (0, 0), goal = (rows - 1, cols - 1);
grid[start] = '.'; grid[goal] = '.'; // départ + arrivée franchissables
return grid;
}
// Heuristique : Manhattan (admissible : coût min = 1, distance >= Manhattan*1).
int Manhattan((int r, int c) a, (int r, int c) b) => Math.Abs(a.r - b.r) + Math.Abs(a.c - b.c);
// Vérifie la connectivité start->goal par BFS (évite un terrain cloisonné par les murs).
bool Connected(Dictionary<(int, int), char> g, (int, int) s, (int, int) goal)
{
var seen = new HashSet<(int, int)> { s };
var queue = new Queue<(int, int)>();
queue.Enqueue(s);
while (queue.Count > 0)
{
var cur = queue.Dequeue();
if (cur.Equals(goal)) return true;
foreach (var n in Neighbors(g, cur))
if (seen.Add(n)) queue.Enqueue(n);
}
return false;
}
// Comme le RNG .NET (≠ Mersenne Twister Python) peut cloisonner le départ, on cherche
// le premier seed tel que start rejoigne goal. Pédagogie inchangée ; seed différé du jumeau Python.
Dictionary<(int, int), char> MakeConnectedGrid(int rows, int cols, (int, int) s, (int, int) g, out int seedUsed)
{
int seed = 42;
while (true)
{
var grid = MakeGrid(rows, cols, seed);
if (Connected(grid, s, g)) { seedUsed = seed; return grid; }
seed++;
}
}
var grid = MakeConnectedGrid(ROWS, COLS, start, goal, out int actualSeed);
// Coût d'un pas vers une case voisine (null = mur / hors-boundaires).
int? StepCost(Dictionary<(int, int), char> g, (int, int) cur, (int, int) nxt)
{
return g.TryGetValue(nxt, out char t) ? TERRAIN_COST[t] : null;
}
// Voisins 4-connexes franchissables.
List<(int, int)> Neighbors(Dictionary<(int, int), char> g, (int r, int c) s)
{
var out_ = new List<(int, int)>();
foreach (var (dr, dc) in new[] { (-1, 0), (1, 0), (0, -1), (0, 1) })
{
var n = (s.r + dr, s.c + dc);
if (n.Item1 >= 0 && n.Item1 < ROWS && n.Item2 >= 0 && n.Item2 < COLS
&& StepCost(g, s, n).HasValue)
out_.Add(n);
}
return out_;
}
int nWalls = 0;
foreach (var v in grid.Values) if (v == '#') nWalls++;
Console.WriteLine($"Grille {ROWS}x{COLS} : {nWalls} murs ({100.0*nWalls/(ROWS*COLS):F0}%), départ {start}, but {goal} (seed .NET = {actualSeed}).");
Console.WriteLine("Coûts contrastés (route=1, herbe=3, marécage=8) -> A* va explorer, Greedy va se tromper : terrain non-dégénéré.");Grille 25x25 : 91 murs (15%), départ (0, 0), but (24, 24) (seed .NET = 43).
Coûts contrastés (route=1, herbe=3, marécage=8) -> A* va explorer, Greedy va se tromper : terrain non-dégénéré.