arraystypescriptgraph

Creating a Bidimensional Grid Array using Map Graph in Typescript

I want to make a Game that uses a 2D Grid to represent the game map. I want to use a Graph Map to generate the map randomly, selecting random neighbors to make the connections between the grid nodes.

My types look like this:

type TileType = 'grass' | 'rock' | 'water' | 'empty';

type TileNode = {
  id: number; // Storing the ID
  type: TileType; // Node type
  neighbors: number[]; 

                      // This stores the IDs of the neighbors, varying 
                      // from 1 to 4

}

type MapGraph = {
  tiles: Map<number, TileNode>; // For holding the ID and the Node
}

export type { TileType, TileNode, MapGraph };

This is just a random map that I made, this is generated randomly by a function inside my code, but for example purposes I have included it here hardcoded.

const mapGraph2: MapGraph = {
    tiles: new Map([
        [0, {id: 0, type: 'grass', neighbors: [1, 3]}],      
        [1, {id: 1, type: 'grass', neighbors: [0, 4, 2]}],   
        [2, {id: 2, type: 'grass', neighbors: [1, 5]}],       
        [3, {id: 3, type: 'grass', neighbors: [0, 4, 6]}],
        [4, {id: 4, type: 'grass', neighbors: [1, 3, 5, 7]}],
        [5, {id: 5, type: 'grass', neighbors: [2, 4, 8]}],
        [6, {id: 6, type: 'grass', neighbors: [3, 7]}],
        [7, {id: 7, type: 'grass', neighbors: [6, 4, 8]}],
        [8, {id: 8, type: 'grass', neighbors: [7, 5, ]}],
    ]),
    nextId: mapGraph.nextId
}

This, ultimately, has to look like this in my game: The tiles being next to each other as the Graph dictates.

// [0 1 2]
// [3 4 5]
// [6 7 8]

I actually tried just making sure my React component renders a SVG initially (Being the TILE 0) and then it just pops the neighbors around it. But this solution did not work because I do not have directions.

Another way to implement this, is making a Type that kinda looks like this:

type TileNode = {
    id: number;
    node-south: number; // Node ID
    node-north: number;
    node-west: number;
    node-east: number;
}

This would work as this would dictate the directions of the tiles so mapping this to a 2D game map would be easier, but I cant make use of this because supposedly the best solution isn't this one, and I wanted to know if its possible to directly convert the Graph to a Grid respecting the neighbors and placing them with sense.

A Bidimensional Array is not needed, its not my ultimate goal, but I think it would help to represent it here in Stackoverflow without going all in in React-Native components.

EXAMPLE EDIT:

Here I made an example of what I want.

Graph Map

This needs to be converted to:

2D Example

