Почему некоторые случайно выбранные варианты для BestDoor делают недоступные комнаты? ⇐ Javascript

[Anonymous]

Я делаю мини -игру Minecraft, которая включает в себя кучу комнат, соединенных случайно открытыми/закрытыми дверями. Я хочу убедиться, что игрок всегда может добраться до каждой комнаты, даже если им нужно взять огромный объезд. Мое решение для этого состояло в том, чтобы сделать некоторый код, чтобы определить, какие двери необходимо зависеть от других дверей (то есть, если дверь 1-2 закрыта, должна быть открыта дверь 1-167), но иногда мой код возвращает макет, который закрывает комнаты, когда все случайные двери закрыты. < /P>
function getDoorName(a, b) {
return [a, b].sort().join("-");
}

function buildGraph(rooms, hallwayPairs) {
const graph = {};
for (const r of rooms) graph[r] = [];
for (const [a, b] of hallwayPairs) {
if (!graph[a]) graph[a] = [];
if (!graph) graph = [];
graph[a].push(b);
graph.push(a);
}
console.log("Graph built:", graph);
return graph;
}

function isConnectedAllRooms(rooms, openEdges) {
const graph = buildGraph(rooms, openEdges);
const visited = new Set();
const stack = [];

for (const r of [...rooms].sort(() => Math.random() - 0.5)) {
if (graph[r] && graph[r].length > 0) {
stack.push(r);
break;
}
}

if (stack.length === 0) {
console.log("No starting room found, assuming 0 or 1 room:", rooms.length);
return rooms.length Math.random() - 0.5);
for (const u of neighbors) {
if (!visited.has(u)) stack.push(u);
}
}
}
const allConnected = visited.size === rooms.length;
if (!allConnected) {
console.log(
"Disconnected rooms:",
rooms.filter((r) => !visited.has(r))
);
}
return allConnected;
}

function isSubset(sub, sup) {
return sub.every((x) => sup.includes(x));
}

function dedupeMinimalSets(sets) {
const minimal = [];
for (const s of sets) {
const combo = [...s].sort();
let subsumed = false;
for (const m of minimal) {
if (isSubset(m, combo)) {
subsumed = true;
break;
}
}
if (!subsumed) {
for (let i = minimal.length - 1; i >= 0; i--) {
if (isSubset(combo, minimal)) minimal.splice(i, 1);
}
minimal.push(combo);
}
}
return minimal;
}

function findBridgeDoors(rooms, hallwayPairs) {
const graph = buildGraph(rooms, hallwayPairs);
const ids = {},
low = {};
let time = 0;
const bridges = [];

function dfs(at, parent) {
ids[at] = low[at] = ++time;
for (const to of (graph[at] || []).sort(() => Math.random() - 0.5)) {
if (to === parent) continue;
if (!ids[to]) {
dfs(to, at);
low[at] = Math.min(low[at], low[to]);
if (low[to] > ids[at]) bridges.push(getDoorName(at, to));
} else {
low[at] = Math.min(low[at], ids[to]);
}
}
}

for (const r of [...rooms].sort(() => Math.random() - 0.5))
if (!ids[r]) dfs(r, -1);
console.log("Bridges found:", bridges);
return bridges;
}

function findMinimalDependencies(rooms, hallwayPairs, options = {}) {
const { maxBruteforceDoors = 18 } = options;
const doorList = hallwayPairs.map(([a, b]) => getDoorName(a, b));
const doorToEdge = Object.fromEntries(
doorList.map((d, i) => [d, hallwayPairs])
);
const graph = buildGraph(rooms, hallwayPairs);

const incidentCuts = [];
for (const room of rooms) {
const neighbors = graph[room] || [];
const incident = neighbors.map((n) => getDoorName(room, n));
const uniq = Array.from(new Set(incident)).sort();
if (uniq.length >= 1) incidentCuts.push(uniq);
}

const bridgeDoorNames = findBridgeDoors(rooms, hallwayPairs);
const bridgeCuts = bridgeDoorNames.map((d) => [d]);

const extraCuts = [];
if (doorList.length Math.random() - 0.5
);
for (const door of shuffledDoors) {
const cutSet = doorCutMap[door];
const count = [...cutSet].filter((i) => uncoveredCuts.has(i)).length;
if (count > bestCount) {
bestCount = count;
bestDoor = door;
}
}
if (bestDoor == null) break;
dependentDoors.add(bestDoor);
for (const cutIdx of doorCutMap[bestDoor]) uncoveredCuts.delete(cutIdx);
}

