Algorithm help

[FutureCow]

I'm designing a new game like the old pipe mania (aka pipe dreams) but I need some help with the algorithm for game play.

My problem is a bit hard to describe so I've drawn some simplified pics of a level to try to explain it

The game requires the player to make an enclosed pipe system, joining water sources to outlets, and passing through certain switches. Depending on the level, some switches / pipes will already be placed, the player adds various combinations of pieces to complete the level requirements.

In the attached image1 I have coloured some pieces to explain them
* water sources (yellow)
* water destination (red)
* T junctions connecting two pipes (pink)
* Switch (green) As you can see it has labelled inputs and an output on it.

The first thing I need to do when the player thinks they have "completed" the level is to check all pieces are connected. This is already done.
The second thing is where my issue is. Water is supposed to flow in the direction of the arrows as indicated by the second picture. Some pieces (like the taps, drain and switch) have definite inputs and output ends. The ends of the pipe pieces are variable depending on what they're connecting to (ie. sometimes water flows right to left in a horizontal pipe, other times left to right depending on which end ultimately connects to an output and which to an input).

It's a very easy thing to loop through every piece and check that where it has an output the next piece's end is an input. What I'm trying to avoid though is the player having to label each and every piece's ends as either input or output. So my problem is how do I programatically assign input/output sides to each bit of pipe in the diagram assuming the only pieces with known ends are the ones in red, green or yellow.

I was originally going to loop left to right, top to bottom as it's just a tiled map, but that wouldn't work if, for example the puzzle was the mirror of the one shown here (such that inputs were on the right, output on the left).
I think I need some sort of tree for each path, or a linked list or something. *shudder* I suspect I'm going to need recursion - but I have no idea how to do it in pseudocode let alone code it in GLBasic (assuming it supports recursion which I don't know yet!)

Does my description of the problem make sense?

The pieces are stored in a map[ x][y]   array of type where type has the fields
PieceType
Side1InputOrOutput
Side2InputOrOutput
Side3InputOrOutput
Side4InputOrOutput


[attachment deleted by admin]

[Kitty Hello]

Hehe.

OK, make a 2nd array that contains "points I already checked" flags, of the same size as your pipe array.

Then start at the furnace and look where the water flows. If if can flow, recursively call your function again, like this:

Code (glbasic) Select Expand




FUNCTION Flow: map%[], beenthere%[], x%, y%

beenthere[x][y] = TRUE // indicate not to peek this tile again
select map[x][y] // what part
   case 0: // I bar , e.g.
      if beenthere[x][y-1] = false
         Flow(map[], beenthere[], x,y-1)
      endif
      if beenthere[x][y+1] = false
        Flow(map[], beenthere[], x,y+1)
      endif
   case 1; // - bar....
endselect

endfunction


I hope you get the idea.

[FutureCow]

Gaaaaa! Recursion!!! 

Thanks Gernot, I wasn't sure that GLBasic would handle recursion - when I searched for "recursion" on the website the only page that came back was one related to "Puyo Puyo" where you said

The problem of finding >3 connected, same-color blocks can be found in many ways. This one is not the most elegant or fastest, but it's the easiest to understand, I guess - if you exclude the recursion one, which might fail due to a stack overflow.

I couldn't work out from that whether you meant GLBasic would have stack issues with recursion. It's great to see your example though - I haven't written a recursive algorythm in 10 years or so. This gives me a great idea where to start - many thanks!!!

[Hemlos]

Any issues with throwing 2 dimensional arrays of types at recursive functions?

Only in the coding of it...glbin.exe will crash if the DIM array input exceeds the bounds.

[FutureCow]

Thanks Hemlos, I'm sure I'll manage to crash it at some point.  (The first time I try my code is pretty much guaranteed to crash! )
At least I know what to look out for!

[Kitty Hello]

Aye, recursion could cause a stack oerflow. His array is not big enough, though.

[FutureCow]

How much data would you need to be consuming through recursion to overflow the stack?
What sort of error would you expect to see?

[Hemlos]

How much data would you need to be consuming through recursion to overflow the stack?
What sort of error would you expect to see?

What i mean is just becareful not to put in more inputs than the array bounds...either using a DIMPUSH or REDIM can solve the issue. But if your bounds are fixed, and limit the number of inputs, to not exceed the number of slots in the DIM; you wont get an error.

The error wil be, when you start the program...it will just crash and close the program.

Thats the only thing about DIM arrays you need to watch out for, because the editor wont tell you that you created an overflowing array....the game just simply crashes at DIM initialization.

The way i use a DIM is a bit dirty....
If i only need 100-200 slots, and it fluxuates to and from alot....i would just preset the DIM array[999]
The trick is not rolling through the whole array, just read the indexes you need in small clusters.
The way to optimize would be to predefine an imaginary bounds into a variable...so you dont need to read excessive data.

[Kitty Hello]

DIMPUSH automatically resizes the array if required.
Yes, using a DIMPUSH solution over recursion is often better when you fill big arrays. For small arrays, the recursion is pretty fine.

[Moru]

If you are adding a lot of data to big arrays I would suggest making your own read/write pointer and allocate a large ammount of memory each time the pointer gets close to the array limit. Using dimpush makes it quite slow when you are getting bigger arrays.