[JASS] Checking if integer from a list is linked ?

[Ardenian]

I have an issue where I need to do the following:
I have n array variabled integers. Each integer can have the value of another integer variable array from the list.
Example:
Integer[1] = 5
Integer[5] = 3

Now I need to check the following:
If Integer[A] == Integer[?] then
If Integer[?] == Integer[??] and Integer[??] != A then

In words:
I need to check if a certain integer is linked to another and if that other integer is linked to another one and if that one is not linked to the first one.
I am not sure whether my approach is correct.

I aim for checking whether certain integers are not linked to another structure.

Example:

Integer[1] = 5
Integer[5] = 1
with all other variable values !=1 and !=5

Imagine it like bubbles. Integers form a bubble, linking to each other, and I need to check whether
there are more than one bubble, independent bubbles.

Any suggestions ?

 

[IcemanBo]

One needs to know the goal of it, because randomly making such checks does not really make sense, as it may just and in infinite actions.

I'm not sure, but it doesn't seem as a very good approach to structure indices/integers.

Could you explain?

 

[Anitarf]

What defines a "bubble", what do all integers in one bubble have in common? Why did they get added to that bubble and not another? It would be easier to check if two integers share that common property that makes them belong tot he same bubble, rather than actually checking if they are in the same bubble (which would require a loop). Also, your if statement doesn't make much sense to me, if A is in the same bubble as B and B is in the same bubble as C, then C must be in the same bubble as A, so what you're checking for can't possibly be true.

 

[Ardenian]

@IcemanBoa and Anitarf
Excuse, please, even in my native language I have no idea how to explain it.
Let me give you another example. Replace 'bubble' with 'room'.

Each room is numerated and indexed. This is the variable array, the room Id, if you wish to call it as such.
Each room is linked to only one other room. This is the value of the room variable.
-> Array = Room Id; Value = Another room the room is linked to

Many rooms being linked to each other form a structure, a 'bubble'.
Yes, Anitarf, my example was off, excuse.

My aim is to check if there are two different structures, two independent bubbles,
if there is no connection between two bunches of rooms.

For the example below, a black tile is one room.

This is alright, do nothing	This is bad, perform actions

I have no idea how to approach this. My only idea was to create a loop for the linked room,
checking if the room is linked to any room except the previous check ones and somehow filter out
if integers are not within that check/list.

 

[IcemanBo]

I'm still not sure I fully understand.

Each room is numerated and indexed.

"Numerated and Indexed."

So
room[0]
room[1]
room[2]
.. or something more?

Each room is linked to only one other room. This is the value of the room variable.

So
room[0] = 2
... means room[0] is linked to room[2].

-> Array = Room Id

"Array" -> means "Index in the Array"?

Many rooms being linked to each other form a structure, a 'bubble'.

But each room only can have one "next/linked" room, right?

My guess is you can index the "room-structure/complex" and bind it to the room, as kind of parent, at creation.

Set RoomsIndex = 1
loop
    CreateRoom()
    RoomCounter++
    Set RoomParent[RoomCounter] = RoomsIndex
endloop

// ^Created first "bunch" of rooms

Set RoomsIndex = RoomsIndex + 1
loop
    CreateRoom()
    RoomCounter++
    Set RoomParent[RoomCounter] = RoomsIndex
endloop

// ^Created next "bunch" of rooms, and so on

....

Later when you check if rooms are connected, you can compare:

if (RoomParent[i] == RoomParent[i]) then
    // are connected
endif

Is that it?

 

[Ardenian]

1. No, nothing more, that's how it is, yes.
2. Yes, exactly
3. Yes, with index I refer to the array
4. Yes, one room is linked actively to only one other one. However, the algorithm is concepted
to not link two rooms to each other.
Now I only need to make sure everything is connected somehow.

5. So from what I understand, I link all rooms to each other in your script ?
Well, I theory that's one solution, but I need to consider that in the best case,
only one room is connected to another, means there is only one connection to another room.
I am not sure how to alter your solution to consider this case.

 

[IcemanBo]

In the code no connection logic is included. Only provides a check if they share the same parent of rooms.

 

[Ardenian]

Could you elaborate the code further, please ?
From what I understand, you create a bunch of rooms and link them all to one.
In the second loop you create another, additional bunch of rooms and link them to the second room ?

