Fury of Dracula. Search algorithm.

findNearbyLocations.js

const data = {
    locations: {
        atlantic_ocean: {
            id: 'atlantic_ocean',
            name: 'Atlantic Ocean',
            isSea: true,
        },
        biscay_bay: {
            id: 'biscay_bay',
            name: 'Biscay bay',
            isSea: true,
        },
        north_atlantic: {
            id: 'north_atlantic',
            name: 'North Atlantic',
            isSea: true,
        },
        south_atlantic: {
            id: 'south_atlantic',
            name: 'South Atlantic',
            isSea: true,
        },
        north_sea: {
            id: 'north_sea',
            name: 'North sea',
            isSea: true,
        },
        english_channel: {
            id: 'english_channel',
            name: 'English channel',
            isSea: true,
        },
        irish_sea: {
            id: 'irish_sea',
            name: 'Irish sea',
            isSea: true,
        },
        midterranean_sea: {
            id: 'midterranean_sea',
            name: 'Midterranean sea',
            isSea: true,
        },
        jonian_sea: {
            id: 'jonian_sea',
            name: 'Jonian sea',
            isSea: true,
        },
        tyrrhenian_sea: {
            id: 'tyrrhenian_sea',
            name: 'Tyrrhenian sea',
            isSea: true,
        },
        adriatic_sea: {
            id: 'adriatic_sea',
            name: 'Adriatic sea',
            isSea: true,
        },
        black_sea: {
            id: 'black_sea',
            name: 'Black sea',
            isSea: true,
        },



        edinburg: {
            id: 'edinburg',
            name: 'Edinburg',
            isSea: false,
        },
        manchester: {
            id: 'manchester',
            name: 'Manchester',
            isSea: false,
        },
        liverpool: {
            id: 'liverpool',
            name: 'Liverpool',
            isSea: false,
        },
        london: {
            id: 'london',
            name: 'London',
            isSea: false,
        },
        swansea: {
            id: 'swansea',
            name: 'Swansea',
            isSea: false,
        },
        plymouth: {
            id: 'plymouth',
            name: 'Plymouth',
            isSea: false,
        },
        galway: {
            id: 'galway',
            name: 'Galway',
            isSea: false,
        },
        dublin: {
            id: 'dublin',
            name: 'Dublin',
            isSea: false,
        },


        lisbon: {
            id: 'lisbon',
            name: 'Lisbon',
            isSea: false,
        },
        cadiz: {
            id: 'cadiz',
            name: 'Cadiz',
            isSea: false,
        },
        madrid: {
            id: 'madrid',
            name: 'Madrid',
            isSea: false,
        },
        granada: {
            id: 'granada',
            name: 'Granada',
            isSea: false,
        },
        alicante: {
            id: 'alicante',
            name: 'Alicante',
            isSea: false,
        },
        barcelona: {
            id: 'barcelona',
            name: 'Barcelona',
            isSea: false,
        },
        santander: {
            id: 'santander',
            name: 'Santander',
            isSea: false,
        },
        saragossa: {
            id: 'saragossa',
            name: 'Saragossa',
            isSea: false,
        },


        nantes: {
            id: 'nantes',
            name: 'Nantes',
            isSea: false,
        },
        le_havre: {
            id: 'le_havre',
            name: 'Le Havre',
            isSea: false,
        },
        paris: {
            id: 'paris',
            name: 'Paris',
            isSea: false,
        },
        bordeaun: {
            id: 'bordeaun',
            name: 'Bordeaun',
            isSea: false,
        },
        toulouse: {
            id: 'toulouse',
            name: 'Toulouse',
            isSea: false,
        },
        clermont_ferrand: {
            id: 'clermont_ferrand',
            name: 'Clermont Ferrand',
            isSea: false,
        },
        marseilles: {
            id: 'marseilles',
            name: 'Marseilles',
            isSea: false,
        },
        brussels: {
            id: 'brussels',
            name: 'Brussels',
            isSea: false,
        },
        strasbourg: {
            id: 'strasbourg',
            name: 'Strasbourg',
            isSea: false,
        },


        zurich: {
            id: 'zurich',
            name: 'Zurich',
            isSea: false,
        },
        geneva: {
            id: 'geneva',
            name: 'Geneva',
            isSea: false,
        },
        milan: {
            id: 'milan',
            name: 'Milan',
            isSea: false,
        },
        genoa: {
            id: 'genoa',
            name: 'Genoa',
            isSea: false,
        },
        venice: {
            id: 'venice',
            name: 'Venice',
            isSea: false,
        },
        cagliari: {
            id: 'cagliari',
            name: 'Cagliari',
            isSea: false,
        },
        florence: {
            id: 'florence',
            name: 'Florence',
            isSea: false,
        },
        rome: {
            id: 'rome',
            name: 'Rome',
            isSea: false,
        },
        naples: {
            id: 'naples',
            name: 'Naples',
            isSea: false,
        },
        bari: {
            id: 'bari',
            name: 'Bari',
            isSea: false,
        },


        amsterdam: {
            id: 'amsterdam',
            name: 'Amsterdam',
            isSea: false,
        },
        cologne: {
            id: 'cologne',
            name: 'Cologne',
            isSea: false,
        },
        hamburg: {
            id: 'hamburg',
            name: 'Hamburg',
            isSea: false,
        },
        berlin: {
            id: 'berlin',
            name: 'Berlin',
            isSea: false,
        },
        lejpzig: {
            id: 'lejpzig',
            name: 'Lejpzig',
            isSea: false,
        },
        frankfurk: {
            id: 'frankfurk',
            name: 'Frankfurk',
            isSea: false,
        },
        nuremberg: {
            id: 'nuremberg',
            name: 'Nuremberg',
            isSea: false,
        },
        munich: {
            id: 'munich',
            name: 'Munich',
            isSea: false,
        },


        prague: {
            id: 'prague',
            name: 'Prague',
            isSea: false,
        },
        vienna: {
            id: 'vienna',
            name: 'Vienna',
            isSea: false,
        },
        zagreb: {
            id: 'zagreb',
            name: 'Zagreb',
            isSea: false,
        },
        budapest: {
            id: 'budapest',
            name: 'Budapest',
            isSea: false,
        },
        szeged: {
            id: 'szeged',
            name: 'Szeged',
            isSea: false,
        },
        sarajevo: {
            id: 'sarajevo',
            name: 'Sarajevo',
            isSea: false,
        },
        belgrade: {
            id: 'belgrade',
            name: 'Belgrade',
            isSea: false,
        },
        klausenburg: {
            id: 'klausenburg',
            name: 'Klausenburg',
            isSea: false,
        },


        castle_dracula: {
            id: 'castle_dracula',
            name: 'Castle Dracula',
            isSea: false,
        },
        valona: {
            id: 'valona',
            name: 'Valona',
            isSea: false,
        },
        salonica: {
            id: 'salonica',
            name: 'Salonica',
            isSea: false,
        },
        atrens: {
            id: 'atrens',
            name: 'Atrens',
            isSea: false,
        },
        sofia: {
            id: 'sofia',
            name: 'Sofia',
            isSea: false,
        },
        varna: {
            id: 'varna',
            name: 'Varna',
            isSea: false,
        },
        constanta: {
            id: 'constanta',
            name: 'Constanta',
            isSea: false,
        },
        bucharest: {
            id: 'bucharest',
            name: 'Bucharest',
            isSea: false,
        },
        galatz: {
            id: 'galatz',
            name: 'Galatz',
            isSea: false,
        },
    },
    graph: {
        atlantic_ocean: ['galway', 'hamburg', 'edinburg', 'irish_sea', 'english_channel', 'midterranean_sea'],
        biscay_bay: ['nantes', 'bordeaun', 'santander'],
        north_atlantic: ['galway', 'nantes', 'bordeaun', 'north_sea', 'irish_sea', 'english_channel', 'south_atlantic'],
        south_atlantic: ['santander', 'lisbon', 'cadiz', 'north_atlantic', 'midterranean_sea'],

        north_sea: ['amsterdam', 'hamburg', 'edinburg', 'english_channel', 'north_atlantic'],
        english_channel: ['london', 'plymouth', 'le_havre', 'north_sea', 'north_atlantic'],
        irish_sea: ['dublin', 'liverpool', 'swansea', 'north_atlantic'],
        midterranean_sea: ['alicante', 'barcelona', 'marseilles', 'cagliari', 'tyrrhenian_sea', 'south_atlantic'],
        jonian_sea: ['athens', 'salonica', 'valona', 'tyrrhenian_sea', 'adriatic_sea', 'black_sea'],
        tyrrhenian_sea: ['genoa', 'rome', 'naples', 'cagliari', 'midterranean_sea', 'jonian_sea'],
        adriatic_sea: ['bari', 'valona', 'venice', 'jonian_sea'],
        black_sea: ['constanta', 'varna', 'jonian_sea'],

        edinburg: ['manchester', 'north_sea'],
        manchester: ['edinburg', 'liverpool', 'london'],
        liverpool: ['irish_sea', 'swansea', 'manchester'],
        london: ['manchester', 'plymouth', 'swansea', 'english_channel'],
        swansea: ['liverpool', 'london', 'irish_sea'],
        plymouth: ['english_channel', 'london'],
        galway: ['north_atlantic', 'atlantic_ocean', 'dublin'],
        dublin: ['galway', 'irish_sea'],

        lisbon: ['south_atlantic', 'atlantic_ocean', 'santander', 'madrid', 'cadiz'],
        cadiz: ['lisbon', 'madrid', 'granada', 'south_atlantic'],
        madrid: ['santander', 'saragossa', 'alicante', 'granada', 'cadiz', 'lisbon'],
        granada: ['alicante', 'madrid', 'cadiz'],
        alicante: ['saragossa', 'madrid', 'granada', 'midterranean_sea'],
        barcelona: ['toulouse', 'saragossa', 'midterranean_sea'],
        santander: ['lisbon', 'madrid', 'saragossa', 'bordeaun', 'south_atlantic'],
        saragossa: ['madrid', 'santander', 'toulouse', 'barcelona'],

        nantes: ['le_havre', 'paris', 'clermont_ferrand', 'bordeaun', 'north_atlantic'],
        le_havre: ['english_channel', 'brussels', 'paris', 'nantes'],
        paris: ['brussels', 'strasbourg', 'geneva', 'clermont_ferrand', 'nantes', 'le_havre'],
        bordeaun: ['nantes', 'clermont_ferrand', 'toulouse', 'santander', 'north_atlantic'],
        toulouse: ['barcelona', 'saragossa', 'bordeaun', 'clermont_ferrand', 'marseilles'],
        clermont_ferrand: ['paris', 'geneva', 'marseilles', 'toulouse', 'bordeaun', 'nantes'],
        marseilles: ['toulouse', 'genoa', 'milan', 'zurich', 'geneva', 'clermont_ferrand', 'midterranean_sea'],
        brussels: ['amsterdam', 'cologne', 'strasbourg', 'paris', 'le_havre'],
        strasbourg: ['paris', 'brussels', 'cologne', 'frankfurk', 'nuremberg', 'zurich'],

        zurich: ['geneva', 'strasbourg', 'nuremberg', 'munich', 'milan', 'marseilles'],
        geneva: ['paris', 'zurich', 'strasbourg', 'marseilles', 'clermont_ferrand'],
        milan: ['zurich', 'munich', 'venice', 'genoa', 'marseilles'],
        genoa: ['milan', 'marseilles', 'venice', 'florence', 'tyrrhenian_sea'],
        venice: ['munich', 'milan', 'genoa', 'florence', 'adriatic_sea'],
        cagliari: ['midterranean_sea', 'tyrrhenian_sea'],
        florence: ['venice', 'genoa', 'rome'],
        rome: ['florence', 'naples', 'bari', 'tyrrhenian_sea'],
        naples: ['rome', 'bari', 'tyrrhenian_sea'],
        bari: ['adriatic_sea', 'naples', 'rome'],

        amsterdam: ['north_sea', 'cologne', 'brussels'],
        cologne: ['brussels', 'strasbourg', 'hamburg', 'amsterdam', 'lejpzig', 'frankfurk'],
        hamburg: ['lejpzig', 'cologne', 'berlin', 'north_sea'],
        berlin: ['hamburg', 'prague', 'lejpzig'],
        lejpzig: ['prague', 'berlin', 'hamburg', 'cologne', 'frankfurk', 'nuremberg'],
        frankfurk: ['cologne', 'lejpzig', 'nuremberg', 'strasbourg'],
        nuremberg: ['strasbourg', 'zurich', 'frankfurk', 'lejpzig', 'prague', 'munich'],
        munich: ['zurich', 'milan', 'venice', 'nuremberg', 'vienna', 'zagreb'],

        prague: ['berlin', 'vienna', 'nuremberg'],
        vienna: ['prague', 'budapest', 'zagreb', 'munich'],
        zagreb: ['vienna', 'budapest', 'szeged', 'sarajevo', 'munich'],
        budapest: ['klausenburg', 'szeged', 'zagreb', 'vienna'],
        szeged: ['klausenburg', 'belgrade', 'zagreb', 'budapest'],
        sarajevo: ['belgrade', 'sofia', 'valona', 'zagreb'],
        belgrade: ['szeged', 'sarajevo', 'klausenburg', 'bucharest', 'sofia'],
        klausenburg: ['castle_dracula', 'belgrade', 'budapest', 'szeged', 'bucharest', 'galatz'],

        castle_dracula: ['klausenburg', 'galatz'],
        valona: ['atrens', 'salonica', 'adriatic_sea', 'sarajevo', 'sofia'],
        salonica: ['jonian_sea', 'valona', 'sofia'],
        atrens: ['valona', 'jonian_sea'],
        sofia: ['valona', 'salonica', 'bucharest', 'sarajevo', 'belgrade', 'varna'],
        varna: ['constanta', 'sofia', 'black_sea'],
        constanta: ['bucharest', 'varna', 'black_sea'],
        bucharest: ['constanta', 'sofia', 'galatz', 'belgrade', 'klausenburg'],
        galatz: ['klausenburg', 'castle_dracula', 'bucharest'],
    }
}

