Check If All Tiles Are Connected

Question

enter image description here

Hi! I have an interesting problem.

I have drawn in a HTML canvas a series of hexagons (ignore the dots)

For each hexagon I have it's x and y coordinates of their center, that's how I identify them.

I store the hexagons in an array called hexagons where I store Hexagons

    function Hexagon()
    {
        this.shape
        this.x
        this.y
    }

I have a function that returns an object with all the adjacent hexagons of a given hexagon

function get_adjacent_hexagons(hexagon)
{
    var x = hexagon.x
    var y = hexagon.y
    var adjacents = []
    for(var i=0; i<editor_hexagons.length; i++)
    {
        if(editor_hexagons[i].x === x && editor_hexagons[i].y == y - (2*s))
        {
            adjacents.push(editor_hexagons[i])
        }
        if(editor_hexagons[i].x === x && editor_hexagons[i].y == y + (2*s))
        {
            adjacents.push(editor_hexagons[i])  
        }
        if(editor_hexagons[i].x === x - (s*1.5) && editor_hexagons[i].y == y - s)
        {
            adjacents.push(editor_hexagons[i])  
        }
        if(editor_hexagons[i].x === x - (s*1.5) && editor_hexagons[i].y == y + s)
        {
            adjacents.push(editor_hexagons[i])  
        }
        if(editor_hexagons[i].x === x + (s*1.5) && editor_hexagons[i].y == y - s)
        {
            adjacents.push(editor_hexagons[i])  
        }
        if(editor_hexagons[i].x === x + (s*1.5) && editor_hexagons[i].y == y + s)
        {
            adjacents.push(editor_hexagons[i])  
        }
    }
    return adjacents
}

Given this information, is it possible to make an algorithm to check if all the hexagons are connected

That is if there is no hexagon or group of hexagons on their own?

For example in the picture provided they are all connected.

----- EDIT -----

This seems to be working

function check_connection()
{
    visited = []
    visit_hexagon(hexagons[0])
}

function visit_hexagon(hexagon)
{
    var not_visited = true
    for(var i=0; i<visited.length; i++)
    {
        if(visited[i] === hexagon)
        {
            not_visited = false
            break
        }
    }
    if(not_visited)
    {
        visited.push(hexagon)
        var adjacents = get_adjacent_hexagons(hexagon)
        for(var i=0; i<adjacents.length; i++)
        {
            visit_hexagon(adjacents[i])
        }
    }
}

Yes, of course it's possible. However, given your `get_adjacent_hexagons` implementation, I doubt it will be efficient. — Bergi, Jul 10 '14 at 20:04
What's the difference between the `hexagons` array and that `editor_hexagons` variable? Why is `adjacents` a global variable? — Bergi, Jul 10 '14 at 20:07
@Bergi you're right, by editor_hexagons I meant hexagons, let me edit that. — madprops, Jul 10 '14 at 20:08
Again, `visited` should not be global; make it local and `visit_hexagon` a local function in `check_connection`. Instead of the `not_visited` loop, just use [`indexOf`](http://stackoverflow.com/q/237104/1048572). Also, this hardly works, as `get_adjacent_hexagons` returns an object but you iterate it as if `adjacents` was an array. — Bergi, Jul 10 '14 at 23:41

score 1 · Answer 1 · answered Jul 10 '14 at 20:06

Yes. Since you can find the adjacent hexagons, you can create a graph of all the hexagons on the map. Then, you can simply run a breadth first search starting from a single node in the graph, and then check if all the nodes have been found after the end of the search. See more detailed at: https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Computational_aspects

score 1 · Accepted Answer · answered Jul 10 '14 at 20:08

1

Start by organizing your nodes (hexagons) into a graph structure where each node has a reference to the other nodes it is connected to. Mark all nodes as "unvisited". Start at any node and perform a breadth or depth first search marking each node you find as "visited". If after this there are any nodes that are not marked "visited" then your graph is not completely connected.

answered Jul 10 '14 at 20:08

mclaassen

5,018
4
30
52

@madprops I think your get_adjacent_hexagons is probably not working correctly. – mclaassen Jul 10 '14 at 22:56
but they are, I think. Check this picture http://i.imgur.com/t17KrRc.png I inserted those console.logs when I get the adjacents, printing each adjacent id. For some reason it doesn't visit 30 – madprops Jul 10 '14 at 23:03
@madprops I think it's because `adjacents` is global. You're replacing the list of adjacents in the recursive call. – mclaassen Jul 10 '14 at 23:13
No problem. Also you could make this a lot more efficient by pre populating the list of adjacents once and storing that in each hexagon object. – mclaassen Jul 10 '14 at 23:18

Check If All Tiles Are Connected

2 Answers2