Castle Paradox

[Mr B]

This question was brought up by a couple of projects I had been mulling over, and finalized by my PoliSci teacher's lecture on representative districts.

The question is this: how can I determine whether adding or removing a segment from a group (for the purposes of simplicity, assume I'm talking about a tile on a grid) cam be done without breaking it up into two groups?

For example, let's say that I am programming next year's hot game, Circulatory System Tycoon. Cells can only recieve the benefit of a blood supply if the blood vessel they are adjacent to is also connected to the heart. For adding vessel segments, this wouldn't be very difficult -- segments can only be added if they are adjacent to pre-existant segments. If the heart is the first segment created, then no problem exists.

However, what about removing vessel segments? What if removing a segment causes other segments to be divorced from the heart? (we'll assume that we don't need to worry about creating functional loops so that the blood can actually cycle...) What if removing one segment causes the circulatory system to break into two circulatory systems, one of which does not have a heart?

I thought of a few different solutions, all but one of which ended up being really poor. This last one seems to work, but I am not sure about it and I don't know if it's the best way.

I'll start out by defining what I think a cohesive area is.

Cohesive Area Definition #1: A cohesive area is an area such that a path may be drawn from any point within the area to any other point within the area such that the path does not need to cross any points not within the area.

Cohesive Area Definition #2: A cohesive area is an area such that all points are contained within a single edge.

Definition #2 is simpler and probably easier to work with, but I don't know if it's actually true... Even if it is, how can you get a computer to define "inside of an edge?"

I'll work with def #2 for the time being.

Anyways, my addition algorithm is pretty simple. A segment may be added only if it will be in contact with a pre-existant segment.

The subtraction algorithm is giving me a little trouble. How to tell when removing a point will not make the area uncohesive? The solution I found was to have a little bug (er, process) that runs around the edge of the point to be removed, such that it is always hugging an edge. For each connection on the point to other points of the same time (for a tile, this would be the four sides) a bug is generated. Each bug runs runs with the same handedness (i.e., they will all hug edges to their left, or all to their right).

If a bug reaches an edge of its area type it pursues that edge until it meets up with the point to be removed again.

When a bug reaches the "birthplace" of another bug, it is successful and dies. If a bug reaches its own birthplace without touching the birthplace of any other bug, then it is in an area separate from the other bugs and thus the removal would be invalid (since it would form two separate areas). (this is only true if the point to be removed is adjacent to two or more other points of its own kind -- if it were at the tip of a peninsula it would only spawn one bug; this problem could be easily solved by straight-out permitting the removal of any point that is adjacent to only one other point of its own kind).

Note that bugs will only die successfully if they recross their own birthplace in the same orientation as they left it. This prevents them from falsely dying if they happen to hit their birthplace coming back from a peninsula or somesuch.

Of course, if bug Alfred hits the birthplace of bug Bethany, then they can both immediately die knowing that they succeeded in their mission, since if Alfred is in the same area as Bethany, then Bethany is in the same area as Alfred.

Let me give an example:

[TMC]

Sorry, short answer and I prehaps didn't read over very well, going to bed.

I'm not sure Cohesive Area Definition #2 is bullet proof, it depends on which edge you choose. I don't know if it actually is a problem for the method you describe below, but:

[msw188]

I don't like Topology.

Okay, I haven't read your entire post yet, but I have to go and I want to point out quickly before I forget:

Your definition #2 is okay only under certain conditions. The main one I can think of now is that the edge cannot cross itself (like a figure eight). You also are not running an if and only if here. I mean that there exist fully cohesive areas that have more than one 'edge'. For example, a flat donut would be such an area. Inside-ness and outside-ness is a problem, too. I'll be back in a few minutes, I'll type more about it then.

Okay, I'm back, so the rest of this is an edit.

Shoot, I can't 'review' the post while I edit. I will start a new post. Sorry about the soon-to-be double post.

[msw188]

Okay, your bug algorithm seems to get around some of the problems I was pointing out in your definition of a cohesive area (you will notice that your algorithm does not really count edges at all, but rather asks the question 'can I travel from one spot on this edge to another spot on this edge, without leaving the area?'). This seems all well and good, and the only thing I can think of to add is this:
You do not need to have the bugs hit each other's birthplaces in order necessarily. You can set it so that if bug 1 meets bug 2, then ONE of the bugs (along with its birthplace) dies, and then let the other bug continue. If all but one of the bugs die in this way, then you are connected. This may be important for trying to use this algorithm for things other than OHR maps, where your 'area' may be more than two dimensional (and thus your 'edges' more than one dimensional lines, so that they need not be so simply cyclic; I don't think it has any real effect on your current situation).

Actually, your algorithm is so based on the idea of traveling along a linear wall that it will not work in more than two dimensions in any case. So I'm pretty sure either your cyclic method or my method will work equally well. I'm not sure which would be easier to program.

In addition, I thought I'd mention that there is an easy way for a computer to tell whether it is on the inside or outside of a simple closed curve, that you are probably familiar with - go out toward 'infinity' (or the furthest border of the map) and count how may times you pass through an edge. If the answer is odd, you were 'inside', if even, you were 'outside'. Note that this only works if you know beforehand that there is only one edge that you are dealing with.

[Mike Caron]

[msw188]

Sorry, when I said that bugs meet, I meant either they meet or one hits the other's birthplace.

[Mr B]

It should probably be that the bug that steps on the birthplace is the one that dies. If the other one dies then the first one will have to cover all of its path over again for no reason.

[Bob the Hamster]

I find this question fascinating, but it was a little over my head.. However, I showed it to Brian and he had lots of interesting things to say about this. I quote his e-mail here:

[Mike Caron]

Hmm, he raises a valid point: Why do we need to care about whether it's connected or not when we're deleting a tile?

In SimCity, for example, every time the sim is updated, the engine does such a brute force check from every Water Pump to determine whether there's water there. If you break the link, then it'll be reflected in the next cycle.

Of course, there's other factors as well, in that case, such as water supply vs watering area which might make a pipe unwatered, but it's the same idea.

I can't imagine many situations in which you cannot allow the chain to be broken without adverse effects.
_________________
I stand corrected. No rivers ran blood today. At least, none that were caused by us.

Final Fantasy Q
OHR Developer BLOG
Official OHRRPGCE Wiki and FAQ

[Mr B]

[Bob the Hamster]

[Mike Caron]

[Mr B]

[msw188]

You're right. I guess I really meant 'only one type of edge', rather than just one edge. You also need to make sure that you're 'infinity' is not a member of 'my area', otherwise this will be getting it backwards.

The main reason we are having these sorts of misunderstandings, I think, is that I am thinking in terms of 'inside' and 'outside', whereas you seem to be thinking more in terms of 'area A' versus 'area B'. The idea is still the same though. The only other problem I can think of is corners, or traveling along an edge. This may not be easy for a computer to recognize. Do you see what I mean? I have to go for now...

[Mr B]

Yeah; I was thinking in terms of areas, not edges. I was using edges as a means of defining areas.

And as was mentioned, the usefulness of an edge algorithm is probably restricted to a 2-D field.