Ohh I think I understand. I create parent rooms and create rooms to that parent, child rooms.
The parent rooms are linked to each other in a not yet defined way, yes ?

Hm, I think I had this solution when setting up my first code versions, but there were
certain problems with it ( related to the child room locations/range and overlapping).
However, this seems to be a great solution to avoid a needed check for having not connected rooms,
I think I give this solution a try and see how coding goes.
Thank you!

 

[IcemanBo]

Yes, but be aware that there is no real "ParentRoom". It's not a real room.
It's just an index that certain rooms share together, so they have the same parent.
An other room collection have an other RoomParent index and so are not linked to others.

 

[Ardenian]

I don't understand this point. If that parent is not a real one, how do I make sure every bunch
of rooms has a connection to each other bunch ?
Wouldn't I have then several bunches of rooms forming those bubbles from previous posts,
independently from each other ?

 

[IcemanBo]

how do I make sure every bunch
of rooms has a connection to each other bunch ?

To each other bunch? What does that mean?

Please stop calling it bubbles, it's just confusing me.
And I don't know what the last question means.

As I said I did not talk to any room_to_room connect, but only that if you have a room, you also know it's parent-index.
If you compare two rooms and want to check if they are within the same room-chain then you can just compare their parent-index.

 

[Ardenian]

Alright, forget the first stuff.

Okay, if they have the same parent-index, they are connected, yes.
But this would require two rooms to have the same parent.
I basically don't understand your concept of a parent room.

I thought, firstly, that I create an actual room, a parent room, and then attach child
rooms to it. Then I manually link all parent rooms and that's it, everything connected.

In your suggestion, a room has an imaginary parent room.
Well, I think the problem is that we have different concepts of what these rooms are.

If I linked one room to a second one, then I had basically that second one as parent.
But this does not allow me to directly check their parent or to say in detail,
what if two rooms have different linked parents, but these two linked parents share the same parent, a fifth room ?

 

[IcemanBo]

If I linked one room to a second one, then I had basically that second one as parent.

No.
Having parent has NOT to do with linking rooms.
It is totaly independant.

 

[Ardenian]

Well, uh, I search for a good way to link to check the rooms making sure everything is linked somehow.

Nonetheless, I can adapt the idea of parent rooms for my own, even if we see it as
completely different things, thank you

 

[Anitarf]

Okay, you have described the data structure that you are using, but not how you are using it. Before you can do your "bubble" check, you need to first establish the links between your rooms. The algorithm that establishes these links is the key, if that algorithm is good you might not even need your check to begin with. Of course, there are many different ways you can write such an algorithm, so you should try explaining what you are trying to do more generally. Then we can figure out the most suitable solution for your problem.

 

[Ardenian]

At the moment, my algorithm does the following:
It creates randomly rooms throughout the map. Then it selects randomly a random amount n.
Now comes the difficult part. I loop through all the rooms I selected and link them to one other,
but only if the other one is not linked to the currently looped one ( so they cannot be
linked vice-versa).
The decisive point is the distance between rooms. The priority is the higher the nearer a room is.
However, this can result into different, unconnected structures of linked rooms if they are far away from each other.

 

[Anitarf]

I think a better algorithm might be to first loop through all the combinations of two rooms and check if a link between them would intersect any other room. If not, add the link to an array of possible links. This has O(N^3) time complexity but that's okay, we don't have that many rooms. Once you have an array of all possible links, remove a certain percentage of them at random to get your maze.

Now, as you remove the links, here's where you'd add your checks to make sure you don't split your rooms into two unconnected sections. To do this check efficiently, each room would also need to keep track of all the rooms it is linked to, that way before removing a link between rooms A and B you can do an A* search for another path between A and B and if you don't find it, you don't remove the link.

 

[Ardenian]

Thanks Anitarf, intersection of a connection with a room is already considered and fixed.
I use a particular terrain type to mark the connections, but if a connection is within a room,
then no terrain type will be created within the room. This also contributes to randomization.

Hm, this sounds very complex. I think I might stay with my altered idea of IcemanBo's parent room
suggestion. It is a lot more easier to understand for me and already concepted.

To summarize, I am going to create parent rooms and connect them to each other.
Then, I loop through the parent rooms and create with chance child rooms and connect
them to the parent. With a small chance another child room will be created and linked to
the child room of the parent room.

Thank you both, Anitarf and IcemanBo, you helped me a lot!