Solution

  • For ease of discussion I will just assume nodes are numeric ids with no data. You can easily modify any algorithm to associate data with these ids as well. A graph is therefore of the form

    interface Graph {
    [id: number]: {
        neighbors: number[]
    }
}

    whereas a two dimensional grid could be of the form number[][], or Map<number, Map<number, number>> or {[x: number]: {[y: number]: number} or anything that represents x-y coordinates of each node id. For ease of writing an algorithm I will have redundant information in the grid:

    interface Grid {
    grid: { [x: number]: { [y: number]: number } }
    unplaced: Set<number>;
    locations: { [id: number]: [x: number, y: number] }
}

    Here grid is the aforementioned representation where you look up grid[x][y] to see what tile is there (where undefined means there's no tile there). And unplaced is a Set of all currently unplaced tiles, and locations is a reverse lookup of grid. That is, if grid[x][y] is n then locations[n] is [x, y].

    To place a tile on the grid you need to make sure to update all three properties, but this is straightforward:

    function placeTile(grid: Grid, id: number, x: number, y: number): Grid {
    if (!grid.unplaced.has(id)) throw new Error("Not unplaced");
    if (grid.grid[x]?.[y] !== undefined) throw new Error("Tile already placed there");
    return {
        grid: { ...grid.grid, [x]: { ...grid.grid[x], [y]: id } },
        unplaced: grid.unplaced.difference(new Set([id])),
        locations: { ...grid.locations, [id]: [x, y] }
    }
}

    (Note that I'm making a new Grid and not mutating the old one.)

    The relationship between a Grid and a Graph is intended to be that the neighbors of a tile n located at [x, y] = locations[n] are the list of contents of grid[x+1][y], grid[x-1][y], grid[x][y+1], and grid[x][y-1] (that is, the neighbors are in cells immediately to the right, to the left, above, and below).

    I strongly recommend that you do not start with a Graph and use it to generate a Grid.

    First, if you randomly generate a Graph there's a good chance it cannot be a Grid. Some constraints are obvious, like no node can have more than four neighbors. But some constraints are less obvious. For example, the following Graph cannot be a Grid: { 0: { neighbors: [1, 2] }, 1: { neighbors: [0, 2] }, 2: { neighbors: [0, 1] } }. Why not? Well, once you place 0 and 1 next to each other, you can't place 2 anywhere that's both a neighbor of 0 and 1. That would require diagonal neighbors, which we don't allow.

    Second, even if we assume the graph can indeed be embedded in a grid, it isn't simple or obvious how to do this. From my research, the best you can do is a recursive solution where you place tiles individually, checking to make sure each tile you place respects the graph's neighbor relations, and backtracking when you run into a dead end. This is fundamentally a search algorithm.

    Finally, there might be many ways to embed a graph as a grid. For example, a path graph that looks like a 0↔1↔2↔3↔4↔5↔6↔7↔8 can be embedded all sorts of ways, such as a straight line, or some kind of snake. So then the question becomes "which is the desired solution"? Maybe you don't care which one, but someone easily could care, like they want one that needs the smallest area bounding box, and then the search algorithm becomes more complicated.

    To reiterate: it's easy for there to be zero solutions or many solutions, and finding even one solution requires a search.

    It is much much easier to start with a Grid and use it to generate a Graph. Here is a simple function that does this:

    function gridToGraph(grid: Grid): Graph {
    const dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    return Object.fromEntries(Object.entries(grid.locations).map(
        ([k, [x, y]]) => [k, {
            neighbors: dirs.map(([dx, dy]) =>
                grid.grid[x + dx]?.[y + dy]
            ).filter(n => n !== undefined)
        }]));
}

    Look how short that is. It takes each tile in the grid, looks at its immediate neighbors, and puts them in an array. This representation is unique if you ignore the order of the neighbors arrays (and if you wanted to, you could sort those). It's just a loop.

    If for some reason you persist in wanting to start with a graph and go to a grid, then things become ugly. I wrote a program to do that, but... does it have bugs? Who knows. It's complicated. Here it is:

    function graphToGrid(graph: Graph): Grid | undefined {
    if (Object.values(graph).some(n => n.neighbors.length > 4)) return undefined;

    const dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    const emptyGrid: Grid = {
        grid: {},
        locations: {},
        unplaced: new Set(Object.keys(graph).map(x => Number(x)))
    }
    function tryToPlaceTile(grid: Grid, id: number, x: number, y: number): Grid | undefined {

        const actuallyPlacedNeighbors = new Set(dirs.map(([dx, dy]) => grid.grid[x + dx]?.[y + dy]).filter(x => x !== undefined));
        const intendedPlacedNeighbors = new Set(graph[id].neighbors.filter(n2 => !grid.unplaced.has(n2)));
        if (actuallyPlacedNeighbors.symmetricDifference(intendedPlacedNeighbors).size) {
            return undefined;
        }
        grid = placeTile(grid, id, x, y);
        if (grid.unplaced.size === 0) return grid;


        // find unplaced tile with at least one placed neighbor
        const unplacedTile = (
            Array.from(grid.unplaced)
        ).find(n => graph[n].neighbors.some(n2 => !grid.unplaced.has(n2)));

        if (unplacedTile === undefined) {
            const firstTile = (Array.from(grid.unplaced))[0];
            const newEmptyGrid: Grid = {
                grid: {},
                locations: {},
                unplaced: new Set(grid.unplaced)
            }
            const newNextGrid = tryToPlaceTile(newEmptyGrid, firstTile, 0, 0);
            if (!newNextGrid) return undefined;
            const offset = Math.max(...Object.values(grid.locations).map(([x, _]) => x)) + 2 - Math.min(...Object.values(newNextGrid.locations).map(([x, _]) => +x));
            return {
                grid: { ...grid.grid, ...Object.fromEntries(Object.entries(newNextGrid.grid).map(([k, v]) => [+k + offset, v])) },
                locations: { ...grid.locations, ...Object.fromEntries(Object.entries(newNextGrid.locations).map(([i, [x, y]]) => [i, [+x + offset, y]])) },
                unplaced: newNextGrid.unplaced
            }
        }

        const [newX, newY] = grid.locations[graph[unplacedTile].neighbors.find(n2 => !grid.unplaced.has(n2))!];

        for (const [dx, dy] of (dirs)) {
            const nextGrid = tryToPlaceTile(grid, unplacedTile, newX + dx, newY + dy);
            if (nextGrid) return nextGrid;

        }
        return undefined;

    }

    const firstTile = emptyGrid.unplaced.values().next().value;
    if (firstTile === undefined) return emptyGrid; // huh?

    return tryToPlaceTile(emptyGrid, firstTile, 0, 0);
}

    Rather than go through every line here, I'll describe the general approach I'm taking:

    1. Pick a random unplaced tile and place it at the origin [0, 0].

    2. Pick a placed tile which has at least one unplaced neighbor. If you can't do this, then either:

      • all the tiles have been placed, in which case you're done, or
      • the unplaced tiles are not connected at all to the tiles you've placed; it's a separate grid entirely. So you're done with the current grid and you should go back to step 1 to place the rest of the tiles, and then, if you want, join the two disconnected grids however you want (like offset the x-coordinates of one grid so it doesn't touch any of the elements of the other grid)

    3. Try to place the unplaced neighbor next to the placed tile, by trying each of the spaces next to the placed tile in turn (that is, check "up", "down", "left", "right" in turn). To "try" a space:

      • if the space is not empty, you've failed, go back to step 3 with the next direction
      • if placing the tile there would cause the tile not to be a grid neighbor to all of its graph neighbor tiles that have already been placed, then you've failed, go back to step 3 with the next direction.
      • if placing the tile there would cause the tile to be a grid neighbor to a placed tile which is not a graph neighbor, then you've failed, go back to step 3 with the next direction.
      • provisionally place the tile in the space, and then recurse by starting at step 2 again. If this comes back as a failure, then you've failed, go back to step 3 with the next direction. If it succeeds, then you're done! Return the successfully created grid.

    4. If you've tried all four directions and each one fails, then you've failed. It is impossible to create a grid for the graph given the current grid. Return a failure. Note that this doesn't mean a global failure, it's possible you're recursing in step 3 somewhere, and the current failure just means the previously placed tile needs to be undone.

    My verbal description of this is complicated, and to describe the code above in more detail would be even worse. I've done some things like bail out early if any node has more than four graph neighbors, and I'm comparing Sets to check if neighbors are as expected, and... anyway, it's complicated.

    Okay, so, we can test against your example. Given a grid that looks like

    0: 4,1
1: 6,0,5
2: 6
3: 7
4: 0
5: 8,1,7
6: 7,1,2
7: 3,6,5
8: 5,9
9: 8

    my function generates this grid:

    |   |   |0  |4  |
|2  |6  |1  |   |
|   |7  |5  |8  |
|   |3  |   |9  |

    which looks similar to yours. Note that there are a lot of places in the algorithm where you pick one of some set, and if you do that randomly it means you can get different grids. If I turn on randomness of choice in my code, then I get things like

    |   |   |4  |   |
|   |   |0  |   |
|2  |6  |1  |   |
|   |7  |5  |8  |
|   |3  |   |9  |

    or

    |4  |0  |   |   |   |
|   |1  |5  |8  |9  |
|2  |6  |7  |   |   |
|   |   |3  |   |   |

    which all obey the graph definition while being different in terms of the embedding.

    I've tried hand-coded graphs with disconnected things (let's say you add {100: [101], 101: [100]} at the end of an existing graph, then you'll end up with some two-tile thing floating around:

    |   |3  |   |9  |
|   |7  |5  |8  |
|2  |6  |1  |   |
|   |   |0  |4  |
|   |   |   |   |
|   |100|   |   |
|   |101|   |   |

    I could try random graphs but they almost always fail in my experience. At this point I think I'll stop. Again, the graphToGrid() algorithm I've written is complicated, and much much more complicated than gridToGraph(), which is straightforward. If you ever find yourself in a position where you want both a Graph and a Grid, please make it easy and start with the Grid.

    Playground link to code