const startNode = 'edinburg';
const seaPositions = [];
const deep = 3;

function findNearbyLocations(startNode, deep = 0, seaPositions = [], excludeLocations = []) {
    let subLocations = [];
    const childLocations = data.graph[startNode];

    if (excludeLocations.indexOf(startNode) >= 0) {
        return [];
    }
    if (excludeLocations.length <= Math.round(deep / 2)) {
        excludeLocations.unshift(startNode);
    }

    if (deep == 0) {
        return [startNode];
    }
    const currentDeep = deep - 1;
    childLocations.forEach((locationId) => {
        const location = data.locations[locationId];


        if (location.isSea && seaPositions.indexOf(currentDeep) != -1) {
            subLocations = [
                ...subLocations,
                ...findNearbyLocations(locationId, currentDeep, seaPositions, excludeLocations)
            ];
        }
        if (!location.isSea && seaPositions.indexOf(currentDeep) == -1) {
            subLocations = [
                ...subLocations,
                ...findNearbyLocations(locationId, currentDeep, seaPositions, excludeLocations)
            ];
        }
    });

    const unique = [];
    subLocations.forEach((location) => {
        if (unique.indexOf(location) == -1) {
            unique.unshift(location);
        }
    });

    return unique;
}

console.log('queue', findNearbyLocations(startNode, deep, seaPositions));