const dependencies = {};
for (const cut of allCuts) {
let keeper = cut.find((d) => dependentDoors.has(d));
if (!keeper) {
keeper = cut[0];
dependentDoors.add(keeper);
}
const others = cut.filter((d) => d !== keeper);
if (!dependencies[keeper]) dependencies[keeper] = [];
dependencies[keeper].push(others);
}

const randomDoors = doorList.filter((d) => !dependentDoors.has(d));
const validRandomDoors = randomDoors.filter((door) => {
const openEdges = hallwayPairs.filter(
([a, b]) => getDoorName(a, b) !== door
);
const connected = isConnectedAllRooms(rooms, openEdges);
if (!connected)
console.log("Excluding random door that disconnects:", door);
return connected;
});

let count1 = 0;
for (const conds of Object.values(dependencies)) {
for (const cond of conds) count1 += cond.length;
}

console.log("Final dependencies:", dependencies);
console.log("Valid random doors:", validRandomDoors);

return {
randomDoors: validRandomDoors,
dependencies,
minimalFailureSets: allCuts,
totalComplexity: count1,
};
}

function finalCheck(ranDoors, label = "") {
const openEdges = hallways.filter(
(h) => !ranDoors.includes(getDoorName(h[0], h[1]))
);
if (isConnectedAllRooms(rooms, openEdges)) return 1;
const unreachable = rooms.filter((r) => {
const g = buildGraph(rooms, openEdges);
const seen = new Set();
const stack = [rooms.find((r) => g[r] && g[r].length > 0)];
while (stack.length) {
const curr = stack.pop();
if (!seen.has(curr)) {
seen.add(curr);
for (const n of g[curr] || []) {
if (!seen.has(n)) stack.push(n);
}
}
}
return !seen.has(r);
});
console.log(`Unreachable with label: ${label}`);
console.log(unreachable);
return 0;
}
let rooms = [
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 167,
38914, 131417, 1015, 1120, 15181925, 182324, 222728, 273236, 2829, 2529, 3031,
3539, 3135, 323637,
];

let hallways = [
[1, 2],
[1, 167],
[2, 3],
[2, 7],
[3, 4],
[3, 38914],
[3, 9],
[4, 5],
[4, 9],
[5, 11],
[6, 167],
[6, 12],
[7, 167],
[7, 8],
[7, 13],
[8, 38914],
[9, 38914],
[10, 11],
[10, 1015],
[11, 1120],
[12, 13],
[12, 16],
[13, 131417],
[14, 131417],
[14, 18],
[14, 15],
[15, 1015],
[1015, 1120],
[16, 17],
[16, 22],
[17, 22],
[17, 131417],
[17, 18],
[18, 15181925],
[19, 15181925],
[19, 20],
[20, 1120],
[20, 26],
[21, 22],
[21, 27],
[22, 23],
[22, 222728],
[23, 28],
[23, 182324],
[24, 182324],
[24, 25],
[25, 26],
[25, 2529],
[25, 30],
[26, 30],
[27, 222728],
[28, 222728],
[28, 2829],
[28, 32],
[29, 2829],
[29, 2529],
[30, 3031],
[31, 3135],
[31, 3031],
[32, 273236],
[32, 323637],
[32, 33],
[32, 36],
[33, 34],
[33, 37],
[34, 35],
[34, 38],
[35, 3135],
[35, 3539],
[35, 39],
[36, 273236],
[36, 323637],
[37, 323637],
[37, 38],
[39, 3539],
[2529, 3135],
[3031, 3539],
];

let bestResult = null;
let bestRandomDoorsCount = 0;
const startTime = Date.now();

while (Date.now() - startTime < 1000 * 100 || !bestResult) {
const result = findMinimalDependencies(rooms, hallways);
const ranDoors = result.randomDoors;
if (finalCheck(ranDoors, ranDoors.join(", "))) {
if (ranDoors.length > bestRandomDoorsCount) {
bestResult = result;
bestRandomDoorsCount = ranDoors.length;
console.log(
"New best with " +
ranDoors.length +
" random doors and " +
result.totalComplexity +
" conditions."
);
}
}
}

if (bestResult) {
console.log("Best configuration found:");
console.log(`Random doors: `, bestResult.randomDoors);
console.log("Dependency rules:");
for (const [door, conditions] of Object.entries(bestResult.dependencies)) {
for (const cond of conditions) {
console.log(`\"${door}\" must be open if `, cond, `are all closed`);
}
}
console.log(
"\nBest configuration has " +
bestResult.randomDoors.length +
" random doors and " +
bestResult.totalComplexity +
" complexity."
);
} else {
console.log("No configuration passed the finalCheck within the time limit.");
}


Подробнее здесь: https://stackoverflow.com/questions/797 ... able-rooms