Determine if a shape is closed

I’ve been in the process of trying to workout if a shape is closed so intern I can fill the shape, I’ve written a little test program in VB.net.



Red = walls
Light Blue = water
Black = Towers
Dark Blue = Fill

I’ve seen this other person ask the same question here:

http://gamedev.stackexchange.com/qu...et-of-tiles-on-a-grid-forms-an-enclosed-shape

A lot of the person ideas are the same as this will be a touch app, using unity, I’m just trying to put a prototype together and though this was going to be the hardest part so I’ll start there.

Although they allow(is classed as a connection) diagonal tiles as well mine does not.



I’ve workout the code for filling the shape using the following website.

http://lodev.org/cgtutor/floodfill.html

As far as I’m aware the graph formula is taken from here:

https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

or at least an idea personally I don’t really understand this, it’s been 30 years since I was at school I did not learn this form of trig etc.

I’ve always said if I can understand it I can code it, makes sense I suppose.

Anyways this got me thinking, this is basically a form of Linked List, which I do understand.

A node in a linked list contains some sort of data and a link to the next node itself

Hmmmm I paused that might work, I’ll still need to know which are the start and end nodes in the list.

I then though of another problem with this let’s take the map image, and add another shape above the first this could intersect with the nodes at the top of the first shape so a traditional node itself will not work or are these effectively separate shapes??

I’ve seen versions that have a list of connecting nodes in a node, the problem with that is not all sides could be connected e.g. a square(node) has four sides top, right, bottom, left edges these can have a connection to another node.

Although the list will only have a maximum of four connections the order could be all over, with a list depending on what order they where inserted (yes you could order them) it’s an overload that I wanted to mitigate if at all possible then I though to make this easy on checking for connections each node could have four connection variables e.g. TopConnection, RightConnection, BottomConnection and LeftConnaction, this would greatly simplify checking.

Please can you let me know if I’m on the correct track, if you still think the other ways is best please can you make it in layman’s terms or I’ll get lost before you start.